\newpage\subsection{Pseudo-randomness.\label{pseudor}}

The above definition of randomness is very robust, if not practical. True
random generators are rarely used in computing. The problem is {\em not} that
making a true random generator is impossible: we just saw efficient ways to
perfect the distributions of biased random sources. The reason lies in many
extra benefits provided by pseudorandom generators. E.g., when experimenting
with, debugging, or using a program one often needs to repeat the exact same
sequence. With a truly random generator, one actually has to record all its
outcomes: long and costly. The alternative is to generate {\em pseudo-random}
strings from a short seed. Such methods were justified in [Blum Micali], [Yao]:

First, take any one-way permutation $F_n(x)$ (see sec.~\ref{crypt}) with a {\em
hard-core} bit (see below) $B_p(x)$ which is easy to compute from $x,p$, but
infeasible to guess from $p,n,F_n(x)$ with any noticeable correlation.\\
 Then take a random {\em seed} $x_0,p,n\in\{0,1\}^k$ and
 Repeat: ($S_i\gets B_p(x_i);\, x_{i+1}\gets F_n(x_i);\, i\gets i+1$).

We will see how distinguishing outputs $S$ of this generator from strings of
coin flips would imply a fast inverting of $F$ (believed impossible).

But if P=NP (a famous open problem), no one-way $F$, and no pseudorandom
generators could exist.

By Kolmogorov's standards, pseudo-random strings are not random: let $G$ be the
generator; $s$ be the seed, $G(s) = S$, and $|S|\gg k=|s|$. Then $K(S) \le
O(1)+ k \ll |S|$, so this violates Kolmogorov's definition. We can distinguish
between truly and pseudo- random strings by simply trying all short seeds.
However this takes time exponential in the seed length. Realistically, a
pseudo-random string will be as good as a truly random one if they can't be
distinguished in feasible time. Such generators we call {\em perfect}.

{\bf Theorem}: [Yao] Let $G(s)=S\in\{0,1\}^n$ run in time $t_G$.
 Let a probabilistic algorithm $A$ in expected (over internal coin flips)
 time $t_A$ accept $G(s)$ and truly random strings with different by $d$
probabilities. Then, for random $i$, one can use $A$ to guess $S_i$ from
$S_{i+1},S_{i+2}, \ldots$ in time $t_A+t_G$ with correlation $d/O(n)$.

Proof: Let $p_i$ be the probability that $A$ accepts $S=G(s)$ modified by
replacing its first $i$ digits with truly random bits. Then $p_0$ is the
probability of accepting $G(s)$ and must differ by $d$ from the probability
$p_n$ of accepting random string. Then $p_{i-1}-p_i = d/n$, for randomly chosen
$i$. Let $P_0(x)$ and $P_1(x)$ be the probabilities of acceptance of $r0x$ and
$r1x$ for random $r$ of length $i-1$. Then $(P_1(x)+P_0(x))/2$ averages to
$p_i$ for $x=S_{i+1}, S_{i+2},\ldots$, while
$P_{S_i}(x)=P_0(x)+(P_1(x)-P_0(x))S_i$ averages to $p_{i-1}$ and
$(P_1(x)-P_0(x)) (S_i-1/2)$ to $p_{i-1}-p_i = d/n$. So, $P_1(x)-P_0(x)$ has the
stated correlation with $S_i$. Q.E.D.

If the above generator was not perfect, one could guess $S_i$ from the sequence
$S_{i+1},S_{i+2},\ldots$ with a polynomial (in $1/|s|$) correlation. But,
$S_{i+1}, S_{i+2}\ldots$ can be produced from $p,n,x_{i+1}$. So, one could
guess $B_p(x_i)$ from $p,n,F(x_i)$ with correlation $d/n$, which cannot be done
for hard-core $B$.

 \paragraph {Hard Core.} The key to constructing a pseudorandom generator is
finding a hard core for a one-way $F$. The following $B$ is hard-core for any
one-way $F$, e.g., for Rabin's OWF in sec.~\ref{crypt}. [Knuth 1997, v.2, 3d
ed., Chap.3.5.F Pseudorandom numbers, pp.36, 170-179] has more details and
references.

Let $B_p(x)=(x\cdot p)= (\sum_ix_ip_i\bmod2)$. [Goldreich Levin] converts any
method $g$ of guessing $B_p(x)$ from $p,n,F(x)$ with correlation $\varepsilon$
into an algorithm of finding $x$, i.e.\ inverting $F$ (slower $\varepsilon^2$
times than $g$).

{\bf Proof.} Take $k=|x|=|y|$, $j=\log(2k/\varepsilon^2)$, $v_i= 0^i10^{k-i}$.
 Let $B_p(x) =(x\cdot p)$ and $b(x,p)=(-1)^{B_p(x)}$.

Assume, for $y=F_n(x)$, $g(y,p,w)\in\{\pm 1\}$ guesses $B_p(x)$ with
correlation $\sum_p2^{-|p|}b(x,p) g_p >\varepsilon$, where $g_p$ abbreviates
$g(y,p,w)$, since $w,y$ are fixed throughout the proof.

Averaging $(-1)^{(x\cdot p)} g_p$ over $>2k/\varepsilon^2$ random pairwise
independent $p$ deviates from its average by $<\varepsilon$ (and so is $>0$)
with probability $>1-1/2k$. The same for $(-1)^{(x\cdot[p+v_i])} g_{p+v_i}=
(-1)^{(x\cdot p)} g_{p+v_i} (-1)^{x_i}$.

Take a random matrix $P\in\{0,1\}^{k\times j}$. Then the vectors $Pr$,
$r\in\{0,1\}^j\setminus\{0^j\}$ are pairwise independent. So, for a fraction
$\ge1-1/2k$ of $P$, sign$\sum_r (-1)^{xPr} g_{Pr+v_i}= (-1)^{x_i}$. We could
thus find $x_i$ for all $i$ with probability $>1/2$ if we knew $z=xP$. But $z$
is short: we can try all $2^j$ possible values!

So the inverter, for a random $P$ and all $i,r$, computes $G_i(r)=g_{Pr+v_i}$.
It uses Fast Fourier on $G_i$ to compute $h_i(z)=\sum_rb(z,r)G_i(r)$. The sign
of $h_i(z)$ is the $i$-th bit for the $z$-th member of output list. Q.E.D.