Cryptography with right-angled Artin groups

Delaram Kahrobaei, Ramon Flores


In this paper we propose right-angled Artin groups as a platform for secret sharing schemes based on the efficiency (linear time) of the word problem. Inspired by previous work of Grigoriev-Shpilrain in the context of graphs, we define two new problems: Subgroup Isomorphism Problem and Group Homomorphism Problem. Based on them, we also propose two new authentication schemes. For right-angled Artin groups, theĀ  Group Homomorphism and Graph Homomorphism problems are equivalent, and the later is known to be NP-complete. In the case of the Subgroup Isomorphism problem, we bring some results due to Bridson who shows there are right-angled Artin groups in which this problem is unsolvable.

Full Text:



A. Myasnikov, V. Shpilrain, and A. Ushakov. Non-commutative cryptography and complexity of group-theoretic problems. American Mathematical Society, 2011.

K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J.-s. Kang, and Ch. Park. New Public-Key Cryptosystem Using Braid Groups, pages 166--183. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000. DOI: 10.1007/3-540-44598-6_10

B. Eick and D. Kahrobaei. Polycyclic groups: a new platform for cryptography, preprint arxiv: Technical report, 2004.

J. Gryak and D. Kahrobaei. The status of the polycyclic group-based cryptography: A survey and open problems. Groups Complexity Cryptology, De Gruyter, 8(2):171--186, 2016. DOI: 10.1515/gcc-2016-0013

V. Shpilrain and A. Ushakov. Thompson's Group and Public Key Cryptography, volume 3531, pages 151--163. Springer Berlin Heidelberg, 2005. DOI: 10.1007/11496137_11

I. Chatterji, D. Kahrobaei, and N. Lu. Cryptosystems using subgroup distortion. arXiv:1610.07515v1.

V. Shpilrain and G. Zapata. Combinatorial Group Theory and Public Key Cryptography. Applicable Algebra in Engineering, Communication and Computing, 17(3):291--302, 2006. DOI: 10.1007/s00200-006-0006-9

M. Habeeb, D. Kahrobaei, and V. Shpilrain. A secret sharing scheme based on group presentations and the word problem. Contemp. Math., Amer. Math. Soc., 582:143--150, 2012. DOI: 10.1090/conm/582/11557

D. Kahrobaei and V. Shpilrain. Using Semidirect Product of (Semi)groups in Public Key Cryptography, volume 9709, pages 132--141. Springer International Publishing, 2016. DOI: 10.1007/978-3-319-40189-8_14

G. Baumslag, B. Fine, and X. Xu. Cryptosystems using linear groups. Applicable Algebra in Engineering, Communication and Computing, 17(3):205--217, 2006. DOI: 10.1007/s00200-006-0003-z

G. Petrides. Cryptanalysis of the Public Key Cryptosystem Based on the Word Problem on the Grigorchuk Groups, volume 2898, pages 234--244. Springer Berlin Heidelberg, 2003. DOI: 10.1007/978-3-540-40974-8_19

D. Grigoriev and I. Ponomarenko. Homomorphic public-key cryptosystems and encrypting boolean circuits. Applicable Algebra in Engineering, Communication and Computing, 17(3):239--255, 2006. DOI: 10.1007/s00200-006-0005-x

A. Shamir. How to share a secret. Commun. ACM, 22(11):612--613, 1979. DOI: 10.1145/359168.359176

D. Grigoriev and V. Shpilrain. Authentication schemes from actions on graphs, groups, or rings. Annals of Pure and Applied Logic, 162(3):194--200, 2010. DOI: 0.1016/j.apal.2010.09.004

K. Hauschild and W. Rautenberg. Interpretierbarkeit in der gruppentheorie. Algebra Universalis, 1:136--151, 1971.

T. Korbeda. Right-angled Artin groups and their subgroups. Lecture notes Yale University, pages 1--50, 2013.

R. Charney. An introduction to right-angled Artin groups. Geometriae Dedicata, 125(1):141--158, 2007. DOI: 10.1007/s10711-007-9148-6

W. Magnus, A. Karrass, and D. Solitar. Combinatorial group theory. Dover Publications, New York, 1976.

L. Babaisi. Graph isomorphism in quasipolynomial time. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 684--697. ACM, 2016. DOI: 10.1145/2897518.2897542

H.-N. Liu, C. Wrathall, and K. Zeger. Efficient solution of some problems in free partially commutative monoids. Information and Computation, 89(2):180 -- 198, 1990. DOI: 10.1016/0890-5401(90)90010-F

J. Crisp, E. Godelle, and B. Wiest. The conjugacy problem in right-angled Artin groups and their subgroups. Journal of topology, 2(3):442--460, 2009. DOI: 10.1112/jtopol/jtp018

M. Garey and J. Johnson. Computers and Intractability, A Guide to NP-Completeness. W. H. Freeman, 1979.

M. Bridson. Cube complexes, subgroups of mapping class groups, and nilpotent genus. Geometric group theory, IAS/Park City Math. Ser., 21(21), 2014.

E. Rips. Subgroups of small cancellation groups. Bulletin of the London Mathematical Society, 14(1):45--47, 1982. DOI: 10.1112/blms/14.1.45

F. Haglund and D. T. Wise. Special cube complexes. Geometric and Functional Analysis, 17(5):1551--1620, 2008. DOI: 10.1007/s00039-007-0629-4

M.R. Bridson and C.F. Miller. Recognition of subgroups of direct products of hyperbolic groups. Proceedings of the American Mathematical Society, 132(1):59--65, 2004.

S. Kijima, Y. Otachi, T. Saitoh, and T. Uno. Subgraph isomorphism in graph classes. Discrete Mathematics, 312(21):3164--3173, 2012. DOI: 10.1016/j.disc.2012.07.010



  • There are currently no refbacks.

Copyright (c) 2017 Delaram Kahrobaei

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN: 1896-5334 (print), 2300-889X (online)

Open Acces CrossRef Indexed in DOAJ