2016/10/20 by Ramón Flores, Flores, Ramón, Delaram Kahrobaei +1 · 1 citation
Computer Science · Engineering · Mathematics · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1610.06495
openalex publication_date 2016/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.