Paper 2012/056

A New Pseudorandom Generator from Collision-Resistant Hash Functions

Alexandra Boldyreva and Virendra Kumar


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.

Available format(s)
Publication info
Published elsewhere. Proceedings of the 2012 Cryptographers' Track of the RSA Conference (CT-RSA '12)
Pseudorandom generatorhash functioncollision-resistanceprovable security.
Contact author(s)
virendra @ gatech edu
2012-02-06: received
Short URL
Creative Commons Attribution


      author = {Alexandra Boldyreva and Virendra Kumar},
      title = {A New Pseudorandom Generator from Collision-Resistant Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/056},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.