***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Delaram Kahrobaei (CUNY)
Thursday 23rd February, 3:00 in Fine Hall 224.
Title: NP-complete problems in graph groups and connection to post-quantum cryptography
Abstract: 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 imply 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.
----------------------------------
Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)