You are looking at a specific version 20121101:172718 of this paper. See the latest version.

Paper 2012/616

Hardness Preserving Constructions of Pseudorandom Functions, Revisited

Nishanth Chandran and Sanjam Garg

Abstract

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<\epsilon<\frac{1}{2}$. Our constructions present a tradeoff between the output length of the PRF and the level of hardness preserved. We obtain our construction through the use of {\em almost} $\alpha$-wise independent hash functions coupled with a novel proof strategy.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
nishanth @ cs ucla edu
History
2015-02-13: revised
2012-11-01: received
See all versions
Short URL
https://ia.cr/2012/616
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.