A New Pseudorandom Generator From Collision-Resistant Hash Functions
The authors present a new hash-function-based Pseudo-Random Generator (PRG). Their 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. Their construction does not use pairwise-independent functions and is thus more efficient, requiring less computation and a significantly shorter seed.