Statistical test on {0,1}^n:

an algorithm A such that A(x) outputs “0”(not random) or “1”(random)

A(x) = 1 if and only if the number of generated 1s are not hugely different from the number of 0s

A(x) = 1 if and only if the number of two consecutive 0s are not dramatically different from a quarter of the total number of bits.

A(x) = 1 if and only if max-run-of-o(x) <= 10 * log2(n)

Advantage[A,G] = | Pr[A(G(k))=1] – Pr[A(r)=1] |

Advantage close to 1 -> A can distinguish G from random

Advantage close to 0 -> A cannot distinguish, or the PRG is pretty much like random

secure PRG <=> Advantage[A,G] is negligible for all efficient statistical tests.

Thm(Yao’82), an unpredictable PRG is secure