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 "extend in one direction infinitely" 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?

  • 1
    $\begingroup$ if you can predict the next bit, then you can use this idea to predict -1. For the simplest case consider the LFSR. $\endgroup$ – kelalaka Sep 20 '20 at 19:51
  • $\begingroup$ Sorry, but I do not get what $b_{-1}$ is supposed to resemble since the BBS-generator builds a sequence of the form $b_0b_1 \ldots$ . $\endgroup$ – 3nondatur Sep 21 '20 at 9:41
  • 1
    $\begingroup$ I used it since you used. You can consider it like given any k bits of the sequence if you can predict the next bit better than random coin flipping then you can convert the idea to find the bit before the given k bits. $\endgroup$ – kelalaka Sep 21 '20 at 10:00
  • $\begingroup$ But why should $b_{-1}$ exist? I mean the BBS-generator starts its output with $b_0$, so $b_0$ has no previous bit. $\endgroup$ – 3nondatur Sep 21 '20 at 10:09

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.