Pseudorandom generator theorem

Pseudorandomness

In computational complexity a distribution is considered pseudorandom is 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 ε polynomial in n

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

Pseudorandom generator

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

Pseudorandom generator theorem

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 distributin 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 hybrid approach and proof by contradiction as follows:

Let's 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, 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, last one of the given bits, and 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 betwenn U and G_l, which implies that G_l is not a pseudorandom generator, which is a contradiciton to the hypothesis. Q.E.D.

Existence of pseudorandom generators

In complexity theory existence of pseudorandom generators is related to existence of one-way functions and hard-core predicate. Formally, pseudorandom generators exist if and only if one-way functions exist, or

PRG ↔ OWF

Definitions

One-way functions

Intuitively one-way functions are functions that are easy to compute and hard to invert. In other words the complexity (or circuit size) of the function is much smaller than one of its inverse. Formally: A function ƒ:  {0,1}ⁿ → {0,1}ⁿ is (S,ε) one-way if for any circuit C of size ≤ S,

Prob[ƒ(C(ƒ(x))) = ƒ(x)] ≤ ε .

Moreover, ƒ is a one-way function if

• ƒ can be computed in polynomial time
• ƒ is (poly(n), 1/poly(n)) one-way

Hard-core predicate

Function B: {0,1}ⁿ→{0,1} is a hard-core predicate for function ƒ if

• B can be computed
• for any polynomial size circuit C and any non-negligible ε = 1/poly(n), Prob_x~U [C(ƒ(x))=B(x)]≤1/2+ε

In other words it is hard to predict B(x) from function ƒ(x).

Proof

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

PRG → OWF

Consider a pseudorandom generator G_l: {0,1}^l → {0,1}^2l. Let's create the following one-way function ƒ:  {0,1}ⁿ → {0,1}ⁿ that uses the first half of the output of G_l as its output. Formally,

ƒ(x,y) → G_l(x)