In cryptography and the theory of computation, Yao's test is a test defined by Andrew Chi-Chih Yao in 1982,[1] 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.
be a collection of sets
-bit long sequences, and for each
μ
be a probability distribution on
A predicting collection
is a collection of boolean circuits of size less than
be the probability that on input
, a string randomly selected in
with probability
μ ( s )
with probability
μ
{\displaystyle p_{k,S}^{C}={\mathcal {P}}[C_{k}(s)=1|s\in S_{k}{\text{ with probability }}\mu _{k}(s)]}
be the probability that
-bit long sequence selected uniformly at random in
passes Yao's test if for all predicting collection
, for all but finitely many
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.