Paper 2005/159
On Constructing Parallel Pseudorandom Generators from OneWay Functions
Emanuele Viola
Abstract
We study pseudorandom generator (PRG) constructions G^f : {0,1}^l > {0,1}^{l+s} from oneway 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 polynomialsize constant depth circuit (i.e. AC^0) and C and the q's are generated from x arbitrarily. We show that every blackbox 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 onetoone function f : {0,1}^n \to {0,1}^m where m < 5n. This shows that either adaptive queries or sequential computation are necessary for blackbox PRG constructions with constant factor stretch (i.e. s = \Omega(l)) from oneway functions, even if the functions are onetoone. On the positive side we show that if there is a oneway 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 polynomialsize constant depth circuits then there is a PRG : {0,1}^l \to {0,1}^{l+1} computable by polynomialsize constant depth circuits. This complements our negative result above because onetoone functions are regular. We also study constructions of averagecase hard functions starting from worstcase 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 averagecase hard for every worstcase hard f, then there is an averagecase 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 constructiononeway functionblackboxconstantdepth circuithardness amplificationrestrictionnoise sensitivity
 Contact author(s)
 viola @ eecs harvard edu
 History
 20050604: received
 Short URL
 https://ia.cr/2005/159
 License

CC BY
BibTeX
@misc{cryptoeprint:2005/159, author = {Emanuele Viola}, title = {On Constructing Parallel Pseudorandom Generators from OneWay 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} }