{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:54:46Z","timestamp":1764132886937,"version":"3.40.5"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,12,24]],"date-time":"2014-12-24T00:00:00Z","timestamp":1419379200000},"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":[[2016,4]]},"DOI":"10.1007\/s00145-014-9194-9","type":"journal-article","created":{"date-parts":[[2014,12,23]],"date-time":"2014-12-23T22:03:39Z","timestamp":1419372219000},"page":"283-335","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Limits on the Usefulness of Random Oracles"],"prefix":"10.1007","volume":"29","author":[{"given":"Iftach","family":"Haitner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eran","family":"Omri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hila","family":"Zarosim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,24]]},"reference":[{"key":"9194_CR1","doi-asserted-by":"crossref","unstructured":"B. Barak and M. Mahmoody. Merkle puzzles are optimal - an $$O(n^{2})$$ O ( n 2 ) -query attack on any key exchange from a random oracle. In Advances in Cryptology - CRYPTO \u201909, pages 374\u2013390, 2009.","DOI":"10.1007\/978-3-642-03356-8_22"},{"key":"9194_CR2","doi-asserted-by":"crossref","unstructured":"B. Barak and M. Mahmoody-Ghidary. Lower bounds on signatures from symmetric primitives. In Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), 2007.","DOI":"10.1109\/FOCS.2007.71"},{"key":"9194_CR3","unstructured":"A. Beimel, K. Nissim, and E. Omri. Distributed private data analysis: On simultaneously solving how and what. CoRR, abs\/1103.2626, 2011."},{"key":"9194_CR4","doi-asserted-by":"crossref","unstructured":"R. Canetti, O. Goldreich, and S. Halevi. On the random-oracle methodology as applied to length-restricted signature schemes. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, 2004.","DOI":"10.1007\/978-3-540-24638-1_3"},{"key":"9194_CR5","doi-asserted-by":"crossref","unstructured":"Y.-C. Chang, C.-Y. Hsiao, and C.-J. Lu. On the impossibilities of basing one-way permutations on central cryptographic primitives. In Advances in Cryptology - CRYPTO \u201902, pages 110\u2013124, 2002.","DOI":"10.1007\/3-540-36178-2_7"},{"issue":"1","key":"9194_CR6","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1137\/0404004","volume":"4","author":"B Chor","year":"1991","unstructured":"B. Chor and E. Kushilevitz. A zero-one law for boolean privacy. SIAM J. Discrete Math., 4(1):36\u201347, 1991.","journal-title":"SIAM J. Discrete Math."},{"key":"9194_CR7","doi-asserted-by":"crossref","unstructured":"D. Dachman-Soled, Y. Lindell, M. Mahmoody, and T. Malkin. On the black-box complexity of optimally-fair coin tossing. In tcc11, pages 450\u2013467, 2011.","DOI":"10.1007\/978-3-642-19571-6_27"},{"key":"9194_CR8","doi-asserted-by":"crossref","unstructured":"D. Dachman-Soled, M. Mahmoody, and T. Malkin. Can optimally-fair coin tossing be based on one-way functions? In TCC, pages 217\u2013239, 2014.","DOI":"10.1007\/978-3-642-54242-8_10"},{"key":"9194_CR9","doi-asserted-by":"crossref","unstructured":"C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, pages 265\u2013284, 2006.","DOI":"10.1007\/11681878_14"},{"key":"9194_CR10","doi-asserted-by":"crossref","unstructured":"A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology - CRYPTO \u201986, pages 186\u2013194, 1987.","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9194_CR11","doi-asserted-by":"crossref","unstructured":"R. Gennaro and L. Trevisan. Lower bounds on the efficiency of generic cryptographic constructions. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 305\u2013313, 2000.","DOI":"10.1109\/SFCS.2000.892119"},{"issue":"1","key":"9194_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, and L. Trevisan. Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing, 35(1):217\u2013246, 2005.","journal-title":"SIAM Journal on Computing"},{"key":"9194_CR13","unstructured":"Y. Gertner, S. Kannan, T. Malkin, O. Reingold, and M. Viswanathan. The relationship between public key encryption and oblivious transfer. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), 2000."},{"key":"9194_CR14","unstructured":"S. Goldwasser and Y. Tauman-Kalai. On the (in)security of the fiat-shamir paradigm. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), 2003."},{"key":"9194_CR15","doi-asserted-by":"crossref","unstructured":"A. Groce, J. Katz, and A. Yerukhimovich. Limits of computational differential privacy in the client\/server setting. In Theory of Cryptography, Eighth Theory of Cryptography Conference, TCC 2011, pages 417\u2013431, 2011.","DOI":"10.1007\/978-3-642-19571-6_25"},{"key":"9194_CR16","doi-asserted-by":"crossref","unstructured":"I. Haitner, J. J. Hoch, O. Reingold, and G. Segev. Finding collisions in interactive protocols - A tight lower bound on the round complexity of statistically-hiding commitments. In Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), 2007.","DOI":"10.1109\/FOCS.2007.7"},{"key":"9194_CR17","doi-asserted-by":"crossref","unstructured":"I. Haitner, E. Omri, and H. Zarosim. Limits on the usefulness of random oracles. In Theory of Cryptography, Tenth Theory of Cryptography Conference, TCC 2013, pages 437\u2013456, 2013.","DOI":"10.1007\/978-3-642-36594-2_25"},{"key":"9194_CR18","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 44\u201361. ACM Press, 1989.","DOI":"10.1145\/73007.73012"},{"key":"9194_CR19","doi-asserted-by":"crossref","unstructured":"J. Kahn, M. Saks, and C. Smyth. A dual version of reimer\u2019s inequality and a proof of rudich\u2019s conjecture. In Computational Complexity, 2000. Proceedings. 15th Annual IEEE Conference on, pages 98\u2013103, 2000.","DOI":"10.1109\/CCC.2000.856739"},{"key":"9194_CR20","unstructured":"J. H. Kim, D. Simon, and P. Tetali. Limits on the efficiency of one-way permutation-based hash functions. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 535\u2013542, 1999."},{"key":"9194_CR21","unstructured":"M. Mahmoody, H. K. Maji, and M. Prabhakaran. Limits of random oracles in secure computation. Technical Report 1205.3554v1, arXiv, 2012. arXiv:1205.3554v1 ."},{"key":"9194_CR22","doi-asserted-by":"crossref","unstructured":"A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. P. Vadhan. The limits of two-party differential privacy. Electronic Colloquium on Computational Complexity (ECCC), page 106, 2011. Preliminary version in FOCS\u201910.","DOI":"10.1109\/FOCS.2010.14"},{"key":"9194_CR23","unstructured":"R. C. Merkle. Secure communications over insecure channels. In SIMMONS: Secure Communications and Asymmetric Cryptosystems, 1982."},{"key":"9194_CR24","doi-asserted-by":"crossref","unstructured":"I. Mironov, O. Pandey, O. Reingold, and S. P. Vadhan. Computational differential privacy. In Advances in Cryptology - CRYPTO \u201909, pages 126\u2013142, 2009.","DOI":"10.1007\/978-3-642-03356-8_8"},{"key":"9194_CR25","doi-asserted-by":"crossref","unstructured":"D. Pointcheval and J. Stern. Security proofs for signature schemes. In Advances in Cryptology - EUROCRYPT \u201996, pages 387\u2013398, 1996.","DOI":"10.1007\/3-540-68339-9_33"},{"key":"9194_CR26","doi-asserted-by":"crossref","unstructured":"O. Reingold, L. Trevisan, and S. 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\u201320. Springer, 2004.","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"9194_CR27","doi-asserted-by":"crossref","unstructured":"S. Rudich. The use of interaction in public cryptosystems. In Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO \u201991, pages 242\u2013251, 1992.","DOI":"10.1007\/3-540-46766-1_19"},{"issue":"1","key":"9194_CR28","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M Santha","year":"1986","unstructured":"M. Santha and U. V. Vazirani. Generating quasi-random sequences from semi-random sources. J. Comput. Syst. Sci., 33(1):75\u201387, 1986.","journal-title":"J. Comput. Syst. Sci."},{"key":"9194_CR29","doi-asserted-by":"crossref","unstructured":"D. Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In Advances in Cryptology - EUROCRYPT \u201998, pages 334\u2013345, 1998.","DOI":"10.1007\/BFb0054137"},{"key":"9194_CR30","doi-asserted-by":"crossref","unstructured":"H. Wee. One-way permutations, interactive hashing and statistically hiding commitments. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, pages 419\u2013433, 2007.","DOI":"10.1007\/978-3-540-70936-7_23"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9194-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-014-9194-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9194-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9194-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T08:32:04Z","timestamp":1747297924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-014-9194-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,24]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9194"],"URL":"https:\/\/doi.org\/10.1007\/s00145-014-9194-9","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2014,12,24]]},"assertion":[{"value":"14 January 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2014","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"}]}}