Yao's test
Encyclopedia
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.
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 
:
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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and the theory of computation
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, 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.
Boolean circuits
Let be a polynomial, and be a collection of sets of -bit long sequences, and for each , let be a probability distributionProbability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
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
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 undecidableUndecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
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.