{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:18Z","timestamp":1787337558192,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>A central focus of modern cryptography is the construction of efficient, high-level cryptographic tools (e.g., encryption schemes) from weaker, low-level cryptographic primitives (e.g., one-way functions). Of interest are both the existence of such constructions and their efficiency.<\/jats:p>\n                  <jats:p>Here, we show essentially tight lower bounds on the best possible efficiency of any black-box construction of some fundamental cryptographic tools from the most basic and widely used cryptographic primitives. Our results hold in an extension of the model introduced by Impagliazzo and Rudich and improve and extend earlier results of Kim, Simon, and Tetali. We focus on constructions of pseudorandom generators, universal one-way hash functions, and digital signatures based on one-way permutations, as well as constructions of public- and private-key encryption schemes based on trapdoor permutations. In each case, we show that any black-box construction beating our efficiency bound would yield the unconditional existence of a one-way function and thus, in particular, prove $P \\neq NP$.<\/jats:p>","DOI":"10.1137\/s0097539704443276","type":"journal-article","created":{"date-parts":[[2005,10,17]],"date-time":"2005-10-17T21:00:17Z","timestamp":1129582817000},"page":"217-246","source":"Crossref","is-referenced-by-count":84,"title":["Bounds on the Efficiency of Generic Cryptographic Constructions"],"prefix":"10.1137","volume":"35","author":[{"given":"Rosario","family":"Gennaro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yael","family":"Gertner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Boaz Barak, How to go beyond the black\u2010box simulation barrier, IEEE Computer Soc., Los Alamitos, CA, 2001, 106\u20131151948699","DOI":"10.1109\/SFCS.2001.959885"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. Barak,\n                      Constant\u2010round coin\u2010tossing with a man in the middle, or realizing the shared random string model\n                      , in 43rd IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 2002, pp. 345\u2013355.","DOI":"10.1109\/SFCS.2002.1181957"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Donald Beaver, Correlated pseudorandomness and the complexity of private computations, ACM, New York, 1996, 479\u20134881427546","DOI":"10.1145\/237814.237996"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Oded Goldreich, On defining proofs of knowledge, Lecture Notes in Comput. Sci., Vol. 740, Springer, Berlin, 1993, 390\u201342095d:94014","DOI":"10.1007\/3-540-48071-4_28"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Shafi Goldwasser, New paradigms for digital signatures and message authentication based on noninteractive zero knowledge proofs, Lecture Notes in Comput. Sci., Vol. 435, Springer, New York, 1990, 194\u20132111062235","DOI":"10.1007\/0-387-34805-0_19"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Shai Halevi, Amit Sahai, Salil Vadhan, Many\u2010to\u2010one trapdoor functions and their relation to public\u2010key cryptosystems, Lecture Notes in Comput. Sci., Vol. 1462, Springer, Berlin, 1998, 283\u201329899j:94038","DOI":"10.1007\/BFb0055735"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Manuel Blum, Shafi Goldwasser, An efficient probabilistic public\u2010key encryption scheme which hides all partial information, Lecture Notes in Comput. Sci., Vol. 196, Springer, Berlin, 1985, 289\u201329987e:94029","DOI":"10.1007\/3-540-39568-7_23"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-002-0112-1"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Y. Desmedt and Y. Frankel,\n                      Threshold cryptosystems\n                      , in Advances in Cryptology\u2014Crypto 1989, Lecture Notes in Comput. Sci. 435, Springer\u2010Verlag, New York, 1990, pp. 307\u2013315.","DOI":"10.1007\/0-387-34805-0_28"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351717"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Fischlin,\n                      On the impossibility of constructing non\u2010interactive statistically\u2010secret protocols from any trapdoor one\u2010way function\n                      , in Cryptographers\u2019 Track\u2014RSA 2002, Lecture Notes in Comput Sci. 2271, Springer\u2010Verlag, New York, 2002, pp. 79\u201395.","DOI":"10.1007\/3-540-45760-7_7"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Rosario Gennaro, Yael Gertner, Jonathan Katz, Lower bounds on the efficiency of encryption and digital signature schemes, ACM, New York, 2003, 417\u20134252005k:94019","DOI":"10.1145\/780542.780604"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Rosario Gennaro, Luca Trevisan, Lower bounds on the efficiency of generic cryptographic constructions, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 305\u20133131931828","DOI":"10.1109\/SFCS.2000.892119"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan, The relationship between public key encryption and oblivious transfer, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 325\u20133351931830","DOI":"10.1109\/SFCS.2000.892121"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Yael Gertner, Tal Malkin, Omer Reingold, On the impossibility of basing trapdoor functions on trapdoor predicates (extended abstract), IEEE Computer Soc., Los Alamitos, CA, 2001, 126\u20131351948701","DOI":"10.1109\/SFCS.2001.959887"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser, Silvio Micali, On the cryptographic applications of random functions (extended abstract), Lecture Notes in Comput. Sci., Vol. 196, Springer, Berlin, 1985, 276\u2013288820023","DOI":"10.1007\/3-540-39568-7_22"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Levin,\n                      Hard\u2010core predicates for any one\u2010way function\n                      , in 21st ACM Symposium on Theory of Computing, ACM, New York, 1989, pp. 25\u201332.","DOI":"10.1145\/73007.73010"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson,\n                      How to play any mental game or a completeness theorem for protocols with honest majority\n                      , in 19th ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 218\u2013229.","DOI":"10.1145\/28395.28420"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0217017"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, A. Schrift, A. Shamir, The discrete logarithm modulo a composite hides O(n) bits, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), Vol. 47, 1993, 376\u201340495g:94014","DOI":"10.1016\/0022-0000(93)90038-X"},{"key":"R29","unstructured":"R. Impagliazzo,\n                      Very Strong One\u2010Way Functions and Pseudo\u2010random Generators Exist Relative to a Random Oracle\n                      , manuscript, 1996."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Luby,\n                      One\u2010way functions are essential for complexity\u2010based cryptography\n                      , in 30th IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 1989, pp. 230\u2013235.","DOI":"10.1109\/SFCS.1989.63483"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich,\n                      Limits on the provable consequences of one\u2010way permutations\n                      , in 21st ACM Symposium on Theory of Computing, ACM, New York, 1989, pp. 44\u201361.","DOI":"10.1145\/73007.73012"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Jeff Kahn, Michael Saks, Cliff Smyth, A dual version of Reimer\u2019s inequality and a proof of Rudich\u2019s conjecture, IEEE Computer Soc., Los Alamitos, CA, 2000, 98\u20131032002a:68044","DOI":"10.1109\/CCC.2000.856739"},{"key":"R33","unstructured":"Jeong Kim, Daniel Simon, Prasad Tetali, Limits on the efficiency of one\u2010way permutation\u2010based hash functions, IEEE Computer Soc., Los Alamitos, CA, 1999, 535\u20135421917593"},{"key":"R34","unstructured":"L. Lamport,\n                      Constructing Digital Signatures from a One\u2010Way Function\n                      , Technical report CSL\u201098, SRI International, Menlo Park, CA, 1979."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"R36","unstructured":", Proceedings of the Twenty\u2010first Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), 1989, 0\u20130, viii+600, Held in Seattle, Washington, May 15\u201317, 198990c:68003"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Omer Reingold, Luca Trevisan, Salil Vadhan, Notions of reducibility between cryptographic primitives, Lecture Notes in Comput. Sci., Vol. 2951, Springer, Berlin, 2004, 1\u2013202146664","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"J. Rompel,\n                      One\u2010way functions are necessary and sufficient for secure signatures\n                      , in 22nd ACM Symposium on Theory of Computing, ACM, New York, 1990, pp. 387\u2013394.","DOI":"10.1145\/100216.100269"},{"key":"R39","unstructured":"S. Rudich,\n                      Limits on the Provable Consequences of One\u2010Way Functions\n                      , Ph.D. thesis, University of California at Berkeley, Berkeley, CA, 1988."},{"key":"R40","doi-asserted-by":"crossref","unstructured":"S. Rudich,\n                      The use of interaction in public cryptosystems\n                      , in Advances in Cryptology\u2014Crypto 1991, Lecture Notes in Comput. Sci. 576, Springer\u2010Verlag, New York, 1992, pp. 242\u2013251.","DOI":"10.1007\/3-540-46766-1_19"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"Daniel Simon, Finding collisions on a one\u2010way street: can secure hash functions be based on general assumptions? Lecture Notes in Comput. Sci., Vol. 1403, Springer, Berlin, 1998, 334\u20133452000h:94032","DOI":"10.1007\/BFb0054137"},{"key":"R42","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"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"A. C.\u2010C. Yao,\n                      How to generate and exchange secrets\n                      , in 27th IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 1986, pp. 162\u2013167.","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539704443276","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:31Z","timestamp":1787336251000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539704443276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539704443276"],"URL":"https:\/\/doi.org\/10.1137\/s0097539704443276","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}