Cryptology ePrint Archive: Report 2012/056

A New Pseudorandom Generator from Collision-Resistant Hash Functions

Alexandra Boldyreva and Virendra Kumar

Abstract: We present a new hash-function-based pseudorandom generator (PRG). Our PRG is reminiscent of the classical constructions iterating a function on a random seed and extracting Goldreich-Levin hardcore bits at each iteration step. The latest PRG of this type that relies on reasonable assumptions (regularity and one-wayness) is due to Haitner et al. In addition to a regular one-way function, each iteration in their ``randomized iterate'' scheme uses a new pairwise-independent function, whose descriptions are part of the seed of the PRG. Our construction does not use pairwise-independent functions and is thus more efficient, requiring less computation and a significantly shorter seed. Our scheme's security relies on the standard notions of collision-resistance and regularity of the underlying hash function, where the collision-resistance is required to be {\em exponential}. In particular, any polynomial-time adversary should have less than $2^{-n/2}$ probability of finding collisions, where $n$ is the output size of the hash function. We later show how to relax the regularity assumption by introducing a new notion that we call {\em worst-case regularity}, which lower bounds the size of primages of different elements from the range (while the common regularity assumption requires all such sets to be of equal size). Unlike previous results, we provide a concrete security statement.

Category / Keywords: foundations / Pseudorandom generator, hash function, collision-resistance, provable security.

Publication Info: Proceedings of the 2012 Cryptographers' Track of the RSA Conference (CT-RSA '12)

Date: received 6 Feb 2012

Contact author: virendra at gatech edu

Available format(s): PDF | BibTeX Citation

Version: 20120206:214313 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]