The Next Bit Theorem

It would certainly be undesirable if there were an efficient algorithm which took as input the first $k$ bits of the sequence from the generator and guessed the $(k+1)$-st bit with probability much greater than $1/2$. We say a generator satisfies the Next Bit Condition if there is no such algorithm.

Theorem 29   If (QRA) is true, the quadratic generator satisfies the Next Bit Condition.

Proof: We will show that an algorithm that could predict the $(k+1)$-st bit could be used to distinguish squares from pseudo-squares mod $n$.

Let $b\in Z^1_n$. The sequence of length $k$

$$b^{2^k}\quad b^{2^{k-1}}\dots b^4\quad b^2$$

can be considered as coming from the quadratic generator with seed the first term of the sequence. If we take this sequence mod 2 and give it to our predictor, we would get a guess as to whether

$$\sqrt{b^2}\equiv0\hbox{ or }1\hbox{ (mod }2)$$

which has probability $>1/2$ of being right. The principle square root of $b^2$ is $b$ if $b$ is a square, $n-b$ if $b$ is a pseudo-square. Since $b\not\equiv n-b$ mod 2, the information from the predictor gives us a guess as to whether $b$ is a square.