Yao's test

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_{k,S}^C 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_{k,S}^C={\mathcal P}[C_k(s)=1 | s\in S_k\text{ with probability }\mu_k(s)]

Moreover, let p_{k,U}^C 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_{k,S}^C-p_{k,U}^C|<\frac{1}{Q(k)}

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. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
This article is issued from Wikipedia - version of the Thursday, May 05, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.