Yao's test

Short description: Cryptographical test for pseudo-randomness

In cryptography and the theory of computation, Yao's test is a test defined by Andrew Chi-Chih Yao in 1982, against pseudo-random sequences. A sequence of words passes Yao's test if an attacker with reasonable computational power cannot distinguish it from a sequence generated uniformly at random.

Formal statement

Boolean circuits

Let [math]\displaystyle{ P }[/math] be a polynomial, and [math]\displaystyle{ S=\{S_k\}_k }[/math] be a collection of sets [math]\displaystyle{ S_k }[/math] of [math]\displaystyle{ P(k) }[/math]-bit long sequences, and for each [math]\displaystyle{ k }[/math], let [math]\displaystyle{ \mu_k }[/math] be a probability distribution on [math]\displaystyle{ S_k }[/math], and [math]\displaystyle{ P_C }[/math] be a polynomial. A predicting collection [math]\displaystyle{ C=\{C_k\} }[/math] is a collection of boolean circuits of size less than [math]\displaystyle{ P_C(k) }[/math]. Let [math]\displaystyle{ p_{k,S}^C }[/math] be the probability that on input [math]\displaystyle{ s }[/math], a string randomly selected in [math]\displaystyle{ S_k }[/math] with probability [math]\displaystyle{ \mu(s) }[/math], [math]\displaystyle{ C_k(s)=1 }[/math], i.e.

[math]\displaystyle{ p_{k,S}^C={\mathcal P}[C_k(s)=1 | s\in S_k\text{ with probability }\mu_k(s)] }[/math]

Moreover, let [math]\displaystyle{ p_{k,U}^C }[/math] be the probability that [math]\displaystyle{ C_k(s)=1 }[/math] on input [math]\displaystyle{ s }[/math] a [math]\displaystyle{ P(k) }[/math]-bit long sequence selected uniformly at random in [math]\displaystyle{ \{0,1\}^{P(k)} }[/math]. We say that [math]\displaystyle{ S }[/math] passes Yao's test if for all predicting collection [math]\displaystyle{ C }[/math], for all but finitely many [math]\displaystyle{ k }[/math], for all polynomial [math]\displaystyle{ Q }[/math] :

[math]\displaystyle{ |p_{k,S}^C-p_{k,U}^C|\lt \frac{1}{Q(k)} }[/math]

Probabilistic formulation

As in the case of the next-bit test, the predicting collection used in the above definition can be replaced by a probabilistic Turing machine, working in polynomial time. This also yields a strictly stronger definition of Yao's test (see Adleman's theorem). Indeed, One could decide undecidable properties of the pseudo-random sequence with the non-uniform circuits described above, whereas BPP machines can always be simulated by exponential-time deterministic Turing machines.