Pseudorandomness

Pseudorandomness means that specified tests cannot effectively distinguish a generated distribution from a genuinely random reference distribution. The allowed tests and their advantage are part of the definition. Passing a few frequency tests does not imply security against every feasible computation.

A pseudorandom generator expands a uniformly chosen $s$-bit seed to $m>s$ bits. For a test $D$, its distinguishing advantage isHere $U_k$ denotes a uniformly sampled $k$-bit string. There are at most $2^s$ generated strings, so an unrestricted test for membership in the generator's range distinguishes with advantage at least $1-2^{s-m}$. The useful claim is therefore computational indistinguishability for a restricted test class, not equality of the two distributions. Such a generator can replace random choices in an algorithm when the relevant computation is among the tests it fools.^[ref]