A Pseudorandom Generator from any One-way Function

Abstract

Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any oneway function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator iff there is a one-way function. Warning: Essentially this paper has been published in SIAM Journal on Computing and is hence subject to copyright restrictions. It is for personal use only. 1 Introduction One of the basic primitives in the study of the interaction between randomness and feasible computation is a pseudorandom generator. Intuitively, a pseudorandom generator is a Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden, email Johanh@nada.kth.se. Research supported by the Swedish National Board for Technical Development. y Department of Computer Science, University of California at San Diego. Research partially done wh...