Aris Tentes
New York University

Hardness Preserving Constructions of Pseudorandom Functions

We show a hardness-preserving construction of a PRF from any length
doubling PRG which improves upon known constructions whenever we can
put a non-trivial upper bound $q$ on the number of queries to the PRF.
Our construction requires only $O(\log q)$ invocations to the
underlying PRG with each query. In comparision, the number of
invocations by the best previous hardness-preserving construction (GGM
using Levin's trick) is logarithmic in the \emph{hardness} of the PRG.
For example, starting from an exponentially secure PRG
$\set{0,1}^n\mapsto \set{0,1}^{2n}$, we get a PRF which is
exponentially secure if queried at most $q=\exp(\sqrt n)$ times and
where each invocation of the PRF requires $\Theta(\sqrt n)$ queries to
the underlying PRG. This is much less than the $\Theta(n)$ required by
known constructions.

Joint work with: Abhishek Jain and Krzysztof Pietrzak