International Association
for Cryptologic Research

We revisit hardness-preserving constructions of a PRF from any length doubling PRG when there is a non-trivial upper bound $q$ on the number of queries that the adversary can make to the PRF. Very recently, Jain, Pietrzak, and Tentes (TCC 2012) gave a hardness-preserving construction of a PRF that makes only $O(\\log q)$ calls to the underlying PRG when $q = 2^{n^\\epsilon}$ and $\\epsilon \\geq \\frac{1}{2}$. This dramatically improves upon the efficiency of the GGM construction. However, they explicitly left open the question of whether such constructions exist when $\\epsilon < \\frac{1}{2}$. In this work, we make progress towards answering this question. In particular we give constructions of PRFs that make only $O(\\log q)$ calls to the underlying PRG even when $q = 2^{n^\\epsilon}$, for $0