{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:58:16Z","timestamp":1764997096150},"reference-count":40,"publisher":"Walter de Gruyter GmbH","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Anshel\u2013Anshel\u2013Goldfeld (AAG) key exchange protocol is based upon the multiple conjugacy problem for a finitely-presented group. The hardness in breaking this protocol relies on the supposed difficulty in solving the corresponding equations for the conjugating element in the group. Two such protocols based on polycyclic groups as a platform were recently proposed and were shown to be resistant to length-based attack. In this article we propose a parallel evolutionary approach which runs on multicore high-performance architectures. The approach is shown to be more efficient than previous attempts to break these protocols, and also more successful. Comprehensive data of experiments run with a GAP implementation are provided and compared to the results of earlier length-based attacks. These demonstrate that the proposed platform is not as secure as first thought and also show that existing measures of cryptographic complexity are not optimal. A more accurate alternative measure is suggested. Finally, a linear algebra attack for one of the protocols is introduced.<\/jats:p>","DOI":"10.1515\/gcc-2016-0012","type":"journal-article","created":{"date-parts":[[2016,10,11]],"date-time":"2016-10-11T08:10:51Z","timestamp":1476173451000},"source":"Crossref","is-referenced-by-count":2,"title":["A parallel evolutionary approach to solving systems of equations in polycyclic groups"],"prefix":"10.1515","volume":"8","author":[{"given":"Matthew J.","family":"Craven","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Robertz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","reference":[{"key":"ref411","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1515\/jmc-2015-0013","article-title":"Analysis of a certain polycyclic group-based cryptosystem","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref161","first-page":"166","article-title":"New public-key cryptosystem using braid groups","year":"2000","journal-title":"CRYPTO 2000"},{"key":"ref61","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/S0021-8693(03)00292-8","article-title":"Conjugacy problem for braid groups and Garside groups","volume":"266","year":"2003","journal-title":"J. Algebra"},{"key":"ref151","first-page":"660","article-title":"Heisenberg groups as platform for the AAG key-exchange protocol","year":"2014","journal-title":"Proceedings of the 22nd International Conference on Network Protocols"},{"key":"ref301","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/S0021-8693(03)00292-8","article-title":"Conjugacy problem for braid groups and Garside groups","volume":"266","year":"2003","journal-title":"J. Algebra"},{"key":"ref451","first-page":"359","article-title":"Length-based cryptanalysis: The case of Thompson\u2019s group","volume":"1","year":"2007","journal-title":"J. Math. Crypt."},{"key":"ref271","first-page":"135","article-title":"An evolutionary algorithm solution of the multiple conjugacy search problem in partially commutative groups with applications","volume":"4","year":"2012","journal-title":"Groups Complex. Cryptol."},{"key":"ref431","first-page":"29","article-title":"Random subgroups and analysis of the length-based and quotient attacks","volume":"2","year":"2008","journal-title":"J. Math. Cryptol."},{"key":"ref351","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1006\/jsco.2002.0559","article-title":"Efficient collection in infinite polycyclic groups","volume":"34","year":"2002","journal-title":"J. Symbolic Comput."},{"key":"ref421","first-page":"76","article-title":"Length based attack and braid groups: Cryptanalysis of Anshel\u2013Anshel\u2013Goldfeld key exchange protocol","year":"2007","journal-title":"Public Key Cryptography"},{"key":"ref471","first-page":"4","article-title":"The GAP Group GAP Groups and Programming Version http www gap system org","journal-title":"Algorithms"},{"key":"ref231","first-page":"4","article-title":"The GAP Group GAP Groups and Programming Version http www gap system org","journal-title":"Algorithms"},{"key":"ref331","first-page":"75","article-title":"Length-based conjugacy search in the braid group","year":"2006","journal-title":"Algebraic Methods in Cryptography"},{"key":"ref121","year":"1989","journal-title":"Genetic Algorithms in Search, Optimization and Machine Learning"},{"key":"ref191","first-page":"29","article-title":"Random subgroups and analysis of the length-based and quotient attacks","volume":"2","year":"2008","journal-title":"J. Math. Cryptol."},{"key":"ref181","first-page":"76","article-title":"Length based attack and braid groups: Cryptanalysis of Anshel\u2013Anshel\u2013Goldfeld key exchange protocol","year":"2007","journal-title":"Public Key Cryptography"},{"key":"ref131","year":"2005","journal-title":"Handbook of Computational Group Theory"},{"key":"ref221","first-page":"929","article-title":"Parallel evolutionary algorithms","year":"2015","journal-title":"Handbook of Computational Intelligence"},{"key":"ref311","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1515\/jmc-2014-0003","article-title":"Length-based attacks in polycyclic groups","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref81","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.aam.2005.03.002","article-title":"Probabilistic solutions of equations in the braid group","volume":"35","year":"2005","journal-title":"Adv. Appl. Math."},{"key":"ref391","first-page":"660","article-title":"Heisenberg groups as platform for the AAG key-exchange protocol","year":"2014","journal-title":"Proceedings of the 22nd International Conference on Network Protocols"},{"key":"ref251","doi-asserted-by":"crossref","first-page":"287","DOI":"10.4310\/MRL.1999.v6.n3.a3","article-title":"An algebraic method for public-key cryptography","volume":"6","year":"1999","journal-title":"Math. Res. Lett."},{"key":"ref11","doi-asserted-by":"crossref","first-page":"287","DOI":"10.4310\/MRL.1999.v6.n3.a3","article-title":"An algebraic method for public-key cryptography","volume":"6","year":"1999","journal-title":"Math. Res. Lett."},{"key":"ref171","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1515\/jmc-2015-0013","article-title":"Analysis of a certain polycyclic group-based cryptosystem","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref91","first-page":"75","article-title":"Length-based conjugacy search in the braid group","year":"2006","journal-title":"Algebraic Methods in Cryptography"},{"key":"ref371","year":"2005","journal-title":"Handbook of Computational Group Theory"},{"key":"ref401","first-page":"166","article-title":"New public-key cryptosystem using braid groups","year":"2000","journal-title":"CRYPTO 2000"},{"key":"ref211","first-page":"359","article-title":"Length-based cryptanalysis: The case of Thompson\u2019s group","volume":"1","year":"2007","journal-title":"J. Math. Crypt."},{"key":"ref101","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1093\/qmath\/20.1.235","article-title":"The braid group and other groups","volume":"20","year":"1969","journal-title":"Quart. J. Math. Oxford"},{"key":"ref241","first-page":"13","article-title":"New key agreement protocols","year":"2001","journal-title":"Topics in Cryptology \u2013 CT-RSA 2001"},{"key":"ref71","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1515\/jmc-2014-0003","article-title":"Length-based attacks in polycyclic groups","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref321","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.aam.2005.03.002","article-title":"Probabilistic solutions of equations in the braid group","volume":"35","year":"2005","journal-title":"Adv. Appl. Math."},{"key":"ref01","first-page":"13","article-title":"New key agreement protocols","year":"2001","journal-title":"Topics in Cryptology \u2013 CT-RSA 2001"},{"key":"ref31","first-page":"135","article-title":"An evolutionary algorithm solution of the multiple conjugacy search problem in partially commutative groups with applications","volume":"4","year":"2012","journal-title":"Groups Complex. Cryptol."},{"key":"ref201","first-page":"69","article-title":"A PTIME solution to the restricted conjugacy problem in generalized heisenberg groups","volume":"8","year":"2016","journal-title":"Groups Complex. Cryptol."},{"key":"ref341","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1093\/qmath\/20.1.235","article-title":"The braid group and other groups","volume":"20","year":"1969","journal-title":"Quart. J. Math. Oxford"},{"key":"ref441","first-page":"69","article-title":"A PTIME solution to the restricted conjugacy problem in generalized heisenberg groups","volume":"8","year":"2016","journal-title":"Groups Complex. Cryptol."},{"key":"ref361","year":"1989","journal-title":"Genetic Algorithms in Search, Optimization and Machine Learning"},{"key":"ref461","first-page":"929","article-title":"Parallel evolutionary algorithms","year":"2015","journal-title":"Handbook of Computational Intelligence"},{"key":"ref111","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1006\/jsco.2002.0559","article-title":"Efficient collection in infinite polycyclic groups","volume":"34","year":"2002","journal-title":"J. Symbolic Comput."}],"container-title":["Groups Complexity Cryptology"],"original-title":[],"link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/gcc.2016.8.issue-2\/gcc-2016-0012\/gcc-2016-0012.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/view\/j\/gcc.2016.8.issue-2\/gcc-2016-0012\/gcc-2016-0012.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T11:40:04Z","timestamp":1692531604000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/gcc-2016-0012\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,1]]},"references-count":40,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.1515\/gcc-2016-0012","relation":{},"ISSN":["1867-1144","1869-6104"],"issn-type":[{"value":"1867-1144","type":"print"},{"value":"1869-6104","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,1]]}}}