Paper Info
Title
A new pseudorandom generator from collision-resistant hash functions
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 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 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.
Year
DOI
Venue
2012
10.1007/978-3-642-27954-6_12
IACR Cryptology ePrint Archive
Keywords
DocType
Volume
hash function,underlying hash function,equal size,new pairwise-independent function,new pseudorandom generator,collision-resistant hash function,worst-case regularity,regular one-way function,common regularity assumption,latest prg,regularity assumption,pairwise-independent function
Conference
2012
ISSN
Citations 
PageRank 
0302-9743
3
0.41
References 
Authors
20
2
Name
Order
Citations
PageRank
Alexandra Boldyreva12297114.80
Virendra Kumar2110.91