Cryptography with right-angled Artin groups

• Autorzy: Flores R. , Kahrobaei D.

Identyfikatory

DOI

10.20904/283008

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

authentication schemes; group homomorphism; graph homomorphism

PL

schematy uwierzytelniania; homomorfizm grup; homeomorfizm grafów

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2016
• Tom: Vol. 28, No. 3
• Strony: 8--16
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Flores R.

• Department of Geometry and Topology, University of Seville, Spain

autor

Kahrobaei D.

• CUNY Graduate Center, PhD program in computer science, City University of New York
• Tandon School of Engineering, Computer Science Department, New York University

Bibliografia

• [1] A. Myasnikov, V. Shpilrain, and A. Ushakov. Non-commutative cryptography and complexity of group-theoretic problems. American Mathematical Society, 2011.
• [2] 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. 10.1007/3-540-44598-6 10.
• [3] B. Eick and D. Kahrobaei. Polycyclic groups: a new platform for cryptography, preprint arxiv: math.gr/0411077. Technical report, 2004.
• [4] 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. 10.1515/gcc-2016-0013.
• [5] V. Shpilrain and A. Ushakov. Thompson's Group and Public Key Cryptography, volume 3531, pages 151-163. Springer Berlin Heidelberg, 2005. 10.1007/11496137 11.
• [6] I. Chatterji, D. Kahrobaei, and N. Lu. Cryptosystems using subgroup distortion. arXiv:1610.07515v1.
• [7] V. Shpilrain and G. Zapata. Combinatorial Group Theory and Public Key Cryptography. Applicable Algebra in Engineering, Communication and Computing, 17(3):291-302, 2006.10.1007/s00200-006-0006-9.
• [8] 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.10.1090/conm/582/11557.
• [9] D. Kahrobaei and V. Shpilrain. Using Semidirect Product of (Semi)groups in Public Key Cryptography, volume 9709, pages 132-141. Springer International Publishing, 2016. 10.1007/978-3-319-40189-8 14.
• [10] G. Baumslag, B. Fine, and X. Xu. Cryptosystems using linear groups. Applicable Algebra in Engineering, Communication and Computing, 17(3):205-217, 2006. 10.1007/s00200-006-0003-z.
• [11] 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.10.1007/978-3-540-40974-8 19.
• [12] 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. 10.1007/s00200-006-0005-x.
• [13] A. Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979. 10.1145/359168.359176.
• [14] Dima Grigoriev and Vladimir Shpilrain. Authentication schemes from actions on graphs, groups, or rings. Annals of Pure and Applied Logic, 162(3):194-200, 2010. 0.1016/j.apal.2010.09.004.
• [15] K. Hauschild and W. Rautenberg. Interpretierbarkeit in der gruppentheorie. Algebra Universalis, 1:136-151, 1971.
• [16] T. Korbeda. Right-angled Artin groups and their subgroups. Lecture notes Yale University, pages 1-50, 2013.
• [17] Ruth Charney. An introduction to right-angled Artin groups. Geometriae Dedicata, 125(1):141-158, 2007. 10.1007/s10711-007-9148-6.
• [18] W. Magnus, A. Karrass, and D. Solitar. Combinatorial group theory. Dover Publications, New York, 1976.
• [19] Laszlo Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 684-697. ACM, . 10.1145/2897518.2897542.
• [20] Hai-Ning Liu, C. Wrathall, and Kenneth Zeger. Ecient solution of some problems in free partially commutative monoids. Information and Computation, 89(2):180 - 198, 1990. 10.1016/0890-5401(90)90010-F.
• [21] 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. 10.1112/jtopol/jtp018.15
• [22] M. Garey and J. Johnson. Computers and Intractability, A Guide to NP-Completeness. W. H. Freeman, 1979.
• [23] M. Bridson. Cube complexes, subgroups of mapping class groups, and nilpotent genus. Geometric group theory, IAS/Park City Math. Ser., 21(21), 2014.
• [24] E. Rips. Subgroups of small cancellation groups. Bulletin of the London Mathematical Society, 14(1):45-47, 1982. 10.1112/blms/14.1.45.
• [25] F. Haglund and D. T. Wise. Special cube complexes. Geometric and Functional Analysis, 17(5):1551-1620, 2008. 10.1007/s00039-007-0629-4.
• [26] Martin R. Bridson and Charles F. Miller. Recognition of subgroups of direct products of hyperbolic groups. Proceedings of the American Mathematical Society, 132(1):59-65, 2004.
• [27] Shuji Kijima, Yota Otachi, Toshiki Saitoh, and Takeaki Uno. Subgraph isomorphism in graph classes. Discrete Mathematics, 312(21):3164-3173, 2012. 10.1016/j.disc.2012.07.010.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).