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.