{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:59:02Z","timestamp":1764997142903,"version":"3.37.3"},"reference-count":68,"publisher":"Walter de Gruyter GmbH","issue":"0","funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["16-11-10002"],"award-info":[{"award-number":["16-11-10002"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,1,17]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We discuss pitfalls in the security of the combinatorial public key cryptosystem based on Nielsen transformations inspired by the ElGamal cryptosystem proposed by Fine, Moldenhauer and Rosenberger. We introduce three different types of attacks to possible combinatorial public key encryption schemes and apply these attacks to the scheme corresponding to the cryptosystem under discussion. As a result of our observation, we show that under some natural assumptions the scheme is vulnerable to at least one of the proposed attacks.<\/jats:p>","DOI":"10.1515\/gcc-2017-0013","type":"journal-article","created":{"date-parts":[[2017,10,17]],"date-time":"2017-10-17T10:01:46Z","timestamp":1508234506000},"source":"Crossref","is-referenced-by-count":1,"title":["Cryptanalysis of a combinatorial public key cryptosystem"],"prefix":"10.1515","volume":"0","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8713-7170","authenticated-orcid":false,"given":"Vitali\u012d","family":"Roman\u2019kov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","reference":[{"journal-title":"The Theory of Groups","year":"1959","key":"ref111"},{"key":"ref631","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1007\/BF01091962","article-title":"Infinite groups","volume":"18","year":"1982","journal-title":"J. Math. Sci."},{"key":"ref231","first-page":"81","article-title":"A linear decomposition attack","volume":"7","year":"2015","journal-title":"Groups Complex. Cryptol."},{"journal-title":"Combinatorial Group Theory","year":"1976","key":"ref581"},{"key":"ref201","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s11856-008-1008-z","article-title":"The Diffie\u2013Hellman key exchange protocol and non-abelian nilpotent groups","volume":"165","year":"2008","journal-title":"Israel J. Math."},{"key":"ref151","first-page":"166","article-title":"New public-key cryptosystem using braid groups","year":"2000","journal-title":"Advances in Cryptology\u2014CRYPTO 2000"},{"key":"ref421","first-page":"644","article-title":"New directions in cryptography","volume":"IT-22","year":"1976","journal-title":"IEEE Trans. Information Theory"},{"journal-title":"The Theory of Matrices. Vols. 1 and 2","year":"1959","key":"ref471"},{"journal-title":"The Theory of Groups","year":"1959","key":"ref501"},{"key":"ref481","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1137\/1018113","article-title":"Ill-conditioned eigensystems and the computation of the Jordan canonical form","volume":"18","year":"1976","journal-title":"SIAM Rev."},{"journal-title":"Combinatorial Group Theory","year":"1976","key":"ref191"},{"key":"ref461","doi-asserted-by":"crossref","first-page":"63","DOI":"10.4236\/jcc.2016.412004","article-title":"Cryptographic protocols based on Nielsen transformations","volume":"4","year":"2016","journal-title":"J. Comp. Commun."},{"key":"ref291","first-page":"35","article-title":"Cryptanalysis of some schemes applying automorphisms","volume":"3","year":"2013","journal-title":"Appl. Discrete Math."},{"key":"ref391","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0021-8693(91)90221-S","article-title":"The algorithmic theory of polycyclic-by-finite groups","volume":"142","year":"1991","journal-title":"J. Algebra"},{"journal-title":"Cryptographic protocols based on inner product spaces and group theory with a special focus on the use of Nielsen transformations","year":"2016","key":"ref601"},{"key":"ref101","first-page":"171","article-title":"The status of polycyclic group-based cryptography: A survey and open problems","volume":"8","year":"2016","journal-title":"Groups Complex. Cryptol."},{"journal-title":"A course in Number Theory and Cryptography","year":"1994","key":"ref161"},{"journal-title":"The Theory of Infinite Soluble Groups","year":"2004","key":"ref171"},{"key":"ref411","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1142\/S0218196714500234","article-title":"A family of polycyclic groups over which the uniform conjugacy problem is NP-complete","volume":"24","year":"2014","journal-title":"Internat. J. Algebra Comput."},{"key":"ref541","first-page":"166","article-title":"New public-key cryptosystem using braid groups","year":"2000","journal-title":"Advances in Cryptology\u2014CRYPTO 2000"},{"journal-title":"Algebraic Cryptography","year":"2013","key":"ref281"},{"key":"ref721","first-page":"110","article-title":"A polynomial time algorithm for the braid double shielded public key cryptosystems","volume":"4(84)","year":"2016","journal-title":"Bull. Karaganda Univ. Math. Ser."},{"journal-title":"Introduction to Cryptography","year":"2012","key":"ref271"},{"key":"ref311","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s10469-015-9327-8","article-title":"Linear decomposition method in analyzing hidden information protocols on algebraic platforms","volume":"54","year":"2015","journal-title":"Algebra Logic"},{"key":"ref451","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","year":"1985","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref61","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","year":"1985","journal-title":"IEEE Trans. Inform. Theory"},{"journal-title":"2006 Global Telecommunications Conference \u2013 IEEE GLOBECOM 2006","article-title":"A non-commutative generalization of ElGamal key exchange using polycyclic groups","year":"2006","key":"ref531"},{"key":"ref91","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1137\/1018113","article-title":"Ill-conditioned eigensystems and the computation of the Jordan canonical form","volume":"18","year":"1976","journal-title":"SIAM Rev."},{"key":"ref381","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":"ref11","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0024-3795(88)90003-1","article-title":"An improved algorithm for the computation of Kronecker\u2019s canonical form of a singular pencil","volume":"105","year":"1988","journal-title":"Linear Algebra Appl."},{"key":"ref261","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF00047221","article-title":"Automorphisms of groups","volume":"29","year":"1992","journal-title":"Acta Appl. Math."},{"key":"ref331","first-page":"110","article-title":"A polynomial time algorithm for the braid double shielded public key cryptosystems","volume":"4(84)","year":"2016","journal-title":"Bull. Karaganda Univ. Math. Ser."},{"journal-title":"Nilpotent Groups. Notes of Lectures given at the Canadian Mathematical Congress Summer Seminar, University of Alberta, 12\u201330 August, 1957","year":"1969","key":"ref511"},{"journal-title":"Computation with Finitely Presented Groups","year":"1994","key":"ref361"},{"key":"ref641","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1142\/S0129626496000200","article-title":"Fast parallel computation of the Jordan normal form of matrices","volume":"6","year":"1996","journal-title":"Parallel Process. Lett."},{"key":"ref21","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1142\/S0218196714500234","article-title":"A family of polycyclic groups over which the uniform conjugacy problem is NP-complete","volume":"24","year":"2014","journal-title":"Internat. J. Algebra Comput."},{"key":"ref321","first-page":"197","article-title":"A nonlinear decomposition attack","volume":"8","year":"2016","journal-title":"Groups Complex. Cryptol."},{"key":"ref31","first-page":"644","article-title":"New directions in cryptography","volume":"IT-22","year":"1976","journal-title":"IEEE Trans. Information Theory"},{"journal-title":"Combinatorial Group Theory","year":"2001","key":"ref181"},{"key":"ref01","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0021-8693(91)90221-S","article-title":"The algorithmic theory of polycyclic-by-finite groups","volume":"142","year":"1991","journal-title":"J. Algebra"},{"key":"ref221","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1515\/jgth-2016-0506","article-title":"Non-commutative lattice problems","volume":"19","year":"2016","journal-title":"J. Group Theory"},{"key":"ref71","doi-asserted-by":"crossref","first-page":"63","DOI":"10.4236\/jcc.2016.412004","article-title":"Cryptographic protocols based on Nielsen transformations","volume":"4","year":"2016","journal-title":"J. Comp. Commun."},{"key":"ref621","first-page":"81","article-title":"A linear decomposition attack","volume":"7","year":"2015","journal-title":"Groups Complex. Cryptol."},{"key":"ref611","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1515\/jgth-2016-0506","article-title":"Non-commutative lattice problems","volume":"19","year":"2016","journal-title":"J. Group Theory"},{"key":"ref241","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1007\/BF01091962","article-title":"Infinite groups","volume":"18","year":"1982","journal-title":"J. Math. Sci."},{"key":"ref711","first-page":"197","article-title":"A nonlinear decomposition attack","volume":"8","year":"2016","journal-title":"Groups Complex. Cryptol."},{"key":"ref741","doi-asserted-by":"crossref","first-page":"741","DOI":"10.4171\/cmh\/142","article-title":"Polynomial-time word problems","volume":"83","year":"2008","journal-title":"Comment. Math. Helv."},{"journal-title":"Cryptographic protocols based on inner product spaces and group theory with a special focus on the use of Nielsen transformations","year":"2016","key":"ref211"},{"journal-title":"The Theory of Matrices. Vols. 1 and 2","year":"1959","key":"ref81"},{"journal-title":"Combinatorial Group Theory","year":"2001","key":"ref571"},{"key":"ref491","first-page":"171","article-title":"The status of polycyclic group-based cryptography: A survey and open problems","volume":"8","year":"2016","journal-title":"Groups Complex. Cryptol."},{"key":"ref651","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF00047221","article-title":"Automorphisms of groups","volume":"29","year":"1992","journal-title":"Acta Appl. Math."},{"key":"ref591","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s11856-008-1008-z","article-title":"The Diffie\u2013Hellman key exchange protocol and non-abelian nilpotent groups","volume":"165","year":"2008","journal-title":"Israel J. Math."},{"key":"ref351","doi-asserted-by":"crossref","first-page":"741","DOI":"10.4171\/cmh\/142","article-title":"Polynomial-time word problems","volume":"83","year":"2008","journal-title":"Comment. Math. Helv."},{"journal-title":"2006 Global Telecommunications Conference \u2013 IEEE GLOBECOM 2006","article-title":"A non-commutative generalization of ElGamal key exchange using polycyclic groups","year":"2006","key":"ref141"},{"key":"ref771","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":"ref251","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1142\/S0129626496000200","article-title":"Fast parallel computation of the Jordan normal form of matrices","volume":"6","year":"1996","journal-title":"Parallel Process. Lett."},{"journal-title":"Algebraic Cryptography","year":"2013","key":"ref671"},{"journal-title":"Computing in Euclidean Geometry","year":"1992","key":"ref41"},{"key":"ref701","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s10469-015-9327-8","article-title":"Linear decomposition method in analyzing hidden information protocols on algebraic platforms","volume":"54","year":"2015","journal-title":"Algebra Logic"},{"journal-title":"Nilpotent Groups. Notes of Lectures given at the Canadian Mathematical Congress Summer Seminar, University of Alberta, 12\u201330 August, 1957","year":"1969","key":"ref121"},{"journal-title":"The Theory of Infinite Soluble Groups","year":"2004","key":"ref561"},{"journal-title":"Computing in Euclidean Geometry","year":"1992","key":"ref431"},{"key":"ref681","first-page":"35","article-title":"Cryptanalysis of some schemes applying automorphisms","volume":"3","year":"2013","journal-title":"Appl. Discrete Math."},{"key":"ref401","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0024-3795(88)90003-1","article-title":"An improved algorithm for the computation of Kronecker\u2019s canonical form of a singular pencil","volume":"105","year":"1988","journal-title":"Linear Algebra Appl."},{"journal-title":"A course in Number Theory and Cryptography","year":"1994","key":"ref551"},{"journal-title":"Introduction to Cryptography","year":"2012","key":"ref661"},{"journal-title":"Computation with Finitely Presented Groups","year":"1994","key":"ref751"}],"container-title":["Groups Complexity Cryptology"],"original-title":[],"link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/gcc.ahead-of-print\/gcc-2017-0013\/gcc-2017-0013.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.degruyter.com\/view\/j\/gcc.ahead-of-print\/gcc-2017-0013\/gcc-2017-0013.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,27]],"date-time":"2024-06-27T20:51:29Z","timestamp":1719521489000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/gcc-2017-0013\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,17]]},"references-count":68,"journal-issue":{"issue":"0"},"URL":"https:\/\/doi.org\/10.1515\/gcc-2017-0013","relation":{},"ISSN":["1867-1144","1869-6104"],"issn-type":[{"type":"print","value":"1867-1144"},{"type":"electronic","value":"1869-6104"}],"subject":[],"published":{"date-parts":[[2017,1,17]]}}}