The above definition of randomness is very robust, if not practical. True
random generators are rarely used in computing. The problem is *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 *pseudo-random*
strings from a short seed. Such methods were justified in [Blum Micali], [Yao]:

First, take any one-way permutation (see sec. 5.5) with a *
hard-core* bit (see below) which is easy to compute from **x,p**, but
infeasible to guess from with any noticeable correlation.

Then take a random *seed* and
Repeat: ().

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, , and . Then , 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 *perfect*.

**Theorem**: [Yao] Let run in time .
Let a probabilistic algorithm **A** in expected (over internal coin flips)
time accept and truly random strings with different by **d**
probabilities. Then, for random **i**, one can use **A** to guess from
in time with correlation .

Proof: Let be the probability that
**A** accepts modified by replacing its
first **i** digits with truly random bits. Then is the probability of
accepting and must differ by **d** from the probability of accepting
random string. Then , for randomly chosen **i**.
Let and be the probabilities of acceptance of **r0x** and **r1x**
for random **r** of length **i-1**. Then averages to for
, while
averages to and to .
So, has the stated correlation with . Q.E.D.

If the above generator was not perfect, one could guess from the sequence
with a polynomial (in ) correlation. But,
can be produced from . So, one could
guess from with correlation , which cannot be done
for hard-core **B**.

Let . [Goldreich Levin] converts any
method **g** of guessing from with correlation
into an algorithm of finding **x**, i.e. inverting **F** (slower
times than **g**).

**Proof.** Take **k=|x|=|y|**, , .
Let and .

Assume, for , guesses with
correlation , where abbreviates
, since **w,y** are fixed throughout the proof.

Averaging over random pairwise
independent **p** deviates from its average by (and so is **>0**)
with probability . The same for .

Take a random matrix . Then the vectors **Pr**,
are pairwise independent. So, for a fraction
of **P**, sign. We could
thus find for all **i** with probability if we knew **z=xP**. But **z**
is short: we can try all possible values!

So the inverter, for a random **P** and all **i,r**, computes .
It uses Fast Fourier on to compute . The sign
of is the **i**-th bit for the **z**-th member of output list. Q.E.D.

Wed Aug 21 20:35:42 EDT 1996