A pseudorandom generator from any one-way function

Authors
Hastad, J Impagliazzo, R Levin, LA Luby, M
Citation
J. Hastad et al., A pseudorandom generator from any one-way function, SIAM J COMP, 28(4), 1999, pp. 1364-1396
Citations number
47
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
28
Issue
4
Year of publication
1999
Pages
1364 - 1396
Database
ISI
SICI code
0097-5397(19990429)28:4<1364:APGFAO>2.0.ZU;2-V
Abstract
Pseudorandom generators are fundamental to many theoretical and applied asp ects of computing. We show how to construct a pseudorandom generator from a ny 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 ge nerator if and only if there is a one-way function.