In-Person Talk 

Graph groups (a.k.a right-angled Artin groups) admit a presentation where the only relations are commutativity relations which are codified in a finite simplicial graph. The fact that these groups are defined by means of a graph implies that there is a tight connection between algorithmic graph theoretic problems and group theoretic problems for graph groups. Since the graph theoretic problems have been of central importance in complexity theory, it is natural to consider some of these graph theoretic problems via their equivalent formulation as group theoretic problems about graph groups. Motivated by the fact that some of these group theoretic problems can be used for cryptographic purposes, such as authentication schemes, secret sharing schemes, zero-knowledge proofs, hash functions and key exchange protocols; Flores-Kahrobaei-Koberda, in a series of recent papers, have considered these graph groups as a promising platform for several cryptographic schemes, due to the fact that some of these problems are NP-Complete. NP-complete graph theoretic problems have been used in cryptography. For example, motivated by the paper by Goldreich, Micali, and Wigderson in 1991, we present a ZKP scheme based on NP-completeness of graph group Hamiltonicity. The goal of Post-Quantum Cryptography (PQC) is to design cryptosystems which are secure against classical and quantum adversaries. A topic of fundamental research for decades, the status of PQC drastically changed with the NIST PQC  standardization process. In July 2022, after five years and three rounds of selection, NIST  selected a first set of PQC standards for Key-Encapsulation Mechanism (KEM) and Digital Signature Scheme  (DSS) protocols, based on lattices and hash functions. The standardization process is still ongoing with a fourth round for KMM and a new NIST call for post-quantum DSS in 2023. Recent attacks against round-3 multivariate signature schemes, Rainbow and GeMMs, as well as the cryptanalysis of round-4 isogeny based KEM SIKE, emphasize the need to continue the cryptanalysis effort in PQC as well as to increase the diversity in the potential post-quantum hard problems. A relatively unexplored family of such problems come from group-based cryptography. There is a method of using ZKP to produce DSS using Fiat-Shamir's transform techniques. It would be interesting to transform the ZKP scheme which has been proposed in the graph group theoretic sense, to a DSS. This would consequently be a post-quantum scheme as the underlying problem is NP-complete.

This is joint work with R. Flores, T. Koberda.