Cryptographically secure PRBGs and the previous-bit test I am reading Junod's paper about the Blum-Blum-Shub PRBG (BBS) and I am having trouble following his reasoning at on page 15, where he argues that the next-bit test can also be peformed for the previous bit in the bit sequence $b_0b_1 \ldots b_k$ , i.e. an attacker can also try to predict $b_{-1}$. If I understand him correctly he deems this obvious as the next-bit test is equivalent to the polynomial-time statistical tests, the latter one being obviously indifferent to a reversal of the given bit sequence.
But I do not understand how this should be applicable, since (in my eyes) random number generators can in any case only build sequences that &quot;extend in one direction infinitely&quot; as they have to have some kind of starting point and the previous bit test can not be applied at the starting bit $b_0$, since there is no previous bit. So wgat is $b_{-1}$ supposed to mean?
Can you explain this to me?
If you only have a subsequence of the output that does not include the first bit, then the bits of your subsequence can be labeled $b_0$, $b_1$, $\dots$. The bits of the overall sequence from which they are taken would then be labeled $\dots$, $b_{-1}$, $b_0$, $b_1$, $\dots$.
In other words, you're not necessarily starting the labeling of the bits at the beginning of the generator output, but rather at some later point. In that case there is a previous bit, and the previous-bit test applies.