{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T17:08:09Z","timestamp":1785604089495,"version":"3.56.0"},"reference-count":88,"publisher":"Walter de Gruyter GmbH","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1564968"],"award-info":[{"award-number":["CCF-1564968"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-15-1-2164"],"award-info":[{"award-number":["N00014-15-1-2164"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Polycyclic groups are natural generalizations of cyclic groups but with more complicated algorithmic properties. They are finitely presented and the word, conjugacy, and isomorphism decision problems are all solvable in these groups. Moreover, the non-virtually nilpotent ones exhibit an exponential growth rate. These properties make them suitable for use in group-based cryptography, which was proposed in 2004 by Eick and Kahrobaei [<\/jats:p>","DOI":"10.1515\/gcc-2016-0013","type":"journal-article","created":{"date-parts":[[2016,10,11]],"date-time":"2016-10-11T08:10:51Z","timestamp":1476173451000},"source":"Crossref","is-referenced-by-count":14,"title":["The status of polycyclic group-based cryptography: A survey and open problems"],"prefix":"10.1515","volume":"8","author":[{"given":"Jonathan","family":"Gryak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Delaram","family":"Kahrobaei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"374","reference":[{"key":"ref401","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s00200-006-0009-6","article-title":"The conjugacy search problem in public key cryptography: Unnecessary and insufficient","volume":"17","year":"2006","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"key":"ref221","first-page":"1","article-title":"Nis05-6: A non-commutative generalization of ElGamal key exchange using polycyclic groups","year":"2006","journal-title":"IEEE Global Telecommunications Conference"},{"key":"ref481","doi-asserted-by":"crossref","first-page":"314","DOI":"10.2307\/1970671","article-title":"The automorphism group of a polycyclic group","volume":"89","year":"1969","journal-title":"Ann. of Math. (2)"},{"key":"ref561","doi-asserted-by":"crossref","first-page":"1511","DOI":"10.1090\/S0025-5718-03-01493-5","article-title":"On the orbit-stabilizer problem for integral matrix actions of polycyclic groups","volume":"72","year":"2003","journal-title":"Math. Comp."},{"key":"ref881","first-page":"169","article-title":"Using the subgroup membership search problem in public key cryptography","year":"2006","journal-title":"Algebraic Methods in Cryptography"},{"key":"ref71","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1112\/plms\/85.1.62","article-title":"Polycyclic groups, analytic groups and algebraic groups","volume":"85","year":"2002","journal-title":"Proc. Lond. Math. Soc. (3)"},{"key":"ref321","year":"2011","journal-title":"Non-Commutative Cryptography and Complexity of Group-Theoretic Problems"},{"key":"ref651","year":"2005","journal-title":"Handbook of Computational Group Theory"},{"key":"ref901","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1112\/blms\/26.6.543","article-title":"Two remarks on polycyclic groups","volume":"26","year":"1994","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref531","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1112\/plms\/85.1.62","article-title":"Polycyclic groups, analytic groups and algebraic groups","volume":"85","year":"2002","journal-title":"Proc. Lond. Math. Soc. (3)"},{"key":"ref01","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":"ref281","first-page":"67","article-title":"On homomorphisms onto finite groups","volume":"119","year":"1983","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref461","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":"ref871","first-page":"366","article-title":"An authentication scheme based on the twisted conjugacy problem","year":"2008","journal-title":"Applied Cryptography and Network Security"},{"key":"ref771","first-page":"81","article-title":"A linear decomposition attack","volume":"7","year":"2015","journal-title":"Groups Complex. Cryptol."},{"key":"ref421","first-page":"169","article-title":"Using the subgroup membership search problem in public key cryptography","year":"2006","journal-title":"Algebraic Methods in Cryptography"},{"key":"ref571","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1007\/s10559-014-9672-y","article-title":"Vulnerability of cryptographic primitives based on the power conjugacy search problem in quantum computing","volume":"50","year":"2014","journal-title":"Cybernet. Systems Anal."},{"key":"ref511","year":"2007","journal-title":"Quantum algorithms in combinatorial group theory"},{"key":"ref801","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/j.jalgebra.2006.03.002","article-title":"Matrix representations for torsion-free nilpotent groups by Deep Thought","volume":"300","year":"2006","journal-title":"J. Algebra"},{"key":"ref641","year":"1969","journal-title":"The Edmonton Notes on Nilpotent Groups"},{"key":"ref141","first-page":"75","article-title":"Length-based conjugacy search in the braid group","year":"2006","journal-title":"Algebraic Methods in Cryptography"},{"key":"ref731","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1006\/jsco.1999.0286","article-title":"A practical algorithm for finding matrix representations for polycyclic groups","volume":"28","year":"1999","journal-title":"J. Symbolic Comput."},{"key":"ref371","first-page":"61","article-title":"Decidable properties of polycyclic groups","volume":"61","year":"1990","journal-title":"Proc. Lond. Math. Soc. (3)"},{"key":"ref41","first-page":"2003","article-title":"Orbit decidability and the conjugacy problem for some extensions of groups","volume":"362","year":"2010","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref211","first-page":"759","article-title":"An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups","year":"2008","journal-title":"LATIN 2008 \u2013 Theoretical Informatics"},{"key":"ref391","first-page":"231","article-title":"Search and witness problems in group theory","volume":"2","year":"2010","journal-title":"Groups Complex. Cryptol."},{"key":"ref61","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01456932","article-title":"\u00dcber unendliche diskontinuierliche Gruppen","volume":"71","year":"1911","journal-title":"Math. Ann."},{"key":"ref611","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":"ref21","doi-asserted-by":"crossref","first-page":"314","DOI":"10.2307\/1970671","article-title":"The automorphism group of a polycyclic group","volume":"89","year":"1969","journal-title":"Ann. of Math. (2)"},{"key":"ref601","first-page":"75","article-title":"Length-based conjugacy search in the braid group","year":"2006","journal-title":"Algebraic Methods in Cryptography"},{"key":"ref181","year":"1969","journal-title":"The Edmonton Notes on Nilpotent Groups"},{"key":"ref781","year":"2011","journal-title":"Non-Commutative Cryptography and Complexity of Group-Theoretic Problems"},{"key":"ref671","first-page":"759","article-title":"An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups","year":"2008","journal-title":"LATIN 2008 \u2013 Theoretical Informatics"},{"key":"ref191","year":"2005","journal-title":"Handbook of Computational Group Theory"},{"key":"ref471","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1016\/j.jalgebra.2007.01.028","article-title":"Using the Mal\u2019cev correspondence for collection in polycyclic groups","volume":"316","year":"2007","journal-title":"J. Algebra"},{"key":"ref171","first-page":"143","article-title":"A secret sharing scheme based on group presentations and the word problem","year":"2012","journal-title":"Computational and Combinatorial Group Theory and Cryptography"},{"key":"ref11","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1016\/j.jalgebra.2007.01.028","article-title":"Using the Mal\u2019cev correspondence for collection in polycyclic groups","volume":"316","year":"2007","journal-title":"J. Algebra"},{"key":"ref701","first-page":"166","article-title":"New public-key cryptosystem using braid groups","year":"2000","journal-title":"Advances in Cryptology"},{"key":"ref721","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0747-7171(08)80081-8","article-title":"Collection from the left and other strategies","volume":"9","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"ref381","first-page":"124","article-title":"Algorithms for quantum computation: Discrete logarithms and factoring","year":"1994","journal-title":"35th Annual Symposium on Foundations of Computer Science"},{"key":"ref741","first-page":"67","article-title":"On homomorphisms onto finite groups","volume":"119","year":"1983","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref451","doi-asserted-by":"crossref","first-page":"421","DOI":"10.4310\/jdg\/1214428658","article-title":"Growth of finitely generated solvable groups and curvature of Riemannian manifolds","volume":"2","year":"1968","journal-title":"J. Differential Geom."},{"key":"ref231","first-page":"377","article-title":"Non-commutative digital signatures using non-commutative groups","volume":"4","year":"2012","journal-title":"Groups Complex. Cryptol."},{"key":"ref241","first-page":"166","article-title":"New public-key cryptosystem using braid groups","year":"2000","journal-title":"Advances in Cryptology"},{"key":"ref331","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":"ref891","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/s00145-013-9170-9","article-title":"Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography","volume":"28","year":"2015","journal-title":"J. Cryptology"},{"key":"ref351","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/BF02219654","article-title":"Conjugacy in polycyclic groups","volume":"8","year":"1969","journal-title":"Algebra Logic"},{"key":"ref851","first-page":"231","article-title":"Search and witness problems in group theory","volume":"2","year":"2010","journal-title":"Groups Complex. Cryptol."},{"key":"ref501","first-page":"2003","article-title":"Orbit decidability and the conjugacy problem for some extensions of groups","volume":"362","year":"2010","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref631","first-page":"143","article-title":"A secret sharing scheme based on group presentations and the word problem","year":"2012","journal-title":"Computational and Combinatorial Group Theory and Cryptography"},{"key":"ref441","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1112\/blms\/26.6.543","article-title":"Two remarks on polycyclic groups","volume":"26","year":"1994","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref491","first-page":"1","article-title":"Quantum algorithms in group theory","year":"2004","journal-title":"Computational and Experimental Group Theory"},{"key":"ref621","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/j.apal.2010.09.004","article-title":"Zero-knowledge authentication schemes from actions on graphs, groups, or rings","volume":"162","year":"2010","journal-title":"Ann. Pure Appl. Logic"},{"key":"ref711","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":"ref761","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 \u2013 PKC 2007"},{"key":"ref681","first-page":"1","article-title":"Nis05-6: A non-commutative generalization of ElGamal key exchange using polycyclic groups","year":"2006","journal-title":"IEEE Global Telecommunications Conference"},{"key":"ref101","doi-asserted-by":"crossref","first-page":"1511","DOI":"10.1090\/S0025-5718-03-01493-5","article-title":"On the orbit-stabilizer problem for integral matrix actions of polycyclic groups","volume":"72","year":"2003","journal-title":"Math. Comp."},{"key":"ref151","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":"ref251","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":"ref291","doi-asserted-by":"crossref","first-page":"447","DOI":"10.4310\/jdg\/1214428659","article-title":"Growth of finitely generated solvable groups","volume":"2","year":"1968","journal-title":"J. Differential Geom."},{"key":"ref431","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/s00145-013-9170-9","article-title":"Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography","volume":"28","year":"2015","journal-title":"J. Cryptology"},{"key":"ref341","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/j.jalgebra.2006.03.002","article-title":"Matrix representations for torsion-free nilpotent groups by Deep Thought","volume":"300","year":"2006","journal-title":"J. Algebra"},{"key":"ref161","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/j.apal.2010.09.004","article-title":"Zero-knowledge authentication schemes from actions on graphs, groups, or rings","volume":"162","year":"2010","journal-title":"Ann. Pure Appl. Logic"},{"key":"ref411","first-page":"366","article-title":"An authentication scheme based on the twisted conjugacy problem","year":"2008","journal-title":"Applied Cryptography and Network Security"},{"key":"ref791","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":"ref911","doi-asserted-by":"crossref","first-page":"421","DOI":"10.4310\/jdg\/1214428658","article-title":"Growth of finitely generated solvable groups and curvature of Riemannian manifolds","volume":"2","year":"1968","journal-title":"J. Differential Geom."},{"key":"ref581","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0021-8693(76)90021-1","article-title":"Conjugate separability in polycyclic groups","volume":"42","year":"1976","journal-title":"J. Algebra"},{"key":"ref691","first-page":"377","article-title":"Non-commutative digital signatures using non-commutative groups","volume":"4","year":"2012","journal-title":"Groups Complex. Cryptol."},{"key":"ref31","first-page":"1","article-title":"Quantum algorithms in group theory","year":"2004","journal-title":"Computational and Experimental Group Theory"},{"key":"ref131","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1515\/jmc-2014-0003","article-title":"Length-based attack for polycyclic groups","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref121","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0021-8693(76)90021-1","article-title":"Conjugate separability in polycyclic groups","volume":"42","year":"1976","journal-title":"J. Algebra"},{"key":"ref361","first-page":"355","article-title":"The twisted conjugacy problem for endomorphisms of polycyclic groups","volume":"13","year":"2010","journal-title":"J. Group Theory"},{"key":"ref811","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/BF02219654","article-title":"Conjugacy in polycyclic groups","volume":"8","year":"1969","journal-title":"Algebra Logic"},{"key":"ref861","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s00200-006-0009-6","article-title":"The conjugacy search problem in public key cryptography: Unnecessary and insufficient","volume":"17","year":"2006","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"key":"ref311","first-page":"81","article-title":"A linear decomposition attack","volume":"7","year":"2015","journal-title":"Groups Complex. Cryptol."},{"key":"ref301","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 \u2013 PKC 2007"},{"key":"ref81","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1017\/S0017089503001423","article-title":"When is the automorphism group of a virtually polycyclic group virtually polycyclic?","volume":"45","year":"2003","journal-title":"Glasg. Math. J."},{"key":"ref821","first-page":"355","article-title":"The twisted conjugacy problem for endomorphisms of polycyclic groups","volume":"13","year":"2010","journal-title":"J. Group Theory"},{"key":"ref271","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1006\/jsco.1999.0286","article-title":"A practical algorithm for finding matrix representations for polycyclic groups","volume":"28","year":"1999","journal-title":"J. Symbolic Comput."},{"key":"ref111","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1007\/s10559-014-9672-y","article-title":"Vulnerability of cryptographic primitives based on the power conjugacy search problem in quantum computing","volume":"50","year":"2014","journal-title":"Cybernet. Systems Anal."},{"key":"ref541","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1017\/S0017089503001423","article-title":"When is the automorphism group of a virtually polycyclic group virtually polycyclic?","volume":"45","year":"2003","journal-title":"Glasg. Math. J."},{"key":"ref51","year":"2007","journal-title":"Quantum algorithms in combinatorial group theory"},{"key":"ref591","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1515\/jmc-2014-0003","article-title":"Length-based attack for polycyclic groups","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref841","first-page":"124","article-title":"Algorithms for quantum computation: Discrete logarithms and factoring","year":"1994","journal-title":"35th Annual Symposium on Foundations of Computer Science"},{"key":"ref521","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01456932","article-title":"\u00dcber unendliche diskontinuierliche Gruppen","volume":"71","year":"1911","journal-title":"Math. Ann."},{"key":"ref751","doi-asserted-by":"crossref","first-page":"447","DOI":"10.4310\/jdg\/1214428659","article-title":"Growth of finitely generated solvable groups","volume":"2","year":"1968","journal-title":"J. Differential Geom."},{"key":"ref261","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0747-7171(08)80081-8","article-title":"Collection from the left and other strategies","volume":"9","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"ref831","first-page":"61","article-title":"Decidable properties of polycyclic groups","volume":"61","year":"1990","journal-title":"Proc. Lond. Math. Soc. (3)"}],"container-title":["Groups Complexity Cryptology"],"original-title":[],"link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/gcc.2016.8.issue-2\/gcc-2016-0013\/gcc-2016-0013.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-0013\/gcc-2016-0013.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T11:40:07Z","timestamp":1692531607000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/gcc-2016-0013\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,1]]},"references-count":88,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.1515\/gcc-2016-0013","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]]}}}