International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On Constructing Parallel Pseudorandom Generators from One-Way Functions

Authors:
Emanuele Viola
Download:
URL: http://eprint.iacr.org/2005/159
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12495,
  title={On Constructing Parallel Pseudorandom Generators from One-Way Functions},
  booktitle={IACR Eprint archive},
  keywords={foundations / Pseudorandom generator construction, one-way function, black-box, constant-depth circuit, hardness amplification, restriction, noise sensitivity},
  url={http://eprint.iacr.org/2005/159},
  note={To appear in  20th IEEE Conference on Computational Complexity. viola@eecs.harvard.edu 12936 received 2 Jun 2005},
  author={Emanuele Viola},
  year=2005
}