Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions - Chandran, Nishanth; Garg, Sanjam (Progress in Cryptology - INDOCRYPT 2014 - 15th International Conference on Cryptology in India, New Delhi, India, December 14-17, 2014, Proceedings, 2014)
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 et al. that outputs n bits. That is, our PRF is not length preserving; however it outputs more bits than the PRF of Jain et al. when ϵ>12. We obtain our construction through the use of information-theoretic tools such as almostα-wise independent hash functions coupled with a novel proof strategy.