Next-bit test - WikiHQ

In cryptography and the theory of computation, the next-bit test is a test against pseudo-random number generators. We say that a sequence of bits passes the next bit test for at any position <math>i</math> in the sequence, if any attacker who knows the <math>i</math> first bits (but not the seed) cannot predict the <math>(i+1)</math>st with reasonable computational power.

Precise statement(s)

Let <math>P</math> be a polynomial, and <math>S=\{S_k\}</math> be a collection of sets such that <math>S_k</math> contains <math>P(k)</math>-bit long sequences. Moreover, let <math>\mu_k</math> be the probability distribution of the strings in <math>S_k</math>.

We now define the next-bit test in two different ways.

Boolean circuit formulation

A predicting collection <math>C=\{C_k^i\}</math> is a collection of boolean circuits, such that each circuit <math>C_k^i</math> has less than <math>P_C(k)</math> gates and exactly <math>i</math> inputs. Let <math>p_{k,i}^C</math> be the probability that, on input the <math>i</math> first bits of <math>s</math>, a string randomly selected in <math>S_k</math> with probability <math>\mu_k(s)</math>, the circuit correctly predicts <math>s_{i+1}</math>, i.e. :

<math>

p_{k,i}^C={\mathcal P} \left[ C_k(s_1\ldots s_i)=s_{i+1} \right | s\in S_k\text{ with probability }\mu_k(s)]

</math>

</div>

Now, we say that <math>\{S_k\}_k</math> passes the next-bit test if for any predicting collection <math>C</math>, any polynomial <math>Q</math> :

</div>

Probabilistic Turing machines

We can also define the next-bit test in terms of probabilistic Turing machines, although this definition is somewhat stronger (see Adleman's theorem). Let <math>\mathcal M</math> be a probabilistic Turing machine, working in polynomial time. Let <math>p_{k,i}^{\mathcal M}</math> be the probability that <math>\mathcal M</math> predicts the <math>(i+1)</math>st bit correctly, i.e.

<math>p_{k,i}^{\mathcal M}={\mathcal P}[M(s_1\ldots s_i)=s_{i+1} | s\in S_k\text{ with probability }\mu_k(s)]</math>

</div>

We say that collection <math>S=\{S_k\}</math> passes the next-bit test if for all polynomial <math>Q</math>, for all but finitely many <math>k</math>, for all <math>0<i<k</math>:

<math>

p_{k,i}^{\mathcal M}<\frac{1}{2}+\frac{1}{Q(k)}

</math>

</div>

Completeness for Yao's test

The next-bit test is a particular case of Yao's test for random sequences, and passing it is therefore a necessary condition for passing Yao's test. However, it has also been shown a sufficient condition by Yao.