A Pseudorandom Generator from Any One-Way Function. H˚astad, J., Impagliazzo, R., Levin, L. A., & Luby, M. 28(4):1364–1396.
A Pseudorandom Generator from Any One-Way Function [link]Paper  doi  abstract   bibtex   
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.
@article{hastadPseudorandomGeneratorAny1999,
  title = {A Pseudorandom Generator from Any One-Way Function},
  author = {H˚astad, Johan and Impagliazzo, Russell and Levin, Leonid A. and Luby, Michael},
  date = {1999-01},
  journaltitle = {SIAM Journal on Computing},
  volume = {28},
  pages = {1364--1396},
  issn = {0097-5397},
  doi = {10.1137/s0097539793244708},
  url = {https://doi.org/10.1137/s0097539793244708},
  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.},
  keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-11514702,computational-science,mathematics,monte-carlo,pseudo-random},
  number = {4}
}
Downloads: 0