Welcome to the resource topic for 2012/616
Title:
Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions
Authors: Nishanth Chandran, 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.
ePrint: https://eprint.iacr.org/2012/616
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .