Cryptology ePrint Archive: Report 2016/343

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

Eric Miles and Emanuele Viola

Abstract: 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.

Category / Keywords: foundations /

Original Publication (in the same form): IACR-JOC-2015

Date: received 30 Mar 2016, last revised 30 Mar 2016

Contact author: enmiles at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20160331:074353 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]