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.