{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T22:21:50Z","timestamp":1744755710166},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,8,19]],"date-time":"2016-08-19T00:00:00Z","timestamp":1471564800000},"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":[[2017,7]]},"DOI":"10.1007\/s00145-016-9233-9","type":"journal-article","created":{"date-parts":[[2016,8,19]],"date-time":"2016-08-19T16:06:52Z","timestamp":1471622812000},"page":"699-734","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Merkle\u2019s Key Agreement Protocol is Optimal: An \n                \n                  \n                \n                $$O(n^2)$$\n                \n                  \n                    \n                      O\n                      (\n                      \n                        n\n                        2\n                      \n                      )\n                    \n                  \n                \n               Attack on Any Key Agreement from Random Oracles"],"prefix":"10.1007","volume":"30","author":[{"given":"Boaz","family":"Barak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,19]]},"reference":[{"key":"9233_CR1","doi-asserted-by":"crossref","unstructured":"C.H. Bennett , G. Brassard, A.K. Ekert, Quantum cryptography. Sci. Am.\n                            267(4), 50\u201357 (1992)","DOI":"10.1038\/scientificamerican1092-50"},{"key":"9233_CR2","unstructured":"E. Biham, Y.J. Goren, Y. Ishai, Basing weak public-key cryptography on strong one-way functions, in TCC (Ran Canetti, ed.). Lecture Notes in Computer Science, vol. 4948 (Springer, 2008), pp.\u00a055\u201372."},{"key":"9233_CR3","unstructured":"G. Brassard, P. H\u00f8yer, K. Kalach, M. Kaplan, S. Laplante, L. Salvail, Merkle puzzles in a quantum world, in CRYPTO (Phillip Rogaway, ed.). Lecture Notes in Computer Science, vol. 6841 (Springer, 2011), pp.\u00a0391\u2013410."},{"key":"9233_CR4","unstructured":"Z. Brakerski, J. Katz, G. Segev, A. Yerukhimovich, Limits on the power of zero-knowledge proofs in cryptographic constructions, in TCC (Yuval Ishai, ed.). Lecture Notes in Computer Science, vol. 6597 (Springer, 2011), pp.\u00a0559\u2013578."},{"key":"9233_CR5","unstructured":"B. Barak, M. Mahmoody-Ghidary, Merkle puzzles are optimal\u2014 an O (n \n                    \n                      \n                    \n                    $$^2$$\n                    \n                      \n                        \n                          \n                          2\n                        \n                      \n                    \n                  )-query attack on any key exchange from a random oracle, in CRYPTO (Shai Halevi, ed.). Lecture Notes in Computer Science, vol. 5677 (Springer, 2009), pp.\u00a0374\u2013390."},{"key":"9233_CR6","unstructured":"M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in ACM Conference on Computer and Communications Security (1993), pp.\u00a062\u201373."},{"key":"9233_CR7","unstructured":"G. Brassard, L. Salvail, Quantum merkle puzzles, in International Conference on Quantum, Nano and Micro Technologies (ICQNM), IEEE Computer Society (2008), pp.\u00a076\u201379."},{"key":"9233_CR8","unstructured":"R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited. JACM: J. ACM\n                            51(4), 557\u2013594 (2004)"},{"key":"9233_CR9","unstructured":"R. Cleve, Limits on the security of coin flips when half the processors are faulty (extended abstract), in Annual ACM Symposium on Theory of Computing (Berkeley, California), 28\u201330 May (1986), pp.\u00a0364\u2013369."},{"key":"9233_CR10","doi-asserted-by":"crossref","unstructured":"W. Diffie, M, Hellman, New directions in cryptography. IEEE Trans. Inf. Theory\n                            IT-22(6), 644\u2013654 (1976)","DOI":"10.1109\/TIT.1976.1055638"},{"key":"9233_CR11","unstructured":"D. Dachman-Soled, Y. Lindell, M. Mahmoody, T. Malkin, On the black-box complexity of optimally-fair coin tossing, in Y. Ishai, ed. TCC. Lecture Notes in Computer Science, vol. 6597 (Springer, 2011), pp.\u00a0450\u2013467."},{"key":"9233_CR12","doi-asserted-by":"crossref","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)","DOI":"10.1137\/S0097539704443276"},{"key":"9233_CR13","unstructured":"L.K. Grover, A fast quantum mechanical algorithm for database search, in Annual ACM Symposium on Theory of Computing (STOC), 22\u201324 May (1996), pp.\u00a0212\u2013219."},{"key":"9233_CR14","unstructured":"I. Haitner, J.J. Hoch, O. Reingold, G. Segev, Finding collisions in interactive protocols\u2014a tight lower bound on the round complexity of statistically-hiding commitments, in Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE (2007), pp.\u00a0669\u2013679."},{"key":"9233_CR15","unstructured":"T. Holenstein, Complexity theory (2015). \n                    http:\/\/www.complexity.ethz.ch\/education\/Lectures\/ComplexityFS15\/skript_printable.pdf"},{"key":"9233_CR16","unstructured":"I. Haitner, E. Omri, H. Zarosim, Limits on the usefulness of random oracles, in A. Sahai, ed. Theory of Cryptography, TCC. Lecture Notes in Computer Science, vol. 7785 (Springer, 2013), pp.\u00a0437\u2013456."},{"key":"9233_CR17","unstructured":"R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way permutations, in Annual ACM Symposium on Theory of Computing (STOC) (1989). Full version available from Russell Impagliazzo\u2019s home page \n                    https:\/\/cseweb.ucsd.edu\/~russell\/secret.ps\n                    \n                  , pp.\u00a044\u201361."},{"key":"9233_CR18","unstructured":"J. Katz, D. Schr\u00f6der, A. Yerukhimovich, Impossibility of blind signatures from one-way permutations, in Yuval Ishai, ed. TCC. Lecture Notes in Computer Science, vol. 6597 (Springer, 2011), pp.\u00a0615\u2013629."},{"key":"9233_CR19","unstructured":"R.C. Merkle, C.S. 244 project proposal (1974). \n                    http:\/\/merkle.com\/1974\/"},{"key":"9233_CR20","doi-asserted-by":"crossref","unstructured":"R.C. Merkle, Secure communications over insecure channels. Commun. ACM\n                            21(4), 294\u2013299 (1978)","DOI":"10.1145\/359460.359473"},{"key":"9233_CR21","unstructured":"M. Mahmoody, H.K Maji, M. Prabhakaran, Limits of random oracles in secure computation, in Proceedings of the 5th conference on Innovations in theoretical computer science, ACM (2014), pp.\u00a023\u201334."},{"key":"9233_CR22","unstructured":"M. Mahmoody, T. Moran, S.P. Vadhan, Time-lock puzzles in the random oracle model, in P. Rogaway, ed. CRYPTO. Lecture Notes in Computer Science, vol. 6841 (Springer, 2011), pp.\u00a039\u201350."},{"key":"9233_CR23","unstructured":"M. Mahmoody, R, Pass, The curious case of non-interactive commitments\u2014on the power of black-box vs. non-black-box use of primitives, in R. Safavi-Naini, R. Canetti, eds. CRYPTO. Lecture Notes in Computer Science, vol. 7417 (Springer, 2012), pp.\u00a0701\u2013718."},{"key":"9233_CR24","doi-asserted-by":"crossref","unstructured":"R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM\n                            21(2), 120\u2013126 (1978)","DOI":"10.1145\/359340.359342"},{"key":"9233_CR25","unstructured":"O. Reingold, L. Trevisan, S.P. Vadhan, Notions of reducibility between cryptographic primitives, in M. Naor, ed. TCC. Lecture Notes in Computer Science, vol. 2951 (Springer, 2004), pp.\u00a01\u201320."}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-016-9233-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9233-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9233-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9233-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:16:16Z","timestamp":1586333776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-016-9233-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,19]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["9233"],"URL":"https:\/\/doi.org\/10.1007\/s00145-016-9233-9","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,19]]},"assertion":[{"value":"14 February 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2016","order":3,"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"}]}}