Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Håstad et al. (1999) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: