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.

gollark: IIRC you can read text off them *and* you can definitely set it.

gollark: There are tons of misapplied communication channels available:- shared disks- redstone- bundled redstone- computer labels- connected signs

gollark: Disknet.

gollark: It's been done.

gollark: Er, just guess that any missile close to the last position of a missile is the same missile.

References

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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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