A pseudorandom generator from any one-way function
SIAM Journal on Computing, 1999•SIAM
Pseudorandom generators are fundamental to many theoretical and applied aspects of
computing. We show how to construct a pseudorandom generator from any one-way
function. Since it is easy to construct a one-way function from a pseudorandom generator,
this result shows that there is a pseudorandom generator if and only if there is a one-way
function.
computing. We show how to construct a pseudorandom generator from any one-way
function. Since it is easy to construct a one-way function from a pseudorandom generator,
this result shows that there is a pseudorandom generator if and only if there is a one-way
function.
Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator if and only if there is a one-way function.
Society for Industrial and Applied Mathematics