{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T09:35:04Z","timestamp":1648546504573},"reference-count":27,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,12,1]],"date-time":"2020-12-01T00:00:00Z","timestamp":1606780800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We analyze security properties of a two-party key-agreement protocol recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, called Kayawood protocol. At the core of the protocol is an action (called <jats:italic>E-multiplication<\/jats:italic>) of a braid group on some finite set. The protocol assigns a secret element of a braid group to each party (private key). To disguise those elements, the protocol uses a so-called cloaking method that multiplies private keys on the left and on the right by specially designed elements (stabilizers for E-multiplication).<\/jats:p>\n               <jats:p>We present a heuristic algorithm that allows a passive eavesdropper to recover Alice\u2019s private key by removing cloaking elements. Our attack has 100% success rate on randomly generated instances of the protocol for the originally proposed parameter values and for recent proposals that suggest to insert many cloaking elements at random positions of the private key. Implementation of the attack is available on GitHub.<\/jats:p>","DOI":"10.1515\/jmc-2019-0015","type":"journal-article","created":{"date-parts":[[2020,12,5]],"date-time":"2020-12-05T08:47:23Z","timestamp":1607158043000},"page":"237-249","source":"Crossref","is-referenced-by-count":0,"title":["Attack on Kayawood protocol: uncloaking private keys"],"prefix":"10.1515","volume":"15","author":[{"given":"Matvei","family":"Kotov","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Stevens Institute of Technology , Hoboken , , NJ , United States of America"},{"name":"Sobolev Institute of Mathematics , Pevtsova 13 , Omsk , , Russia"}]},{"given":"Anton","family":"Menshov","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Stevens Institute of Technology , Hoboken , , NJ , United States of America"},{"name":"Sobolev Institute of Mathematics , Pevtsova 13 , Omsk , , Russia"}]},{"given":"Alexander","family":"Ushakov","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Stevens Institute of Technology , Hoboken , , NJ , United States of America"}]}],"member":"374","published-online":{"date-parts":[[2020,12,1]]},"reference":[{"key":"2021081821075304515_j_jmc-2019-0015_ref_001","doi-asserted-by":"crossref","unstructured":"K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang, and C. Park. New public-key cryptosystem using braid groups. In Advances in Cryptology \u2013 CRYPTO 2000, volume 1880 of Lecture Notes Comp. Sc., pages 166\u2013183, Berlin, 2000. Springer.","DOI":"10.1007\/3-540-44598-6_10"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_002","doi-asserted-by":"crossref","unstructured":"I. Anshel, M. Anshel, and D. Goldfeld. An algebraic method for public-key cryptography. Math. Res. Lett., 6(3-4):287\u2013291, 1999.","DOI":"10.4310\/MRL.1999.v6.n3.a3"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_003","doi-asserted-by":"crossref","unstructured":"J. H. Cheon and B. Jun. A polynomial time algorithm for the braid diffie-hellman conjugacy problem. In Advances in Cryptology \u2013 CRYPTO 2003, volume 2729 of Lecture Notes Comp. Sc., pages 212\u2013225, Berlin, 2003. Springer.","DOI":"10.1007\/978-3-540-45146-4_13"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_004","doi-asserted-by":"crossref","unstructured":"B. Tsaban. Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography. J. Cryptology, 28:601\u2013622, 2012.","DOI":"10.1007\/s00145-013-9170-9"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_005","doi-asserted-by":"crossref","unstructured":"D. Hofheinz and R. Steinwandt. A practical attack on some braid group based cryptographic primitives. In Advances in Cryptology \u2013 PKC 2003, volume 2567 of Lecture Notes Comp. Sc., pages 187\u2013198, Berlin, 2003. Springer.","DOI":"10.1007\/3-540-36288-6_14"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_006","doi-asserted-by":"crossref","unstructured":"D. Garber, S. Kaplan, M. Teicher, B. Tsaban, and U. Vishne. Length-based conjugacy search in the braid group. In Algebraic Methods in Cryptography, volume 418 of Contemp. Math., pages 75\u201388. Amer. Math. Soc., 2006.","DOI":"10.1090\/conm\/418\/07947"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_007","doi-asserted-by":"crossref","unstructured":"A. G. Miasnikov, V. Shpilrain, and A. Ushakov. A practical attack on some braid group based cryptographic protocols. In Advances in Cryptology \u2013 CRYPTO 2005, volume 3621 of Lecture Notes Comp. Sc., pages 86\u201396, Berlin, 2005. Springer.","DOI":"10.1007\/11535218_6"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_008","doi-asserted-by":"crossref","unstructured":"A. G. Miasnikov, V. Shpilrain, and A. Ushakov. Random subgroups of braid groups: an approach to cryptanalysis of a braid group based cryptographic protocol. In Advances in Cryptology \u2013 PKC 2006, volume 3958 of Lecture Notes Comp. Sc., pages 302\u2013314, Berlin, 2006. Springer.","DOI":"10.1007\/11745853_20"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_009","doi-asserted-by":"crossref","unstructured":"A. D. Myasnikov and A. Ushakov. Length based attack and braid groups: Cryptanalysis of Anshel-Anshel-Goldfeld key exchange protocol. In Advances in Cryptology \u2013 PKC 2007, volume 4450 of Lecture Notes Comp. Sc., pages 76\u201388. Springer, 2007.","DOI":"10.1007\/978-3-540-71677-8_6"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_010","doi-asserted-by":"crossref","unstructured":"I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux. Key agreement, the algebraic eraserTM and lightweight cryptography. In Algebraic Methods in Cryptography, volume 418 of Contemporary Mathematics, pages 1\u201334. American Mathematical Society, 2006.","DOI":"10.1090\/conm\/418\/07943"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_011","unstructured":"I. Anshel, D. Atkins, and P. Goldfeld, D. Gunnels. WalnutDSA(TM): A Quantum-Resistant Digital Signature Algorithm. Preprint. Available at https:\/\/eprint.iacr.org\/2017\/058 2017."},{"key":"2021081821075304515_j_jmc-2019-0015_ref_012","unstructured":"I. Anshel, D. Atkins, and P. Goldfeld, D. Gunnels. Ironwood Meta Key Agreement and Authentication Protocol. Preprint. Available at https:\/\/arxiv.org\/abs\/1702.02450 2017."},{"key":"2021081821075304515_j_jmc-2019-0015_ref_013","unstructured":"I. Anshel, D. Atkins, and P. Goldfeld, D. Gunnels. Kayawood, a Key Agreement Protocol. Preprint. Available at https:\/\/eprint.iacr.org\/2017\/1162 2017."},{"key":"2021081821075304515_j_jmc-2019-0015_ref_014","doi-asserted-by":"crossref","unstructured":"D. Hart, D. Kim, G. Micheli, G. P. Perez, C. Petit, and Y. Quek. A Practical Cryptanalysis ofWalnutDSA. In Public-Key Cryptography \u2013 PKC 2018, pages 381\u2013406. Springer International Publishing, 2018.","DOI":"10.1007\/978-3-319-76578-5_13"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_015","doi-asserted-by":"crossref","unstructured":"W. Beullens and S. Blackburn. Practical attacks against the walnut digital signature scheme. In Advances in Cryptology \u2013 ASIACRYPT 2018, volume 11272 of Lecture Notes in Computer Science, pages 35\u201361. Springer, 2018.","DOI":"10.1007\/978-3-030-03326-2_2"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_016","doi-asserted-by":"crossref","unstructured":"M. Kotov, A. Menshov, and A. Ushakov. An attack on the walnut digital signature algorithm. Designs, Codes and Cryptography, 87(10):2231\u20132250, 2019.","DOI":"10.1007\/s10623-019-00615-y"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_017","doi-asserted-by":"crossref","unstructured":"S. Merz and C. Petit. Factoring products of braids via garside normal form. In Public-Key Cryptography \u2013 PKC 2019, volume 11443 of Lecture Notes in Computer Science, pages 646\u2013678. Springer, 2019.","DOI":"10.1007\/978-3-030-17259-6_22"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_018","unstructured":"NIST PQC forum. Available at https:\/\/groups.google.com\/a\/list.nist.gov\/forum\/#!forum\/pqc-forum accessed: June 10, 2018."},{"key":"2021081821075304515_j_jmc-2019-0015_ref_019","doi-asserted-by":"crossref","unstructured":"A. D. Myasnikov and A. Ushakov. Cryptanalysis of Anshel-Anshel-Goldfeld-Lemieux key agreement protocol. Groups Complex. Cryptol., 1:263\u2013275, 2009.","DOI":"10.1515\/GCC.2009.63"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_020","unstructured":"M. Kotov, A. Menshov, A. Myasnikov, Panteleev. D., and A. Ushakov. Conjugacy separation problem in braids: an attack on the original Colored Burau key agreement protocol. Available at https:\/\/eprint.iacr.org\/2018\/491"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_021","unstructured":"CRyptography And Groups (CRAG) C++ Library. Available at https:\/\/github.com\/stevens-crag\/crag"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_022","doi-asserted-by":"crossref","unstructured":"A. G. Miasnikov, V. Shpilrain, and A. Ushakov. Non-Commutative Cryptography and Complexity of Group-Theoretic Problems. Mathematical Surveys and Monographs. AMS, 2011.","DOI":"10.1090\/surv\/177"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_023","doi-asserted-by":"crossref","unstructured":"M. Paterson and A. Razborov. The set of minimal braids is co-NP-complete. J. Algorithms, 12:393\u2013408, 1991.","DOI":"10.1016\/0196-6774(91)90011-M"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_024","doi-asserted-by":"crossref","unstructured":"P. Dehornoy. A fast method for comparing braids. Adv. Math., 125:200\u2013235, 1997.","DOI":"10.1006\/aima.1997.1605"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_025","doi-asserted-by":"crossref","unstructured":"J. S. Birman, K. H. Ko, and S. J. Lee. A new approach to the word and conjugacy problems in the braid groups. Adv. Math., 139:322\u2013353, 1998.","DOI":"10.1006\/aima.1998.1761"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_026","doi-asserted-by":"crossref","unstructured":"D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston. Word processing in groups. Jones and Bartlett Publishers, 1992.","DOI":"10.1201\/9781439865699"},{"key":"2021081821075304515_j_jmc-2019-0015_ref_027","unstructured":"I. Anshel, D. Atkins, and P. Goldfeld, D. Gunnels. The Walnut digital signature algorithm(TM) specification. Submitted to NIST PQC project (2017). Available at https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/round-1-submissions accessed: June 10, 2018."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/15\/1\/article-p237.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2019-0015\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2019-0015\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,18]],"date-time":"2021-08-18T21:25:37Z","timestamp":1629321937000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2019-0015\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,1]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,11,17]]},"published-print":{"date-parts":[[2020,11,17]]}},"alternative-id":["10.1515\/jmc-2019-0015"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2019-0015","relation":{},"ISSN":["1862-2984"],"issn-type":[{"value":"1862-2984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,1]]}}}  <script>parent.window.postMessage('ixistenz.url:https://api.crossref.org/works/10.1515%2FJMC-2019-0015', '*'); </script> <div id='browserdiffcontainer' style='position: fixed; right: 10px; top: 10vh; min-width: 60px;  border: 1px solid white; background: rgb(251, 189, 0);; opacity: 0.9; font-family: helvetica, arial, sans serif;  font-size: 12px; z-index: 20001; padding-bottom: 20px;'><div onclick="toggle('browserdiffcontainerlist'); return false;" style='background: rgb(151, 89, 0);; color: white; '><strong>&nbsp; <span class='glyphicon glyphicon-minus'></span> NODES</strong></div><div id='browserdiffcontainerlist' style='padding-left: 10px; padding-right: 5px; max-height: 50vh; overflow: auto; '><div><a href='#diffid123' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:123', '*');; return false;" style='text-decoration: none; '>INTERN </a> <a style='color: white;' href='#diffid123'><sup>1</sup></a></div><div><a href='#diffid878' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:878', '*');; return false;" style='text-decoration: none; '>Note </a> <a style='color: white;' href='#diffid878'><sup>8</sup></a></div><div><a href='#diffid115' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:115', '*');; return false;" style='text-decoration: none; '>Project </a> <a style='color: white;' href='#diffid115'><sup>2</sup></a></div></div></div>
<script>
function toggle( divname ) {
  var x = document.getElementById( divname );
  if (x.style.display === 'none') {
    x.style.display = 'block';
  } else {
    x.style.display = 'none';
  }
} </script>