Pseudorandom Generators: Theoretical Framework and Applications

Pseudorandom Generators Oded Goldreich Weizmann Institute of Science For Leonid Levin s 75.6thB-day

A general paradigm/framework (PRG Gs) Stretching: k-bit seeds are stretched to l(k)-bit sequences, where l(k)>k. Versions: how big is l(k)? (e.g., polynomial, exponential) Computational indistinguishability. Versions: the class of possible distinguishers (e.g., all PPT, all linear-size circuits, space-bounded, local tests, linear tests, etc). Complexity of generation (i.e., performing the stretching). Versions: polynomial-time (i.e., polynomial in seed length), polynomial in the output length time.

The general-purpose version Stretching: l is an arbitrary polynomial (s.t. l(k)>k). Computational indistinguishability by every PPT. That is, for every PPT algorithm A, Pr[A(G(Uk))=1] = Pr[A(Ul(k))=1] (k) where is a negligible function (i.e., smaller than any 1/poly). Complexity of generation: polynomial-time (i.e., polynomial in seed length). N.B.: The distinguisher is more powerful than the generator. Hardness vs Randomness Paradigm THM [HILL]: One-way functions imply the existence of such PRGs. In fact, OWF exist if and only if such PRGs exist, and for any polynomial stretch.

The HILL Construction, revisited (again and again and again, now by Mazor and Pass) A notion of adaptive / quantitative next-bit unpredictability: The (average) number of bits that are hard to predict in a string selected according to the distribution in question. Key: For a OWF f, the function g(M,x) =(Mf(x) , Mx) has |x|+log(|x|) unpredictable bits, whereas |g(M,x)|=2|x|. (Locations unknown.) Randomized shift: For r [2n], let g (r,M,x(1), ,x(n)) = g(M,x(1))[r+1,2n]g(M,x(2)) g(M,x(n-1)) g(M,x(n))[r]of length n =2n2-2n. Each bit location is unpredictable w.p. (n (n+log n) n)/n = + (log n)/2n. Extraction from copies: Gi(r,s,M,X) = Es(g (r,M,X[1])i g (r,M,X[n2])i) has length (0.5+(log n)/2n) n2and is pseudorandom, where X[j] has length n2, i [n ] and g ()iis the ithbit of g (). Concl.: G(r,s1 sn ,M,X) = (r,s1 sn ,M,G1(r,s1,M,X) Gn (r,sn ,M,X)) is a PRG.

HILL according to Mazor and Pass: Step 1 (using G. & Levin) A notion of adaptive / quantitative next-bit unpredictability: The (average) number of bits that are hard to predict in a string selected according to the distribution in question. For a OWF f, the function g(M,x) =(Mf(x) , Mx) has |x|+log(|x|) unpredictable bits, whereas |g(M,x)|=2|x|. (Locations unknown.) The argument extends to the general case. Hint: piece-wise analysis. Assume f is r-regular, with r = (log n). The first n-r-O(log n) (resp., r-O(log n)) bits of Mf(X) (resp., Mx) are unpredictable. For each location i [r-O(log n),r+O(log n)] in Mx, consider predicting B(M,x)=(Mx)iwhen given F(M,x)=(M,f(x),(Mx)[i-1]) G+Levin: An advantage of in predicting B(M,x) yields retrieving x w.p. poly( ), whereas this is infeasible (since there are 2rpossible choices for x given f(x), whereas (Mx)[i-1]can be replaced by a random string that equals it w.p. 2-(i-1)= 2-r poly(n/ )).

HILL according to Mazor and Pass: Steps 2-4 A notion of adaptive / quantitative next-bit unpredictability: The (average) number of bits that are hard to predict in a string selected according to the distribution in question. g(M,x) =(Mf(x) , Mx) has |x|+log(|x|) unpredictable bits, whereas |g(M,x)|=2|x|. (Locations unknown.) Randomized shift: For r [2n], let g (r,M,x(1), ,x(n)) = g(M,x(1))[r+1,2n]g(M,x(2)) g(M,x(n-1)) g(M,x(n))[r]of length n =2n2-2n. Each bit location is unpredictable w.p. (n (n+log n) n)/n = + (log n)/2n. Extraction from copies: Gi(r,s,M,X) = Es(g (r,M,X[1])i g (r,M,X[n2])i) has length (0.5+(log n)/2n) n2and is pseudorandom, where X[j] has length n2, i [n ] and g ()iis the ithbit of g (). G(r,s1 sn ,M,X) = (r,s1 sn ,M,G1(r,s1,M,X) Gn (r,sn ,M,X)) is a PRG.

The canonical-derandomizers (for BPP) version Stretching: l is arbitrary up to exponential (s.t. l(k)>k). Computational indistinguishability by any linear-sized circuit. That is, for every linear-sized family of Boolean circuit Ck Pr[Ck(G(Uk))=1] = Pr[Ck(Ul(k))=1] 0.1. (Any constant smaller than 1/6 (i.e., half the decision gap of BPP).) Complexity of generation: exponential-time (since we incur such a slowdown in scanning all seeds). N.B.: The generator is more powerful than the distinguisher. THM [NW, IW]: If E does not have exp(0.001n)-sized circuits, then BPP=P (by using such canonical derandomizers).

Other canonical-derandomizers (e.g. for AC0 and AM) Stretching: l is arbitrary up to exponential (s.t. l(k)>k). Computational indistinguishability by any constant-depth polynomial-sized circuit (resp., circuits with SAT gates ). Complexity of generation: exponential-time. Using known hardness results THM [N]: The acceptance probability of AC0 circuits can be approximated in deterministic quasi-polynomial-time. THM [KvM]: If NE coNE does not have exp(0.001n)-sized circuits with SAT-gates, then AM=NP.

Fooling space-bounded distinguishers Stretching: l is arbitrary up to exponential (s.t. l(k)>k). Computational indistinguishability by any s(k)-space algorithm (or rather fixed-ordered ROBP of width 2s(k)). Distinguishing gap varies (between 0.1 and 2- (s(k))). Complexity of generation: linear-space (for derandom n). N.B.: The generator is more powerful than the distinguisher. THM [N]: BPL is in SC (i.e., poly-log space and poly-time), by using a PRG for space s(k)= (k1/2) and l(k)=2s(k). THM [NZ]: a PRG for space s(k)= (k) and l(k)=poly(k). For poly-time lin-space computation, lin randomness suffices. s(k) = O(log n) k = O(log n)2 s(k) = O(log n) k = O(log n)

Fooling more restricted distinguishers Stretching: l is arbitrary up to exponential (s.t. l(k)>k). Computational indistinguishability by * local tests (i.e., t-wise independence); * linear (over GF(2)) tests (i.e., small biased); * approximate counters of block hits . Complexity of generation varies. THM [CG,ABI]: t-wise independent n-bit seq., with k=t log n. THM [NN]: -biased n-bit seq., with k=O(log(n/ )). THM [AKS]: t-step walks on 2n-vertex expander (i.e., k=n+O(t)) hit a vertex set of density with probability 1-exp(- (t)).

A general paradigm/framework, recap Stretching: k-bit seeds are stretched to l(k)-bit sequences, where l(k)>k. Versions: how big is l(k)? (e.g., polynomial, exponential) Computational indistinguishability. Versions: a class of possible distinguishers (e.g., all PPT, all linear-size circuits, space-bounded, local tests, linear tests, etc). Complexity of generation (i.e., performing the stretching). Versions: polynomial-time (i.e., polynomial in seed length), polynomial in the output length time, more...