# Yao's test

Jump to navigation Jump to search

In cryptography and the theory of computation, Yao's test is a test defined by Andrew Chi-Chih Yao in 1982, 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.