Paper 2005/159

On Constructing Parallel Pseudorandom Generators from One-Way Functions

Emanuele Viola

Abstract

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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. To appear in 20th IEEE Conference on Computational Complexity.
Keywords
Pseudorandom generator constructionone-way functionblack-boxconstant-depth circuithardness amplificationrestrictionnoise sensitivity
Contact author(s)
viola @ eecs harvard edu
History
2005-06-04: received
Short URL
https://ia.cr/2005/159
License
Creative Commons Attribution
CC BY

BibTeX

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