Pseudorandom generator theorem

In computational complexity 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" &rarr; {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" &rarr; {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" &rarr; {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:

Let's consider "m+1" intermediate distributions "H_i: 0 &le; i &le; 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 "&epsilon;" = 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 "&epsilon; / m". Note, that since "m" are polynomial in "l", then "&epsilon; / 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 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.

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] &ge; "&epsilon; / 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] | ] &ge; "&epsilon; / 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".

Existence of pseudorandom generators

In complexity theory, 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 &harr; 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 that of its inverse. Formally: A function &fnof;: {0,1}^"n" &rarr; {0,1}^"n" is ("S","&epsilon;") "one-way" if for any circuit "C" of size &le; "S",

Prob [&fnof;("C"(&fnof;("x"))) = &fnof;("x")] &le; "&epsilon;".

Moreover, &fnof; is a "one-way function" if
* &fnof; can be computed in polynomial time
* &fnof; is ("poly"("n"), 1/"poly"("n")) one-way

Hard-core predicate

Function "B": {0,1}^"n" &rarr; {0,1} is a hard-core predicate for function &fnof; if
* "B" can be computed
* for any polynomial size circuit "C" and any non-negligible "&epsilon;" = 1/"poly"("n"), Prob"_x~U " ["C"(&fnof;("x")) = "B"("x")] &le; 1/2+"&epsilon;"

In other words it is hard to predict "B"("x") from function &fnof;("x").

Proof

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

PRG &rarr; OWF

Consider a pseudorandom generator "G_l": {0,1}^"l" &rarr; {0,1}^"2l". Let's create the following one-way function &fnof;: {0,1}^"n" &rarr; {0,1}^"n" that uses the first half of the output of "G_l" as its output. Formally,

&fnof;("x","y") &rarr; "G_l"("x")

A key observation that justifies such selection, is that the image of the function is of size 2^"n" and is a negligible fraction of the pre-image universe of size 2^"2n".

To prove that &fnof; is indeed a one-way function let's construct an argument by contradiction. Assume there exists a circuit "C" that inverts &fnof; with advantage "&epsilon;":

Prob [&fnof;("C"(&fnof;("x","y"))) = &fnof;("x","y")] > "&epsilon;"

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 &le; 1/2^"l", since the size of image is 1/2^"l" of the size of the pre-image. However, if "z" was drawn from the output of "G_l" then the probability of acceptance is > "&epsilon;" 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 > "&epsilon;" − 1/2, which is non-negligible and thus contradicts our assumption of "G_l" being a pseudorandom generator. Q.E.D.

OWF &rarr; PRG

For this case we prove a "weaker" version of the theorem:

One-way permutation &rarr; 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 &fnof; as follows:

"G_l": {0,1}^"l"&rarr;{0,1}^"l"+1 = &fnof;("x")."B"("x"), where "B" is hard-core predicate of &fnof; 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 &rarr; PRG

First, let's show that if "B" is a hard-core predicate for &fnof; then "G_l" is indeed pseudorandom. Again, we'll use an argument by contradiction.

Assume that "G_l" is not a pseudorandom generator; that is, there exists circuit "C" of polynomial size that distinguishes "G_l"("x") =&fnof;("x")."B"("x") from "U_l+1" with advantage &ge;"&epsilon;", where "&epsilon;" is non-negligible. Note, that since &fnof;("x") is a permutation, then if "x" is drawn from uniform distribution, then so if &fnof;("x"). Therefore, "U_l+1" is equivalent to &fnof;("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] &ge; "&epsilon;"

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 &fnof; 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") &and; "C"("z.b")=1] +Prob ["b"&ne;"B"("x") &and; "C"("z.b")=0] =

Prob ["b"="B"("x")] &sdot;Prob ["C"("z.b")=1 | "b"="B"("x")] +Prob ["b"&ne;"B"("x")] &sdot;Prob ["C"("z.b")=0 | "b"&ne;"B"("x")] =

1/2&sdot;Prob ["C"("z.b")=1 | "b"="B"("x")] +1/2&sdot;Prob ["C"("z.b")=0 | "b"&ne;"B"("x")] =

(1−1/2)&sdot;Prob ["C"("z.b")=1 | "b"="B"("x")] +1/2&sdot;(1−Prob ["C"("z.b")=1 | "b"&ne;"B"("x")] ) =

1/2+Prob_"z.b~G(x)" ["C"("z.b")=1] −1/2&sdot;(Prob ["C"("z.b")=1 | "b"="B"("x")] +Prob ["C"("z.b")=1 | "b"&ne;"B"("x")] ) =

1/2+Prob_"z.b~G(x)" ["C"("z.b")=1] −Prob_"z.b~U" ["C"("z.b")=1] &ge; 1/2+"&epsilon;"

This implies that circuit "C"' can predict "B"("x") with probability more than 1/2 + "&epsilon;", which means that "B" cannot be a hard-core predicate for &fnof; and the hypothesis is contradicted. Q.E.D.

OWP &rarr; hard-core predicate

The outline of the proof is as follows:

If &fnof;{0,1}^"n"&rarr;{0,1}^"n" is a one-way permutation, then so is &fnof;'{0,1}^"2n"&rarr;{0,1}^"2n", where &fnof;'("x","y")=&fnof;("x")."y" by definition. Then "B"("x","y")="x"&sdot;"y" is a hard-core predicate for &fnof;', where "&sdot;" 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 &fnof; 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"(&fnof;("x"),"y")="x"&sdot;"y"] &ge; 1/2+"&epsilon;". 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/"&epsilon"²) candidates that include all valid "x". Thus, an algorithm can invert &fnof;("x") in polynomial time for a non-negligible fraction of "x", which contradicts the hypothesis.

References

* W. Diffie, M.E. Hellman. "New Directions in Cryptography." "IEEE Transactions on Information Theory", IT-22, pp.644-654, 1976.
* A.C. Yao. "Theory and Application of Trapdoor Functions." "23rd IEEE Symposium on Foundations of Computer Science", pp.80-91, 1982.
* M. Blum and S. Micali "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits." "SIAM Journal on Computing", v13, pp.850-864, 1984.
* J. Hastad, R. Impagliazzo, L.A. Levin and M. Luby. "A Pseudorandom Generator from any One-way Function." "SIAM Journal on Computing", v28 n4, pp.-1364-1396, 1999.