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.