{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T12:00:44Z","timestamp":1793102444971,"version":"4.5.0"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539793244708","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1364-1396","source":"Crossref","is-referenced-by-count":1115,"title":["A Pseudorandom Generator from any One-way Function"],"prefix":"10.1137","volume":"28","author":[{"given":"Johan","family":"H\u00c5stad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonid A.","family":"Levin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Luby","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0217013"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0217014"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579167"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"R6","unstructured":"R. Boppana and R. Hirschfeld,\n                      Pseudo\u2010random generators and complexity classes\n                      , in Advances in Comp. Research 5, S. Micali, ed., JAI Press, Greenwich, CT, 1989, pp. 1\u201326."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/58562.59305"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90010-U"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0222069"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. A. Levin,\n                      A hard\u2010core predicate for any one\u2010way function\n                      , in Proc. 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 25\u201332.","DOI":"10.1145\/73007.73010"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser, Silvio Micali, Po Tong, Why and how to establish a private code on a public network, IEEE, New York, 1982, 134\u2013144780391","DOI":"10.1109\/SFCS.1982.100"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad,\n                      Pseudo\u2010random generators under uniform assumptions\n                      , in Proc. 22nd ACM Sympos. on Theory of Computing, ACM, New York, 1990, pp. 395\u2013404.","DOI":"10.1145\/100216.100270"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Herzberg and M. Luby,\n                      Public randomness in cryptography\n                      , in Advances in Cryptology, Proc. 12th Annual Cryptology Conf. (CRYPTO \u201992), Santa Barbara, CA, 1992, Lecture Notes in Comput. Sci. 740, Springer\u2010Verlag, Berlin, 1993, pp. 421\u2013432.","DOI":"10.1007\/3-540-48071-4_29"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Luby,\n                      One\u2010way functions are essential for information based cryptography\n                      , in Proc. 30th IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1989, pp. 230\u2013235.","DOI":"10.1109\/SFCS.1989.63483"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. Levin, and M. Luby,\n                      Pseudo\u2010random number generation from one\u2010way functions\n                      , in Proc. 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 12\u201324.","DOI":"10.1145\/73007.73009"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF00189260"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich,\n                      Limits on the provable consequences of one\u2010way functions\n                      , in 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 44\u201356.","DOI":"10.1145\/73007.73012"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and D. Zuckerman,\n                      How to recycle random bits\n                      , in Proc. 30th IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1989, pp. 248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"R26","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming. Vol. 2: Seminumerical Algorithms\n                      , 3rd ed., Addison\u2010Wesley, Bonn, 1998."},{"key":"R27","first-page":"1","volume":"1","author":"Kolmogorov A. N.","year":"1965","journal-title":"Problems Inform. Transmission","ISSN":"https:\/\/id.crossref.org\/issn\/0032-9460","issn-type":"print"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90054-G"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579323"},{"key":"R30","first-page":"1102","volume":"58","author":"Levin L. A.","year":"1993","journal-title":"J. Symbolic Logic","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4812","issn-type":"print"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1515\/9780691206844"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0217022"},{"key":"R33","unstructured":"R. J. McEliece,\n                      A Public Key Cryptosystem Based on Algebraic Coding Theory\n                      , DSN Progress report, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, 1978."},{"key":"R34","unstructured":"J. McInnes,\n                      Cryptography Using Weak Sources of Randomness\n                      , Tech. report 194\/87, University of Toronto, 1987."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung,\n                      Universal one\u2010way hash functions and their applications\n                      , in Proc. 21st ACM Sympos. on Theory of Computing, ACM, New York, 1989, pp. 33\u201343.","DOI":"10.1145\/73007.73011"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and A. Wigderson,\n                      One\u2010way functions are essential for non\u2010trivial zero\u2010knowledge\n                      , in Proc. 2nd Israel Sympos. on the Theory of Computing and Systems, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 3\u201317.","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"R39","unstructured":"A. Renyi,\n                      Probability Theory\n                      , North\u2013Holland, Amsterdam, 1970."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"J. Rompel,\n                      One\u2010way functions are necessary and sufficient for secure signatures\n                      , in Proc. 22nd ACM Sympos. on Theory of Computing, ACM, New York, 1990, pp. 387\u2013394.","DOI":"10.1145\/100216.100269"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90044-9"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"M. Sipser,\n                      A complexity theoretic approach to randomness\n                      , in Proc. 15th ACM Sympos. on Theory of Computing, ACM New York, 1983, pp. 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579325"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"U. Vazirani and V. Vazirani,\n                      Random polynomial time is equal to slightly\u2010random polynomial time\n                      , in Proc. 26th IEEE Sympos. on Found. of Comput. Sci., IEEE, New York, 1985, pp. 417\u2013428.","DOI":"10.1109\/SFCS.1985.45"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"Andrew Yao, Theory and applications of trapdoor functions, IEEE, New York, 1982, 80\u201391780384","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793244708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:53Z","timestamp":1787335973000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793244708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539793244708"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793244708","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}