***********************************
                * 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)