{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T19:20:24Z","timestamp":1722885624568},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T00:00:00Z","timestamp":1554681600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00145-019-09317-z","type":"journal-article","created":{"date-parts":[[2019,4,9]],"date-time":"2019-04-09T01:02:33Z","timestamp":1554771753000},"page":"601-634","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Key Establishment \u00e0 la Merkle in a Quantum World"],"prefix":"10.1007","volume":"32","author":[{"given":"Gilles","family":"Brassard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"H\u00f8yer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kassem","family":"Kalach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sophie","family":"Laplante","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis","family":"Salvail","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,8]]},"reference":[{"issue":"4","key":"9317_CR1","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S Aaronson","year":"2004","unstructured":"S. Aaronson, Y. Shi, Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM\n                           51(4), 595\u2013605 (2004)","journal-title":"Journal of the ACM"},{"key":"9317_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.4086\/toc.2005.v001a003","volume":"1","author":"A Ambainis","year":"2005","unstructured":"A. Ambainis, Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Theory of Computing\n                           1, 37\u201346 (2005)","journal-title":"Theory of Computing"},{"key":"9317_CR3","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"A. Ambainis, Quantum walk algorithm for element distinctness. SIAM Journal on Computing\n                           37, 210\u2013239 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"9317_CR4","unstructured":"A. Ambainis, Personal communication (2016)"},{"key":"9317_CR5","unstructured":"Anonymous Referee, Personal communication through the Editor, 26\u00a0October\u00a02015"},{"issue":"12","key":"9317_CR6","doi-asserted-by":"publisher","first-page":"123010","DOI":"10.1088\/1367-2630\/17\/12\/123010","volume":"17","author":"S Arunachalam","year":"2015","unstructured":"S.\u00a0Arunachalam, V.\u00a0Gheorghiu, T.\u00a0Jochym-O\u2019Connor, M.\u00a0Mosca and P.\u00a0V.\u00a0Srinivasan, On the robustness of bucket brigade quantum RAM. New Journal of Physics\n                           17(12), 123010 (2015)","journal-title":"New Journal of Physics"},{"key":"9317_CR7","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, M.\u00a0Mahmoody-Ghidary, Merkle puzzles are optimal\u2014An \n                    \n                      \n                    \n                    $$O(n^2)$$\n                    \n                      \n                        \n                          O\n                          (\n                          \n                            n\n                            2\n                          \n                          )\n                        \n                      \n                    \n                  \u2013query attack on any key exchange from a random oracle, in Advances in Cryptology\u2014Proceedings of Crypto\u00a02009 (Santa Barbara, California, 2009), pp. 374\u2013390","DOI":"10.1007\/978-3-642-03356-8_22"},{"key":"9317_CR8","unstructured":"A.\u00a0Belovs, G.\u00a0Brassard, P.\u00a0H\u00f8yer, M.\u00a0Kaplan, S.\u00a0Laplante, L.\u00a0Salvail, Provably secure key establishment against quantum adversaries, in Proceedings of 12th Conference on Theory of Quantum Computation, Communication and Cryptography (TQC) (Paris, 2017), pp.\u00a03:1\u20133:17. Open access available at \n                    http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8581\/pdf\/LIPIcs-TQC-2017-3.pdf"},{"key":"9317_CR9","doi-asserted-by":"crossref","unstructured":"A. Belovs, R. \u0160palek, Adversary lower bound for the \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -sum problem, in Proceeding of 4th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS) (Berkeley, California, 2013), pp.\u00a0323\u2013328","DOI":"10.1145\/2422436.2422474"},{"issue":"6","key":"9317_CR10","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"CH Bennett","year":"1973","unstructured":"C.\u00a0H.\u00a0Bennett, Logical reversibility of computation. IBM Journal of Research and Development\n                           17(6), 525\u2013532 (1973)","journal-title":"IBM Journal of Research and Development"},{"issue":"5","key":"9317_CR11","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"CH Bennett","year":"1997","unstructured":"C.\u00a0H.\u00a0Bennett, E.\u00a0Bernstein, G.\u00a0Brassard, U.\u00a0V.\u00a0Vazirani, Strengths and weaknesses of quantum computing. SIAM Journal on Computing\n                           26(5), 1510\u20131523 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"9317_CR12","doi-asserted-by":"crossref","unstructured":"C.\u00a0H.\u00a0Bennett, G.\u00a0Brassard, Quantum cryptography: Public key distribution and coin tossing, in Proceedings of International Conference on Computers, Systems and Signal Processing (Bangalore, India, 1984), pp.\u00a0175\u2013179. Reprinted in Theoretical Computer Science\n                           560-1, 7\u201311 (2014)","DOI":"10.1016\/j.tcs.2014.05.025"},{"key":"9317_CR13","unstructured":"D.\u00a0J.\u00a0Bernstein, Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?, in Proceedings of Workshop on Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS\u201909) (Lausanne, 2009), pp.\u00a0105\u2013116. Proceedings available at \n                    http:\/\/www.hyperelliptic.org\/tanja\/SHARCS\/record2.pdf"},{"key":"9317_CR14","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1038\/nature23461","volume":"549","author":"DJ Bernstein","year":"2017","unstructured":"D.\u00a0J.\u00a0Bernstein, T.\u00a0Lange, Post-quantum cryptography. Nature\n                           549, 188\u2013194 (2017)","journal-title":"Nature"},{"key":"9317_CR15","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M Boyer","year":"1998","unstructured":"M.\u00a0Boyer, G.\u00a0Brassard, P.\u00a0H\u00f8yer, A.\u00a0Tapp, Tight bounds on quantum searching. Fortschritte der Physik\n                           46, 493\u2013505 (1998)","journal-title":"Fortschritte der Physik"},{"key":"9317_CR16","unstructured":"G.\u00a0Brassard, Cryptography in a quantum world, in 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) (Springer, Harrachov, Czech Republic, 2016), pp.\u00a03\u201316. Preliminary version available at \n                    arXiv:1510.04256\n                    \n                   [quant-ph]"},{"issue":"4","key":"9317_CR17","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/3310976","volume":"62","author":"G Brassard","year":"2019","unstructured":"G.\u00a0Brassard, Was Edgar Allan Poe wrong after all? Communications of the ACM\n                           62(4), 132 (2019)","journal-title":"Communications of the ACM"},{"key":"9317_CR18","doi-asserted-by":"crossref","unstructured":"G.\u00a0Brassard, P.\u00a0H\u00f8yer, K.\u00a0Kalach, M.\u00a0Kaplan, S.\u00a0Laplante, L.\u00a0Salvail, Merkle puzzles in a quantum world, in Advances in Cryptology\u2014Proceedings of Crypto\u00a02011 (Santa Barbara, California, 2011), pp.\u00a0391\u2013410","DOI":"10.1007\/978-3-642-22792-9_22"},{"key":"9317_CR19","unstructured":"G.\u00a0Brassard, P.\u00a0H\u00f8yer, M.\u00a0Mosca, A.\u00a0Tapp, Quantum amplitude amplification and estimation, in\u00a0Samuel J. Lomonaco, Jr. editor, Quantum Computation and Quantum Information, AMS Contemporary Mathematics, 305, 53\u201374 (2002)"},{"key":"9317_CR20","unstructured":"G.\u00a0Brassard, P.\u00a0H\u00f8yer, A.\u00a0Tapp, Quantum algorithm for the collision problem (1997). \n                    arXiv:quant-ph\/9705002"},{"key":"9317_CR21","doi-asserted-by":"crossref","unstructured":"G.\u00a0Brassard, L.\u00a0Salvail, Quantum Merkle puzzles, in Proceedings of Second International Conference on Quantum, Nano, and Micro Technologies (ICQNM08) (Sainte-Luce, Martinique, 2008), pp.\u00a076\u201379","DOI":"10.1109\/ICQNM.2008.16"},{"key":"9317_CR22","unstructured":"R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited (1998). \n                    https:\/\/eprint.iacr.org\/1998\/011"},{"issue":"2","key":"9317_CR23","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L Carter","year":"1979","unstructured":"L.\u00a0Carter, and M.\u00a0N.\u00a0Wegman, Universal classes of hash functions. Journal of Computer and System Sciences\n                           18(2), 143\u2013154 (1979)","journal-title":"Journal of Computer and System Sciences"},{"key":"9317_CR24","unstructured":"A.\u00a0Childs, R.\u00a0Kothari, Quantum query complexity of minor-closed graph properties, in Proceedings of 28th Symposium on Theoretical Aspects of Computer Science (STACS) (Dortmund, 2011), pp. 661\u2013672"},{"issue":"6","key":"9317_CR25","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"1976","unstructured":"W.\u00a0Diffie, M.\u00a0E.\u00a0Hellman, New directions in cryptography. IEEE Transactions on Information Theory\n                           22(6), 644\u2013654 (1976)","journal-title":"IEEE Transactions on Information Theory"},{"key":"9317_CR26","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1038\/ncomms1348","volume":"2","author":"I Gerhardt","year":"2011","unstructured":"I.\u00a0Gerhardt, Q.\u00a0Liu, A.\u00a0Lamas-Linares, J.\u00a0Skaar, C.\u00a0Kurtsiefer, V.\u00a0Makarov, Full-field implementation of a perfect eavesdropper on a quantum cryptography system. Nature Communications\n                           2, 349 (2011)","journal-title":"Nature Communications"},{"issue":"16","key":"9317_CR27","doi-asserted-by":"publisher","first-page":"160501","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"V.\u00a0Giovannetti, S.\u00a0Lloyd, L.\u00a0Maccone, Quantum random access memory. Physical Review Letters\n                           100(16), 160501 (2008)","journal-title":"Physical Review Letters"},{"key":"9317_CR28","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser, S.\u00a0Micali, Probabilistic encryption & How to play mental poker keeping secret all partial information, in Proceedings of 14th Annual Symposium on Theory of Computing (STOC) (San Francisco, California, 1982), pp.\u00a0365\u2013377","DOI":"10.1145\/800070.802212"},{"issue":"2","key":"9317_CR29","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"LK Grover","year":"1997","unstructured":"L.\u00a0K.\u00a0Grover, Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters\n                           79(2), 325\u2013328 (1997)","journal-title":"Physical Review Letters"},{"key":"9317_CR30","doi-asserted-by":"publisher","unstructured":"I.\u00a0Haitner, N.\u00a0Mazor, R.\u00a0Oshman, O.\u00a0Reingold, A.\u00a0Yehudayoff, On the communication complexity of key-agreement protocols, in Proceedings of 10th Innovations in Theoretical Computer Science Conference (ITCS) (San Diego, California, 2019), paper no.\u00a040. \n                    https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.40\n                    \n                  .","DOI":"10.4230\/LIPIcs.ITCS.2019.40"},{"key":"9317_CR31","doi-asserted-by":"crossref","unstructured":"P.\u00a0H\u00f8yer, T.\u00a0Lee, R.\u00a0\u0160palek, Negative weights make adversaries stronger, in Proceedings of 39th Annual Symposium on Theory of Computing (STOC) (San Diego, California, 2007) pp.\u00a0526\u2013535. The\u00a0complete version can be found at \n                    arXiv:quant-ph\/0611054","DOI":"10.1145\/1250790.1250867"},{"key":"9317_CR32","doi-asserted-by":"crossref","unstructured":"T.\u00a0Lee, R.\u00a0Mittal, B.\u00a0W.\u00a0Reichardt, R.\u00a0\u0160palek, M.\u00a0Szegedy, Quantum query complexity of state conversion, in Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS) (Palm Springs, California, 2011), pp. 344\u2013353","DOI":"10.1109\/FOCS.2011.75"},{"key":"9317_CR33","unstructured":"F.\u00a0Magniez, Personal communication (2019)"},{"issue":"1","key":"9317_CR34","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1137\/090745854","volume":"40","author":"F Magniez","year":"2011","unstructured":"F.\u00a0Magniez, A.\u00a0Nayak, J.\u00a0Roland, M.\u00a0Santha, Search via quantum walk. SIAM Journal on Computing\n                           40(1), 142-164 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"9317_CR35","unstructured":"R.\u00a0Merkle, C.S.\u00a0244 Project Proposal (1974). Facsimile available at \n                    http:\/\/www.merkle.com\/1974\/FirstCS244projectProposal.pdf"},{"issue":"4","key":"9317_CR36","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1145\/359460.359473","volume":"21","author":"R Merkle","year":"1978","unstructured":"R.\u00a0Merkle, Secure communications over insecure channels. Communications of the\u00a0ACM\n                           21(4), 294\u2013299 (1978)","journal-title":"Communications of the ACM"},{"key":"9317_CR37","unstructured":"National Institute of Standards and Technology\u00a0(NIST), Post-quantum cryptography standardization, \n                    https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/post-quantum-cryptography-standardization"},{"key":"9317_CR38","doi-asserted-by":"crossref","unstructured":"R.\u00a0L.\u00a0Rivest, A.\u00a0Shamir, L.\u00a0Adleman, A\u00a0method for obtaining digital signatures and public-key cryptosystems. Communications of the\u00a0ACM\n                           21(2), 120\u2013126 (1978)","DOI":"10.1145\/359340.359342"},{"key":"9317_CR39","doi-asserted-by":"crossref","unstructured":"M.\u00a0Santha, Quantum walk based search algorithms, in Proceedings of 5th Theory and Applications of Models of Computation (TAMC08) (Xian, 2008), pp.\u00a031\u201346","DOI":"10.1007\/978-3-540-79228-4_3"},{"key":"9317_CR40","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"P.\u00a0W.\u00a0Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing\n                           26, 1484\u20131509 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"9317_CR41","unstructured":"D.\u00a0Unruh, Objection raised during the question period when a preliminary version of this work was presented at the First Annual Conference on Quantum Cryptography (QCrypt), September 2011. Start at the 23rd minute of \n                    https:\/\/www.video.ethz.ch\/conferences\/2011\/qcrypt\/2011-09-12\/5b98752b-7584-4ad0-b7fc-29aaf06371f9.html"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09317-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-019-09317-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09317-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T23:17:11Z","timestamp":1586215031000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-019-09317-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,8]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["9317"],"URL":"https:\/\/doi.org\/10.1007\/s00145-019-09317-z","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,8]]},"assertion":[{"value":"5 December 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}