SPEAKER: Aris Tentes New York University TITLE: Hardness Preserving Constructions of Pseudorandom Functions ABSTRACT: 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