Paper 2016/343

On the complexity of constructing pseudorandom functions (especially when they don't exist)

Eric Miles and Emanuele Viola


We study the complexity of black-box constructions of pseudorandom functions (PRF) from one-way functions (OWF) that are secure against non-uniform adversaries. We show that if OWF do not exist, then given as an oracle any (inefficient) hard-to-invert function, one can compute a PRF in polynomial time with only k(n) oracle queries, for any k(n) = \omega(1) (e.g. k(n) = log^* n). Combining this with the fact that OWF imply PRF, we show that unconditionally there exists a (pathological) construction of PRF from OWF making at most k(n) queries. This result shows a limitation of a certain class of techniques for proving efficiency lower bounds on the construction of PRF from OWF. Our result builds on the work of Reingold, Trevisan, and Vadhan (TCC ’04), who show that when OWF do not exist there is a pseudorandom generator (PRG) construction that makes only one oracle query to the hard-to-invert function. Our proof combines theirs with the Nisan-Wigderson generator (JCSS ’94), and with a recent technique by Berman and Haitner (TCC ’12). Working in the same context (i.e. when OWF do not exist), we also construct a poly-time PRG with arbitrary polynomial stretch that makes non-adaptive queries to an (inefficient) one-bit-stretch oracle PRG. This contrasts with the well-known adaptive stretch-increasing construction due to Goldreich and Micali. Both above constructions simply apply an affine function (parity or its complement) to the query answers. We complement this by showing that if the post-processing is restricted to only taking projections then non-adaptive constructions of PRF, or even linear-stretch PRG, can be ruled out.

Available format(s)
Publication info
Published by the IACR in JOC 2015
Contact author(s)
enmiles @ cs ucla edu
2016-03-31: received
Short URL
Creative Commons Attribution


      author = {Eric Miles and Emanuele Viola},
      title = {On the complexity of constructing pseudorandom functions (especially when they don't exist)},
      howpublished = {Cryptology ePrint Archive, Paper 2016/343},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.