Abstracts

Delaram Kahrobaei: Interactions between Group Theory, Cyber Security, Artificial Intelligence, and Quantum Computation

In this talk, I explore how group theory playing a crucial role in data science and artificial intelligence as well as cyber security and quantum computation. At the same time, how computer science for example machine learning algorithms and computational complexity could help group theorists so tackle their open problems.

Symmetry is present in all forms in the natural and biological structures as well as man-made environments. Computational symmetry applies group-theory to create algorithms that model and analyze symmetry in real data set. The use of symmetry groups in optimizing the formulation of signal processing and machine learning algorithms can greatly enhance the impact of these algorithms in many fields of science and engineering where highly complex symmetries exist.

At the same time, Machine Learning techniques could help with solving long standing group theoretic problems. In the past couple of decades many groups have been proposed for cryptography, for instance: polycyclic groups for public-key exchanges, digital signatures, secret sharing schemes (Eick, Kahrobaei), hyperbolic groups for private key encryption (Chatterji-Kahrobaei), p-groups for multilinear maps (Kahrobaei, Tortora, Tota) among others. [J. Gryak, D. Kahrobaei, The Status of the Polycyclic Group-Based Cryptography: A Survey and Open Problems, Groups Complexity Cryptology, De Gruyter (2016).]

Most of the current cryptosystems are based on number theoretic problems such discrete logarithm problem (DLP) for example Diffie-Hellman key-exchange. Recently there has been some natural connections between algorithmic number theoretic and algorithmic group theoretic problems. For example, it has been shown that for a different subfamily of metabelian groups the conjugacy search problem reduces to the DLP. [J. Gryak, D. Kahrobaei, C. Martinez-Perez, On the conjugacy problem in certain metabelian groups, Glasgow Math. J., Cambridge Univ. Press (2019).]

In August 2015 the National Security Agency (NSA) announced plans to upgrade security standards; the goal is to replace all deployed cryptographic protocols with quantum secure protocols. This transition requires a new security standard to be accepted by the National Institute of Standards and Technology (NIST).

One goal of cryptography, as it relates to complexity theory, is to analyze the complexity assumptions used as the basis for various cryptographic protocols and schemes. A central question is determining how to generate intractible instances of these problems upon which to implement an actual cryptographic scheme. The candidates for these instances must be platforms in which the hardness assumption is still reasonable. Determining if the group-based cryptographic schemes are quantum-safe begins with determining the groups in which these hardness assumptions are invalid in the quantum setting.

In what follows we address the quantum complexity of the Hidden Subgroup Problem (HSP) to determine the groups in which the hardness assumption still stands. The Hidden Subgroup Problem (HSP) asks the following: given a description of a group G and a function f from G to X for some finite set X is guaranteed to be strictly H-periodic, i.e. constant and distinct on left (resp. right) cosets of a subgroup H < G, find a generating set for H.

Group-based cryptography could be shown to be post-quantum if the underlying security problem is NP-complete or unsolvable; firstly, we need to analyze the problem’s equivalence to HSP, then analyze the applicability of Grover’s search problem. [K. Horan, D. Kahrobaei, Hidden Subgroup Problem and Post-quantum Group-based Cryptography, Springer Lecture Notes in Computer Science 10931, 2018].