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

edit

Boolean circuits

edit

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

edit

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

edit
  1. ^ Andrew Chi-Chih Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.