{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T04:22:15Z","timestamp":1745986935110,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642365935"},{"type":"electronic","value":"9783642365942"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36594-2_25","type":"book-chapter","created":{"date-parts":[[2013,2,7]],"date-time":"2013-02-07T02:43:27Z","timestamp":1360205007000},"page":"437-456","source":"Crossref","is-referenced-by-count":10,"title":["Limits on the Usefulness of Random Oracles"],"prefix":"10.1007","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","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-03356-8_22","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B. Barak","year":"2009","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Merkle Puzzles Are Optimal \u2014 An O(n2)-Query Attack on Any Key Exchange from a Random Oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 374\u2013390. Springer, Heidelberg (2009)"},{"key":"25_CR2","unstructured":"Beimel, A., Nissim, K., Omri, E.: Distributed private data analysis: On simultaneously solving how and what. CoRR, abs\/1103.2626 (2011)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-540-24638-1_3","volume-title":"Theory of Cryptography","author":"R. Canetti","year":"2004","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 40\u201357. Springer, Heidelberg (2004)"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/3-540-36178-2_7","volume-title":"Advances in Cryptology - ASIACRYPT 2002","author":"Y.-C. Chang","year":"2002","unstructured":"Chang, Y.-C., Hsiao, C.-Y., Lu, C.-J.: On the Impossibilities of Basing One-Way Permutations on Central Cryptographic Primitives. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol.\u00a02501, pp. 110\u2013124. Springer, Heidelberg (2002)"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-642-19571-6_27","volume-title":"Theory of Cryptography","author":"D. Dachman-Soled","year":"2011","unstructured":"Dachman-Soled, D., Lindell, Y., Mahmoody, M., Malkin, T.: On the Black-Box Complexity of Optimally-Fair Coin Tossing. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 450\u2013467. Springer, Heidelberg (2011)"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology - CRYPTO \u201986","author":"A. Fiat","year":"1987","unstructured":"Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol.\u00a0263, pp. 186\u2013194. Springer, Heidelberg (1987)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 305\u2013313 (2000)","DOI":"10.1109\/SFCS.2000.892119"},{"issue":"1","key":"25_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R. Gennaro","year":"2005","unstructured":"Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing\u00a035(1), 217\u2013246 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR9","unstructured":"Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC (2000)"},{"key":"25_CR10","unstructured":"Goldwasser, S., Tauman-Kalai, Y.: On the (in)security of the fiat-shamir paradigm. In: Proceedings of the 44th Annual Symposium on Foundations of Computer Science, FOCS (2003)"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols \u2013 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":"25_CR12","unstructured":"Haitner, I., Omri, E., Zarosim, H.: Limits on the usefulness of random oracles. Technical Report 2012\/573, Cryptology ePrint Archive (2012), http:\/\/eprint.iacr.org\/2012\/573"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 44\u201361. ACM Press (1989)","DOI":"10.1145\/73007.73012"},{"key":"25_CR14","unstructured":"Kahn, J., Saks, M., Smyth, C.: A dual version of reimer\u2019s inequality and a proof of rudich\u2019s conjecture. In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 98\u2013103 (2000)"},{"key":"25_CR15","unstructured":"Kim, J.H., Simon, D., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 535\u2013542 (1999)"},{"key":"25_CR16","unstructured":"Mahmoody, M., Maji, H.K., Prabhakaran, M.: Limits of random oracles in secure computation. Technical Report, arXiv:1205.3554v1 (2012)"},{"key":"#cr-split#-25_CR17.1","doi-asserted-by":"crossref","unstructured":"McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., Vadhan, S.P.: The limits of two-party differential privacy. In: Electronic Colloquium on Computational Complexity (ECCC), p. 106 (2011)","DOI":"10.1109\/FOCS.2010.14"},{"key":"#cr-split#-25_CR17.2","unstructured":"Preliminary version in FOCS 2010 (2010)"},{"key":"25_CR18","unstructured":"Merkle, R.C.: Secure communications over insecure channels. In: SIMMONS: Secure Communications and Asymmetric Cryptosystems (1982)"},{"key":"25_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-642-03356-8_8","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"I. Mironov","year":"2009","unstructured":"Mironov, I., Pandey, O., Reingold, O., Vadhan, S.: Computational Differential Privacy. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 126\u2013142. Springer, Heidelberg (2009)"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/3-540-68339-9_33","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"D. Pointcheval","year":"1996","unstructured":"Pointcheval, D., Stern, J.: Security Proofs for Signature Schemes. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol.\u00a01070, pp. 387\u2013398. Springer, Heidelberg (1996)"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/3-540-46766-1_19","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"S. Rudich","year":"1992","unstructured":"Rudich, S.: The Use of Interaction in Public Cryptosystems. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 242\u2013251. Springer, Heidelberg (1992)"},{"key":"25_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"D.R. Simon","year":"1998","unstructured":"Simon, D.R.: Findings Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol.\u00a01403, pp. 334\u2013345. Springer, Heidelberg (1998)"},{"key":"25_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-540-70936-7_23","volume-title":"Theory of Cryptography","author":"H. Wee","year":"2007","unstructured":"Wee, H.: One-Way Permutations, Interactive Hashing and Statistically Hiding Commitments. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.\u00a04392, pp. 419\u2013433. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36594-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:11:23Z","timestamp":1745957483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36594-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642365935","9783642365942"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36594-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}