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(logq) calls to the underlying PRG when q=2nϵ and ϵ12. 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 ϵ<12. In this work, we give constructions of PRFs that make only O(logq) calls to the underlying PRG when q=2nϵ, for 0<ϵ<1; our PRF outputs O(n2ϵ) bits (on every input), as opposed to the construction of Jain {\em et al.} that outputs bits. That is, our PRF is not length preserving; however it outputs more bits than the PRF of Jain {\em et al.} when . We obtain our construction through the use of information-theoretic tools such as {\em almost} -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},
      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.