Yao's test explained

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.

Formal statement

Boolean circuits

Let

P be a polynomial, and S = \{S _{k\}} _{k} be a collection of sets S _{k} of P(k) -bit long sequences, and for each k , let \mu _{k} be a probability distribution on S _{k} , and P _{C} be a polynomial. A predicting collection C = \{C _{k\}} is a collection of boolean circuits of size less than P _{C(k)} . Let p ^{C} _{k,S} be the probability that on input s , a string randomly selected in S _{k} with probability \mu(s) , C _{k(s)=1} , i.e.p ^{C = { l P}[C} _{k(s) =1} | s\in S _{kwithprobability\mu} _{k(s)]}

Moreover, let

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

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.

References

1. [Andrew Chi-Chih Yao]