Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Proceedings of the 2012 Cryptographers' Track of the RSA Conference (CT-RSA '12)
Keywords
Pseudorandom generatorhash functioncollision-resistanceprovable security.
Contact author(s)
virendra @ gatech edu
History
2012-02-06: received
Short URL
https://ia.cr/2012/056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/056,
      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{https://eprint.iacr.org/2012/056}},
      url = {https://eprint.iacr.org/2012/056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.