Pseudorandom generator theorem

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. |Prob x∈U  [C(x)=1] − Prob x∈D  [C(x)=1] | ≤ ε. 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 0 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 0 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 1 ,...,u i ,G l (s)) = 1 ] − Prob u, y [C' (u 1 ,>,...,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 1 ,...,u i ,G l (s)) = 1] - Prob y [C' (u 1 ,...,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 .

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 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). Prob[ƒ(C(ƒ(x,y)))  = ƒ(x,y)] > ε Then we can create the following algorithm that will distinguish G l from uniform, which contradicts the hypothesis.

The algorithm would take an input of 2n bits z and compute (x,y) = C(z). If G l (x) = 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/2 l , since the size of the pre-image is 1/2 l of the size of the image.

However, if z was drawn from the output of G l 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 G l is > ε − 1/2 l , which is non-negligible and thus contradicts our assumption of G l being a pseudorandom generator. Q.E.D. G l : {0,1} l →{0,1} l+1   =  ƒ(x).B(x), 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. Assume that G l is not a pseudorandom generator; that is, there exists circuit C of polynomial size that distinguishes G l (x) =ƒ(x).B(x) from U l+1 with advantage ≥ε, where ε is non-negligible.

Note, that since ƒ(x) is a permutation, then if x is drawn from uniform distribution, then so if ƒ(x). Therefore, U l+1 is equivalent to ƒ(x).b, where b is a bit drawn independently from a uniform distribution. Formally, Prob x~U  [C(G(x))=1] − Prob x~U,b~U  [C(x.b)=1]  ≥ ε Let's construct the following algorithm C: 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 Given the output of ƒ the algorithm first guesses bit b by tossing a random coin, i.e. Prob[b=0] = Prob[b=1] = 0.5.

Then, algorithm (circuit) C is run on f(x).b and if the result is 1 then b is outputted, otherwise the inverse of b is returned. Then probability of C guessing B(x) correctly is: Prob x~U  [C(z)=B(x)] = Prob[b=B(x) ∧ C(z.b)=1] + Prob[b≠B(x) ∧ C(z.b)=0] = Prob[b=B(x)]⋅Prob[C(z.b)=1 | b=B(x)] + Prob[b≠B(x)]⋅Prob[C(z.b)=0 | b≠B(x)] = 1/2⋅Prob[C(z.b)=1 | b=B(x)] + 1/2⋅Prob[C(z.b)=0 | b≠B(x)] = (1−1/2)⋅Prob[C(z.b)=1 | b=B(x)] + 1/2⋅(1−Prob[C(z.b)=1 | b≠B(x)]) = 1/2+Prob z.b~G(x)  [C(z.b)=1] − 1/2⋅(Prob[C(z.b)=1 | b=B(x)]+Prob[C(z.b)=1 | b≠B(x)]) = 1/2+Prob z.b~G(x)  [C(z.b)=1] − Prob z.b~U  [C(z.b)=1] ≥ 1/2+ε This implies that circuit C can predict B(x) 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. If ƒ{0,1} n →{0,1} n is a one-way permutation, then so is ƒ'{0,1} 2n →{0,1} 2n , where ƒ'(x,y)=ƒ(x).y by definition. Then B(x,y)=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 Prob x,y [C(ƒ(x),y)=x⋅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(1/ε 2 ) candidates that include all valid x. Thus, an algorithm can invert ƒ(x) in polynomial time for a non-negligible fraction of x, which contradicts the hypothesis.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1321176442 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001321176442 · captured 1762654699.0 · version history

Cite this page as: encyclopegia.org, “Pseudorandom generator theorem”, snapshot enwiki-001321176442. https://encyclopegia.org/a/pseudorandom-generator-theorem

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.