1999•SIAM Journal on ComputingRequires access

A Pseudorandom Generator from any One-way Function

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby

Abstract

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.

About this research paper

What this paper is about

Why it matters

OpenAlex reports 1678 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Key concepts: Pseudorandom generator, Pseudorandom number generator, Pseudorandom generator theorem, Pseudorandom function family, Self-shrinking generator, Pseudorandomness, Random seed, Generator (circuit theory)