{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T09:05:52Z","timestamp":1723799152118},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,11,13]],"date-time":"2013-11-13T00:00:00Z","timestamp":1384300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2015,7]]},"DOI":"10.1007\/s00145-013-9161-x","type":"journal-article","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T16:13:04Z","timestamp":1384272784000},"page":"509-532","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Constructing Pseudorandom Functions (Especially when They Don\u2019t Exist)"],"prefix":"10.1007","volume":"28","author":[{"given":"Eric","family":"Miles","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,13]]},"reference":[{"key":"9161_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, A. Itai, A fast and simple randomized algorithm for the maximal independent set problem. J. Algorithms\n                  7, 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"issue":"4","key":"9161_CR2","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in NC0. SIAM J. Comput.\n                  36(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9161_CR3","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00037-007-0237-6","volume":"17","author":"B. Applebaum","year":"2008","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz On pseudorandom generators with linear stretch in NC0. Comput. Complex.\n                  17(1), 38\u201369 (2008)","journal-title":"Comput. Complex."},{"key":"9161_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-540-45198-3_17","volume-title":"7th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)","author":"N. Alon","year":"2003","unstructured":"N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, D. Ron, Testing low-degree polynomials over \n                    \n                      \n                    \n                    ${\\rm GF}(2)$\n                  , in 7th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM). Lecture Notes in Computer Science, vol.\u00a02764 (Springer, Berlin, 2003), pp. 188\u2013199"},{"key":"9161_CR5","first-page":"298","volume-title":"FOCS","author":"M. Alekhnovich","year":"2003","unstructured":"M. Alekhnovich, More on average case vs approximation complexity, in FOCS (2003), pp. 298\u2013307"},{"issue":"4","key":"9161_CR6","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, R. Solovay, Relativizations of the P=?NP question. SIAM J. Comput.\n                  4(4), 431\u2013442 (1975)","journal-title":"SIAM J. Comput."},{"key":"9161_CR7","volume-title":"9th Theory of Cryptography Conference (TCC)","author":"I. Berman","year":"2012","unstructured":"I. Berman, I. Haitner, From non-adaptive to adaptive pseudorandom functions, in 9th Theory of Cryptography Conference (TCC) (2012)"},{"key":"9161_CR8","volume-title":"8th Theory of Cryptography Conference (TCC)","author":"J. Bronson","year":"2011","unstructured":"J. Bronson, A. Juma, P.A. Papakonstantinou, Limits on the stretch of non-adaptive constructions of pseudo-random generators, in 8th Theory of Cryptography Conference (TCC) (2011)"},{"issue":"4","key":"9161_CR9","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput.\n                  13(4), 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9161_CR10","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"B. Chor, O. Goldreich, On the power of two-point based sampling. J. Complex.\n                  5(1), 96\u2013106 (1989)","journal-title":"J. Complex."},{"issue":"2","key":"9161_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"J.L. Carter, M.N. Wegman, Universal classes of hash functions. J. Comput. Syst. Sci.\n                  18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9161_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R. Gennaro","year":"2005","unstructured":"R. Gennaro, Y. Gertner, J. Katz, L. Trevisan, Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput.\n                  35(1), 217\u2013246 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9161_CR13","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM\n                  33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"issue":"6","key":"9161_CR14","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1137\/0222069","volume":"22","author":"O. Goldreich","year":"1993","unstructured":"O. Goldreich, H. Krawczyk, M. Luby, On the existence of pseudorandom generators. SIAM J. Comput.\n                  22(6), 1163\u20131175 (1993)","journal-title":"SIAM J. Comput."},{"key":"9161_CR15","first-page":"25","volume-title":"21st ACM Symp. on the Theory of Computing (STOC)","author":"O. Goldreich","year":"1989","unstructured":"O. Goldreich, L. Levin, A hard-core predicate for all one-way functions, in 21st ACM Symp. on the Theory of Computing (STOC) (1989), pp. 25\u201332"},{"key":"9161_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Volume 1, Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools (Cambridge University Press, Cambridge, 2001)"},{"key":"9161_CR17","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/11787006_20","volume-title":"Coll. on Automata, Languages and Programming (ICALP)","author":"I. Haitner","year":"2006","unstructured":"I. Haitner, D. Harnik, O. Reingold, Efficient pseudorandom generators from exponentially hard one-way functions, in Coll. on Automata, Languages and Programming (ICALP) (2006), pp. 228\u2013239"},{"issue":"4","key":"9161_CR18","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"J. H\u00e5stad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput.\n                  28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"9161_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/11681878_23","volume-title":"TCC","author":"T. Holenstein","year":"2006","unstructured":"T. Holenstein, Pseudorandom generators from one-way functions: a simple construction for any hardness, in TCC, ed. by S. Halevi, T. Rabin. Lecture Notes in Computer Science, vol.\u00a03876 (Springer, Berlin, 2006), pp. 443\u2013461"},{"key":"9161_CR20","first-page":"437","volume-title":"42nd ACM Symp. on the Theory of Computing (STOC)","author":"I. Haitner","year":"2010","unstructured":"I. Haitner, O. Reingold, S.P. Vadhan, Efficiency improvements in constructing pseudorandom generators from one-way functions, in 42nd ACM Symp. on the Theory of Computing (STOC) (2010), pp.\u00a0437\u2013446"},{"key":"9161_CR21","first-page":"698","volume-title":"FOCS","author":"T. Holenstein","year":"2012","unstructured":"T. Holenstein, M. Sinha, Constructing a pseudorandom generator requires an almost linear number of calls, in FOCS (2012), pp. 698\u2013707"},{"key":"9161_CR22","unstructured":"R. Impagliazzo, Very strong one-way functions and pseudo-random generators exist relative to a random oracle. Manuscript (1996)"},{"key":"9161_CR23","first-page":"44","volume-title":"ACM Symp. on the Theory of Computing (STOC)","author":"R. Impagliazzo","year":"1989","unstructured":"R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way permutations, in ACM Symp. on the Theory of Computing (STOC) (1989), pp. 44\u201361"},{"key":"9161_CR24","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/11681878_24","volume-title":"3rd Theory of Cryptography Conference (TCC)","author":"C.-J. Lu","year":"2006","unstructured":"C.-J. Lu, On the complexity of parallel hardness amplification for one-way functions, in 3rd Theory of Cryptography Conference (TCC) (2006), pp. 462\u2013481"},{"issue":"2","key":"9161_CR25","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan, A. Wigderson, Hardness vs randomness. J. Comput. Syst. Sci.\n                  49(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9161_CR26","volume-title":"1st Theory of Cryptography Conference","author":"O. Reingold","year":"2004","unstructured":"O. Reingold, L. Trevisan, S. Vadhan, Notions of reducibility between cryptographic primitives, in 1st Theory of Cryptography Conference, 2004, Feb. 19\u201321 (Springer, Cambridge, 2004)"},{"issue":"4","key":"9161_CR27","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1145\/502090.502099","volume":"48","author":"L. Trevisan","year":"2001","unstructured":"L. Trevisan, Extractors and pseudorandom generators. J. ACM\n                  48(4), 860\u2013879 (2001)","journal-title":"J. ACM"},{"key":"9161_CR28","first-page":"183","volume-title":"20th IEEE Conf. on Computational Complexity (CCC)","author":"E. Viola","year":"2005","unstructured":"E. Viola, On constructing parallel pseudorandom generators from one-way functions, in 20th IEEE Conf. on Computational Complexity (CCC) (2005), pp. 183\u2013197"},{"key":"9161_CR29","volume-title":"ACM Symp. on the Theory of Computing (STOC)","author":"S.P. Vadhan","year":"2012","unstructured":"S.P. Vadhan, C.J. Zheng, Characterizing pseudoentropy and simplifying pseudorandom generator constructions, in ACM Symp. on the Theory of Computing (STOC) (2012)"},{"key":"9161_CR30","first-page":"80","volume-title":"23rd IEEE Symp. on Foundations of Computer Science (FOCS)","author":"A. Yao","year":"1982","unstructured":"A. Yao, Theory and applications of trapdoor functions, in 23rd IEEE Symp. on Foundations of Computer Science (FOCS) (IEEE Press, New York, 1982), pp. 80\u201391"},{"key":"9161_CR31","volume-title":"\u201cRandomized Algorithms\u201d Satellite Workshop of the 23rd Symposium on Mathematical Foundations of Computer Science","author":"M. Zimand","year":"1998","unstructured":"M. Zimand, Efficient privatization of random bits, in \u201cRandomized Algorithms\u201d Satellite Workshop of the 23rd Symposium on Mathematical Foundations of Computer Science (1998). Available at \n                    http:\/\/triton.towson.edu\/~mzimand\/pub\/rand-privat.ps"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-013-9161-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-013-9161-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-013-9161-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-013-9161-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:14:57Z","timestamp":1586333697000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-013-9161-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,13]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["9161"],"URL":"https:\/\/doi.org\/10.1007\/s00145-013-9161-x","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,13]]},"assertion":[{"value":"1 March 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2013","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}