Pseudorandomness

A distribution is considered pseudorandom if no efficient computation can distinguish it from the true uniform distribution by a non-negligible advantage. Formally, a family of distributions D_n is pseudorandom if for any polynomial size circuit C, and any ε inversely polynomial in n

|Prob_x∈U [C(x)=1] − Prob_x∈D [C(x)=1] | ≤ ε.

Pseudorandom generators

A function G_l: {0,1}^l → {0,1}^m, where l < m is a pseudorandom generator if:

• G_l can be computed in time polynomial in l
• G_l(x) is pseudorandom, when x is uniformly random.

One additional pseudorandom bit implies polynomially more pseudorandom bits

It can be shown that if there is a pseudorandom generator G_l: {0,1}^l → {0,1}^l+1, i.e. a generator that adds only one pseudorandom bit, then for any m = poly(l), there is a pseudorandom generator G'_l: {0,1}^l → {0,1}^m.

The idea of the proof is as follows: first s bits from uniform distribution U_l are picked and used as the seed to the first instance of G_l, which is known to be a pseudorandom generator. Next, the output of the first instance of G_l is divided into two parts: first l bits are fed into the second instance of G_l as a seed, while the last bit becomes the first bit of the output. Repeating this process for m times yields an output of m pseudorandom bits.

It can be shown that such G'_l, that consists of m instances of G_l, is indeed a pseudorandom generator by using a hybrid approach and proof by contradiction as follows:

Consider m+1 intermediate distributions H_i: 0  ≤  i  ≤  m, where first i bits are chosen from the uniform distribution, and last m − i bits are chosen from the output of G'_l. Thus, H₀ is the full output of G'_l and H_m is a true uniform distribution U_m. Therefore, distributions H_i and H_i+1 will be different in only one bit (bit number i+1).

Now, assume that G'_l is not a pseudorandom distribution; that is, there exists some circuit C that can distinguish between G'_l and U_m with an advantage ε  =   1/poly(l). In other words, this circuit can distinguish between H₀ and H_m. Therefore, there exists such i that the circuit C can distinguish between H_i and H_i+1 by at least ε / m. Note, that since m are polynomial in l, then ε / m is also polynomial in l and is still a non-negligible advantage.

Now, assume we are given l+1 bits that are either output of G_l or a drawn from uniform distribution. Let's reuse the approach of building large pseudorandom generators out of instances of G_l and construct a string of pseudorandom bits of length m−i−1 in the same way the G'_l was constructed above using the first l given bits as the seed. Then, let's create a string consisting of i bits drawn from uniform, concatenated with the last one of the given bits, followed by the created m−i−1 bits. The resulting output is either H_i or H_i+1, since the i+1 bit is either drawn from uniform or from G_l. Since by assumption we can distinguish between H_i and H_i+1 with non-negligible advantage, then we can distinguish between U and G_l, which implies that G_l is not a pseudorandom generator, which is a contradiction to the hypothesis. Q.E.D.

Now, let's illustrate that if exists, the circuit for distinguishing between G_l and U_l+1 does not have to toss random coins. As we showed above, if exists a circuit C for distinguishing between G'_l and U_m, where m = poly(l), then exists a circuit C' for distinguishing between G_l and U_l+1 that uses i random bits. For this circuit C' : | Prob_{u, s} [C' (u₁,...,u_i,G_l(s)) = 1 ] − Prob_{u, y} [C' (u₁,>,...,u_i,y) = 1] | ≥ ε / m,

where u is a string of i uniformly random bits, s is a string of l uniformly random bits, and y is a string of l+1 uniformly random bits.

Then,

Prob_u[ | Prob_s [C' (u₁,...,u_i,G_l(s)) = 1] - Prob_y [C' (u₁,...,u_i,y) = 1] | ] ≥ ε / m;

Which means, there exists some fixed string u of i bits that can be used as an "advice" to circuit C' for distinguishing between G_l and U_l+1.

Definitions

Proof

Here an outline of the proof is given. Please see references for detailed proofs.

1. Given z=f(x) guess bit b 
2. Run C on z.b
3. IF C(z.b)=1
4.     output b
5. ELSE
6.     output 1-b