Paper 2005/159

On Constructing Parallel Pseudorandom Generators from One-Way Functions

Emanuele Viola


We study pseudorandom generator (PRG) constructions G^f : {0,1}^l -> {0,1}^{l+s} from one-way functions f : {0,1}^n \to {0,1}^m. We consider PRG constructions of the form G^f(x) = C(f(q_{1}) ... f(q_{poly(n)})) where C is a polynomial-size constant depth circuit (i.e. AC^0) 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 < l ( log^{O(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 \to {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 = \Omega(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 \to {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 \to {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 Amp^f in the polynomial time hierarchy (PH) such that Amp^f is average-case hard for every worst-case hard f, then there is an average-case hard function in PH \emph{unconditionally}. Bogdanov and Trevisan (FOCS '03) and Viola (CCC'03) show related but incomparable negative results.

Available format(s)
Publication info
Published elsewhere. To appear in 20th IEEE Conference on Computational Complexity.
Pseudorandom generator constructionone-way functionblack-boxconstant-depth circuithardness amplificationrestrictionnoise sensitivity
Contact author(s)
viola @ eecs harvard edu
2005-06-04: received
Short URL
Creative Commons Attribution


      author = {Emanuele Viola},
      title = {On Constructing Parallel Pseudorandom Generators from One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2005/159},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.