= Pseudorandomness
<Pseudorandomness> means that specified tests cannot effectively distinguish a generated <probability distribution>[distribution] from a genuinely random reference <probability distribution>[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 <discrete uniform distribution>[uniformly chosen] $s$-bit seed to $m>s$ bits. For a test $D$, its distinguishing advantage is
$$
\left|\Pr[D(G(U_s))=1]-\Pr[D(U_m)=1]\right|.
$$
Here $U_k$ denotes a <discrete uniform distribution>[uniformly sampled] $k$-bit string. There are at most $2^s$ generated <string>[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.<Introduction to Theoretical Computer Science by Boaz Barak>[Modeling randomized computation, Pseudorandom generators]{ref}
Back to article page
