__
TR12-019 | 2nd March 2012 13:36
__

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

**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$).

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

{\em 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.

We also use a result by Applebaum, Ishai, and Kushilevitz (J.\ Comput.\ '06) to rule out simple ``hash-query-extract'' PRF

constructions, assuming the existence of OWF computable

in logarithmic space.