Author_Institution :
Div. of Eng. & Appl. Sci., Harvard Univ., Cambridge, MA, USA
Abstract :
We study pseudorandom generator (PRG) constructions Gf : {0, 1}l → {0, 1}1+s from one-way functions f : {0, 1}n → {0, 1}m. We consider PRG constructions of the form Gf (x) = C(f(q1) ...f (gpoly(n))) where C is a polynomial-size constant depth circuit (i.e., AC0) and C and the q´s are generated from x arbitrarily. We show that every black-box PRG construction of this form must have stretch s bounded as s ≤ 1 · (logO(1) n)/m + O(1) = o(l). This holds even if the PRG construction starts from a one-to-one function f : {0,1}n → {0, 1}m where m > 5n. This shows that either adaptive queries or sequential computation are necessary for black-box PRG constructions with constant factor stretch (i.e. s = Ω(l)) from one-way functions, even if the functions are one-to-one. On the positive side we show that if there is a one-way function f : {0, 1}n → {0, 1}m that is regular (i.e. the number of preimages of f(x) depends on |x| but not on x) and computable by polynomial-size constant depth circuits then there is a PRG : {0, 1}l → {0, 1}l + 1 computable by polynomial-size constant depth circuits. This complements our negative result above because one-to-one functions are regular. We also study constructions of average-case hard functions starting from worst-case hard ones, i.e. hardness amplifications. We show that if there is an oracle procedure Ampf in the polynomial time hierarchy (PH) such that Ampf is average-case hard for every worst-case hard f, then there is an average-case hard function in PH unconditionally. Bogdanov and Trevisan (FOGS ´03) and Viola (CCC´03) show related. but incomparable negative results.
Keywords :
circuit complexity; functions; random number generation; Ampf; adaptive queries; black-box PRG construction; hard function; hardness amplification; noise sensitivity; one-way functions; oracle procedure; parallel pseudorandom generators; polynomial size constant depth circuit; polynomial time hierarchy; restriction; sequential computation; AC generators; Books; Circuit noise; Complexity theory; Cryptography; Noise generators; Polynomials; Random variables; Pseudorandom generator construction; black-box; constant-depth circuit; hardness amplification; noise sensitivity; one-way function; restriction;