{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,9]],"date-time":"2026-08-09T16:08:59Z","timestamp":1786291739483,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T00:00:00Z","timestamp":1357689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,1,9]]},"DOI":"10.1145\/2422436.2422480","type":"proceedings-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T12:58:22Z","timestamp":1357217902000},"page":"389-400","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["On the power of nonuniformity in proofs of security"],"prefix":"10.1145","author":[{"given":"Kai-Min","family":"Chung","sequence":"first","affiliation":[{"name":"Cornell, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huijia","family":"Lin","sequence":"additional","affiliation":[{"name":"MIT and Boston University, Cambridge and Boston, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[{"name":"Cornell, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[{"name":"Cornell, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Takahiro Matsuda\n       0002 and \n      Kanta Matsuura\n    .\n  On black-box separations among injective one-way functions\n  . In Yuval Ishai editor TCC volume \n  6597\n   of \n  Lecture Notes in Computer Science pages \n  597\n  --\n  614\n  . \n  Springer 2011\n  .   Takahiro Matsuda 0002 and Kanta Matsuura. On black-box separations among injective one-way functions. In Yuval Ishai editor TCC volume 6597 of Lecture Notes in Computer Science pages 597--614. Springer 2011.","DOI":"10.1007\/978-3-642-19571-6_36"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132614"},{"key":"e_1_3_2_1_3_1","volume-title":"Lower bounds on the query complexity of nonuniform and adaptive reductions showing hardness amplification. Electronic Colloquium on Computational Complexity (ECCC), 18:16","author":"Artemenko Sergei","year":"2011","unstructured":"Sergei Artemenko and Ronen Shaltiel . Lower bounds on the query complexity of nonuniform and adaptive reductions showing hardness amplification. Electronic Colloquium on Computational Complexity (ECCC), 18:16 , 2011 . Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of nonuniform and adaptive reductions showing hardness amplification. Electronic Colloquium on Computational Complexity (ECCC), 18:16, 2011."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89255-7_18"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.38"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_22"},{"key":"e_1_3_2_1_7_1","first-page":"1444","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Blum Manuel","year":"1987","unstructured":"Manuel Blum . How to prove a theorem so no one else can claim it . In Proceedings of the International Congress of Mathematicians , pages 1444 -- 1451 , 1987 . Manuel Blum. How to prove a theorem so no one else can claim it. In Proceedings of the International Congress of Mathematicians, pages 1444--1451, 1987."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446974"},{"key":"e_1_3_2_1_9_1","volume-title":"EUROCRYPT: Advances in Cryptology: Proceedings of EUROCRYPT","author":"Venkatesan Boneh","year":"1998","unstructured":"Boneh and Venkatesan . Breaking RSA may not be equivalent to factoring . In EUROCRYPT: Advances in Cryptology: Proceedings of EUROCRYPT , 1998 . Boneh and Venkatesan. Breaking RSA may not be equivalent to factoring. In EUROCRYPT: Advances in Cryptology: Proceedings of EUROCRYPT, 1998."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.67"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.36"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Emmanuel\n      Bresson Jean\n      Monnerat and \n      Damien\n      Vergnaud\n    .\n  Separation results on the \"one-more\" computational problems\n  . In Tal Malkin editor CT-RSA volume \n  4964\n   of \n  Lecture Notes in Computer Science pages \n  71\n  --\n  87\n  . \n  Springer 2008\n  .   Emmanuel Bresson Jean Monnerat and Damien Vergnaud. Separation results on the \"one-more\" computational problems. In Tal Malkin editor CT-RSA volume 4964 of Lecture Notes in Computer Science pages 71--87. Springer 2008.","DOI":"10.1007\/978-3-540-79263-5_5"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1987260.1987296"},{"key":"e_1_3_2_1_14_1","series-title":"Lecture Notes in Computer Science","first-page":"649","volume-title":"Advances in Cryptology - CRYPTO","author":"De Anindya","year":"2010","unstructured":"Anindya De , Luca Trevisan , and Madhur Tulsiani . Time space tradeoffs for attacks against one-way functions and PRGs . In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010 , 30th Annual Cryptology Conference, Santa Barbara, CA, USA , August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science , pages 649 -- 665 . Springer , 2010. Anindya De, Luca Trevisan, and Madhur Tulsiani. Time space tradeoffs for attacks against one-way functions and PRGs. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 649--665. Springer, 2010."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_27"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222061"},{"key":"e_1_3_2_1_19_1","first-page":"186","volume-title":"Proceedings on Advances in cryptology|CRYPTO '86","author":"Fiat Amos","year":"1987","unstructured":"Amos Fiat and Adi Shamir . How to prove yourself: practical solutions to identification and signature problems . In Proceedings on Advances in cryptology|CRYPTO '86 , pages 186 -- 194 , London, UK , 1987 . Springer-Verlag. Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Proceedings on Advances in cryptology|CRYPTO '86, pages 186--194, London, UK, 1987. Springer-Verlag."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_10"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780604"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443276"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796554"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993651"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796557"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875550"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02620230"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"Goldreich Oded","year":"2004","unstructured":"Oded Goldreich . Foundations of Cryptography: Basic Applications . Cambridge University Press , 2004 . Oded Goldreich. Foundations of Cryptography: Basic Applications. Cambridge University Press, 2004."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf00195207"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.27"},{"key":"e_1_3_2_1_33_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/978-3-642-00457-5_13","volume-title":"Theory of Cryptography, 6th Theory of Cryptography Conference, TCC","author":"Haitner Iftach","year":"2009","unstructured":"Iftach Haitner and Thomas Holenstein . On the (im)possibility of key dependent encryption . In Omer Reingold, editor, Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009 , San Francisco, CA , USA, March 15-17, 2009. Proceedings, volume 5444 of Lecture Notes in Computer Science , pages 202 -- 219 . Springer , 2009. 10.1007\/978-3-642-00457-5_13 Iftach Haitner and Thomas Holenstein. On the (im)possibility of key dependent encryption. In Omer Reingold, editor, Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings, volume 5444 of Lecture Notes in Computer Science, pages 202--219. Springer, 2009. 10.1007\/978-3-642-00457-5_13"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_14"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100270"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73009"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73012"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Jonathan\n      Katz Dominique\n      Schr\u00f6der and \n      Arkady\n      Yerukhimovich\n    .\n  Impossibility of blind signatures from one-way permutations\n  . In Yuval Ishai editor TCC volume \n  6597\n   of \n  Lecture Notes in Computer Science pages \n  615\n  --\n  629\n  . \n  Springer 2011\n  .   Jonathan Katz Dominique Schr\u00f6der and Arkady Yerukhimovich. Impossibility of blind signatures from one-way permutations. In Yuval Ishai editor TCC volume 6597 of Lecture Notes in Computer Science pages 615--629. Springer 2011.","DOI":"10.1007\/978-3-642-19571-6_37"},{"key":"e_1_3_2_1_39_1","first-page":"535","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Kim Jeong Han","year":"1999","unstructured":"Jeong Han Kim , Daniel R. Simon , and Prasad Tetali . Limits on the efficiency of one-way permutation-based hash functions . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS) , pages 535 -- 542 , 1999 . Jeong Han Kim, Daniel R. Simon, and Prasad Tetali. Limits on the efficiency of one-way permutation-based hash functions. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 535--542, 1999."},{"key":"e_1_3_2_1_40_1","volume-title":"Another look at non-uniformity. IACR Cryptology ePrint Archive","author":"Koblitz Neal","year":"2012","unstructured":"Neal Koblitz and Alfred Menezes . Another look at non-uniformity. IACR Cryptology ePrint Archive , 2012 :359, 2012. informal publication. Neal Koblitz and Alfred Menezes. Another look at non-uniformity. IACR Cryptology ePrint Archive, 2012:359, 2012. informal publication."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_3"},{"key":"e_1_3_2_1_42_1","unstructured":"Huijia\n      Lin Rafael\n      Pass and \n      Muthuramakrishnan\n      Venkitasubramaniam\n    .\n  Concurrent non-malleable commitments from any one-way function\n  . In Ran Canetti editor TCC volume \n  4948\n   of \n  Lecture Notes in Computer Science pages \n  571\n  --\n  588\n  . \n  Springer 2008\n  .   Huijia Lin Rafael Pass and Muthuramakrishnan Venkitasubramaniam. Concurrent non-malleable commitments from any one-way function. In Ran Canetti editor TCC volume 4948 of Lecture Notes in Computer Science pages 571--588. Springer 2008."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01001-9_4"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Mohammad\n      Mahmoody\n     and \n      Rafael\n      Pass\n    .\n  The curious case of non-interactive commitments - on the power of black-box vs. non-black-box use of primitives\n  . In Reihaneh Safavi-Naini and Ran Canetti editors CRYPTO volume \n  7417\n   of \n  Lecture Notes in Computer Science pages \n  701\n  --\n  718\n  . \n  Springer 2012\n  .  Mohammad Mahmoody and Rafael Pass. The curious case of non-interactive commitments - on the power of black-box vs. non-black-box use of primitives. In Reihaneh Safavi-Naini and Ran Canetti editors CRYPTO volume 7417 of Lecture Notes in Computer Science pages 701--718. Springer 2012.","DOI":"10.1007\/978-3-642-32009-5_41"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.33"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993652"},{"key":"e_1_3_2_1_48_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/978-3-642-19571-6_35","volume-title":"Theory of Cryptography - 8th Theory of Cryptography Conference, TCC","author":"Pass Rafael","year":"2011","unstructured":"Rafael Pass , Wei-Lung Dustin Tseng, and Muthuramakrishnan Venkitasubramaniam. Towards non-black-box lower bounds in cryptography . In Yuval Ishai, editor, Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011 , Providence, RI , USA, March 28-30, 2011. Proceedings, volume 6597 of Lecture Notes in Computer Science , pages 579 -- 596 . Springer , 2011. Rafael Pass, Wei-Lung Dustin Tseng, and Muthuramakrishnan Venkitasubramaniam. Towards non-black-box lower bounds in cryptography. In Yuval Ishai, editor, Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings, volume 6597 of Lecture Notes in Computer Science, pages 579--596. Springer, 2011."},{"key":"e_1_3_2_1_49_1","volume-title":"First Theory of Cryptography Conference, TCC 2004","volume":"2951","author":"Reingold Omer","year":"2004","unstructured":"Omer Reingold , Luca Trevisan , and Salil P. Vadhan . Notions of reducibility between cryptographic primitives. In Theory of Cryptography , First Theory of Cryptography Conference, TCC 2004 , volume 2951 of Lecture Notes in Computer Science, pages 1--20. Springer , 2004 . Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of reducibility between cryptographic primitives. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, volume 2951 of Lecture Notes in Computer Science, pages 1--20. Springer, 2004."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0291-3"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196725"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735096"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054137"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Dominique\n      Unruh\n    .\n  Random oracles and auxiliary input\n  . In Alfred Menezes editor CRYPTO volume \n  4622\n   of \n  Lecture Notes in Computer Science pages \n  205\n  --\n  223\n  . \n  Springer 2007\n  .   Dominique Unruh. Random oracles and auxiliary input. In Alfred Menezes editor CRYPTO volume 4622 of Lecture Notes in Computer Science pages 205--223. Springer 2007.","DOI":"10.1007\/978-3-540-74143-5_12"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11799-2_11"}],"event":{"name":"ITCS '13: Innovations in Theoretical Computer Science","location":"Berkeley California USA","acronym":"ITCS '13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 4th conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422480","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2422436.2422480","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:15Z","timestamp":1750277655000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422480"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,9]]},"references-count":55,"alternative-id":["10.1145\/2422436.2422480","10.1145\/2422436"],"URL":"https:\/\/doi.org\/10.1145\/2422436.2422480","relation":{},"subject":[],"published":{"date-parts":[[2013,1,9]]},"assertion":[{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}