Pseudorandom generator theorem
In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through a number of theorems, collectively referred to as the pseudorandom generator theorem.
Introduction
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 Dn is pseudorandom if for any polynomial size circuit C, and any ε inversely polynomial in nPseudorandom generators
A function Gl: l → m, where l < m is a pseudorandom generator if:- Gl can be computed in time polynomial in l
- Gl is pseudorandom, when x is uniformly random.
One additional pseudorandom bit implies polynomially more pseudorandom bits
The idea of the proof is as follows: first s bits from uniform distribution Ul are picked and used as the seed to the first instance of Gl, which is known to be a pseudorandom generator. Next, the output of the first instance of Gl is divided into two parts: first l bits are fed into the second instance of Gl 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 Gl, is indeed a pseudorandom generator by using a hybrid approach and proof by contradiction as follows:
Consider m+1 intermediate distributions Hi: 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, H0 is the full output of G'l and Hm is a true uniform distribution Um. Therefore, distributions Hi and Hi+1 will be different in only one bit.
Now, assume that G'l is not a pseudorandom distribution; that is, there exists some circuit C that can distinguish between G'l and Um with an advantage ε = 1/poly. In other words, this circuit can distinguish between H0 and Hm. Therefore, there exists such i that the circuit C can distinguish between Hi and Hi+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 Gl or a drawn from uniform distribution. Let's reuse the approach of building large pseudorandom generators out of instances of Gl 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 Hi or Hi+1, since the i+1 bit is either drawn from uniform or from Gl. Since by assumption we can distinguish between Hi and Hi+1 with non-negligible advantage, then we can distinguish between U and Gl, which implies that Gl 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 Gl and Ul+1 does not have to toss random coins. As we showed above, if exists a circuit C for distinguishing between G'l and Um, where m = poly, then exists a circuit C' for distinguishing between Gl and Ul+1 that uses i random bits. For this circuit C' :
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,
Probu - Proby | ] ≥ ε / 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 Gl and Ul+1.
Existence of pseudorandom generators
The existence of pseudorandom generators is related to the existence of one-way functions and hard-core predicates. 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 of the function is much smaller than that of its inverse. Formally: A function ƒ: n → n is one-way if for any circuit C of size ≤ S,Prob ≤ ε
.
Moreover, ƒ is a one-way function if
- ƒ can be computed in polynomial time
- ƒ is, 1/poly) one-way
Hard-core predicate
- B can be computed in polynomial time
- for any polynomial size circuit C and any non-negligible ε = 1/poly, Probx~U ≤ 1/2+ε
Proof
Here an outline of the proof is given. Please see references for detailed proofs.PRG → OWF
Consider a pseudorandom generator Gl: l → 2l. Let's create the following one-way function ƒ: n → n that uses the first half of the output of Gl as its output. Formally,ƒ → Gl
A key observation that justifies such selection, is that the image of the function is of size 2n and is a negligible fraction of the pre-image universe of size 22n.
To prove that ƒ is indeed a one-way function let's construct an argument by contradiction. Assume there exists a circuit C that inverts ƒ with advantage ε:
Prob > ε
Then we can create the following algorithm that will distinguish Gl from uniform, which contradicts the hypothesis. The algorithm would take an input of 2n bits z and compute = C. If Gl = z the algorithm would accept, otherwise it rejects.
Now, if z is drawn from uniform distribution, the probability that the above algorithm accepts is ≤ 1/2l, since the size of image is 1/2l of the size of the pre-image. However, if z was drawn from the output of Gl then the probability of acceptance is > ε by assumption of the existence of circuit C. Therefore, the advantage that circuit C has in distinguishing between the uniform U and output of Gl is > ε − 1/2l, which is non-negligible and thus contradicts our assumption of Gl being a pseudorandom generator. Q.E.D.
OWF → PRG
For this case we prove a weaker version of the theorem:One-way permutation → pseudorandom generator
A one-way permutation is a one-way function that is also a permutation of the input bits. A pseudorandom generator can be constructed from one-way permutation ƒ as follows:
Gl: l→l+1 = ƒ.B, where B is hard-core predicate of ƒ and "." is a concatenation operator. Note, that by the theorem proven above, it is only needed to show the existence of a generator that adds just one pseudorandom bit.
Hard-core predicate → PRG
First, let's show that if B is a hard-core predicate for ƒ then Gl is indeed pseudorandom. Again, we'll use an argument by contradiction.Assume that Gl is not a pseudorandom generator; that is, there exists circuit C of polynomial size that distinguishes Gl =ƒ.B from Ul+1 with advantage ≥ε, where ε is non-negligible. Note, that since ƒ is a permutation, then if x is drawn from uniform distribution, then so if ƒ. Therefore, Ul+1 is equivalent to ƒ.b, where b is a bit drawn independently from a uniform distribution. Formally,
Probx~U − Probx~U,b~U ≥ ε
Let's construct the following algorithm C:
1. Given z=f guess bit b
2. Run C on z.b
3. IF C=1
4. output b
5. ELSE
6. output 1-b
Given the output of ƒ the algorithm first guesses bit b by tossing a random coin, i.e. Prob = Prob = 0.5. Then, algorithm C is run on f.b and if the result is 1 then b is outputted, otherwise the inverse of b is returned.
Then probability of C guessing B correctly is:
Probx~U =
Prob +
Prob =
Prob⋅Prob +
Prob⋅Prob =
1/2⋅Prob +
1/2⋅Prob =
⋅Prob +
1/2⋅=1 | b≠B =
1/2+Probz.b~G −
1/2⋅=1 | b=B]+Prob −
Probz.b~U ≥ 1/2+ε
This implies that circuit C' can predict B with probability more than 1/2 + ε, which means that B cannot be a hard-core predicate for ƒ and the hypothesis is contradicted. Q.E.D.
OWP → hard-core predicate
The outline of the proof is as follows:If ƒn→n is a one-way permutation, then so is ƒ'2n→2n, where ƒ'=ƒ.y by definition. Then B=x⋅y is a hard-core predicate for ƒ', where ⋅ is a vector dot product. To prove that it is indeed hard-core let's assume otherwise, and show a contradiction with the hypothesis of ƒ being one-way. If B is not a hard-core predicate, then there exists a circuit C that predicts it, so
Probx,y ≥
1/2+ε. That fact can be used to recover x by cleverly constructing permutations y that isolate bits in x. In fact, for a constant fraction of x, there exists a polynomial time algorithm that lists O candidates that include all valid x. Thus, an algorithm can invert ƒ in polynomial time for a non-negligible fraction of x, which contradicts the hypothesis.