Yao's XOR lemma

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.

Let ${\displaystyle P}$ be a polynomial, and ${\displaystyle S=\{S_{k}\}_{k}}$ be a collection of sets ${\displaystyle S_{k}}$ of ${\displaystyle P(k)}$-bit long sequences, and for each ${\displaystyle k}$, let ${\displaystyle \mu _{k}}$ be a probability distribution on ${\displaystyle S_{k}}$, and ${\displaystyle P_{C}}$ be a polynomial. A predicting collection ${\displaystyle C=\{C_{k}\}}$ is a collection of boolean circuits of size less than ${\displaystyle P_{C}(k)}$. Let ${\displaystyle p_{k,S}^{C}}$ be the probability that on input ${\displaystyle s}$, a string randomly selected in ${\displaystyle S_{k}}$ with probability ${\displaystyle \mu (s)}$, ${\displaystyle C_{k}(s)=1}$, i.e.

...
Wikipedia