Yao's test


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 be a polynomial, and be a collection of sets of -bit long sequences, and for each, let be a probability distribution on, and be a polynomial. A predicting collection is a collection of boolean circuits of size less than. Let be the probability that on input, a string randomly selected in with probability,, i.e.


Moreover, let be the probability that on input a -bit long sequence selected uniformly at random in. We say that passes Yao's test if for all predicting collection, for all but finitely many, for all polynomial :

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. 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.