Pseudorandom generators based on regular one-way functions
Webpage for a paper by Goldreich, Krawczyk and Luby
Original Abstract
Pseudorandom generators
(suggested and developed by Blum and Micali and Yao)
are efficient deterministic programs that expand a randomly
selected k-bit seed into a much longer pseudorandom bit sequence that is
indistinguishable in polynomial time from an (equally long) sequence
of unbiased coin tosses.
A fundamental question is to find simple conditions,
as the existence of one-way functions,
which suffice for constructing pseudorandom generators.
This paper consider regular functions, in which every image of a k-bit
string has the same number of preimages of length k.
This paper shows how to construct
pseudorandom generators from any regular one-way function.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.