Cryptography with right-angled Artin groups

Abstract

In this paper we propose right-angled Artin groups as a platform for secret sharingschemes based on the efficiency (linear time) of the word problem. Inspired by previous work of Grigoriev-Shpilrain in the context of graphs, we de ne two new problems: SubgroupIsomorphism Problem and Group Homomorphism Problem. Based on them, we also proposetwo new authentication schemes. For right-angled Artin groups, the Group Homomorphismand 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 whoshows there are right-angled Artin groups in which this problem is unsolvable.