Paper 2012/616

Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions

Nishanth Chandran and Sanjam Garg

Abstract

We revisit hardness-preserving constructions of a pseudo-random function (PRF) from any length doubling pseudo-random generator (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 construction of Goldreich, Goldwasser, and Micali (FOCS 1984). However, they explicitly left open the question of whether such constructions exist when $\epsilon < \frac{1}{2}$. In this work, we give constructions of PRFs that make only $O(\log q)$ calls to the underlying PRG when $q = 2^{n^\epsilon}$, for $0<\epsilon<1$; our PRF outputs $O(n^{2\epsilon})$ bits (on every input), as opposed to the construction of Jain {\em et al.} that outputs $n$ bits. That is, our PRF is not length preserving; however it outputs more bits than the PRF of Jain {\em et al.} when $\epsilon>\frac{1}{2}$. We obtain our construction through the use of information-theoretic tools such as {\em almost} $\alpha$-wise independent hash functions coupled with a novel proof strategy.

Note: Fixed citations and typos.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Indocrypt 2014
Keywords
pseudorandom functionshardness preservationpseudorandom generators
Contact author(s)
nishanth @ cs ucla edu
sanjamg @ berkeley 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

BibTeX

@misc{cryptoeprint:2012/616,
      author = {Nishanth Chandran and Sanjam Garg},
      title = {Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/616},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/616}},
      url = {https://eprint.iacr.org/2012/616}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.