On the Complexity of Constructing Pseudorandom Functions (Especially when They Dont Exist)
We study the complexity of black-box constructions of pseudorandom functions (PRFs) from one-way functions (OWFs) that are secure against non-uniform adversaries. We show that if OWFs 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)=?(1) (e.g., k(n)=log? n). Combining this with the fact that OWFs imply PRFs, we show that unconditionally there exists a (pathological) construction of a 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 PRFs from OWFs. Our result builds on the work of Reingold, Trevisan, and Vadhan (TCC04), who show that when OWFs 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 NisanWigderson generator (JCSS94), and with a recent technique by Berman and Haitner (TCC12).
pseudorandom functions black-box reductions adaptivity