The problem of finding periodicity in quantum cryptanalysis of group cryptography algorithms

Abstract

The article explores the fundamental role of quantum period determination algorithms, particularly in the context of cryptography. The work focuses on quantum algorithms that exploit periodicity, such as Shor's algorithm, which is central to efficient integer factorization. It highlights the challenges quantum algorithms face when applied to non-Abelian groups such as the Suzuki, Hermitage, and Rie groups, which exhibit complex periodic structures that are difficult to solve with existing quantum methods. The study delves into the structure and properties of these groups, explaining the complexity of their representations and the challenges posed by the quantum Fourier transform (QFT) in these cases. This contrasts the relative ease with which Abelian groups can be handled by quantum algorithms with the exponential complexity encountered with non-Abelian groups. The study provides a comparative analysis of the computational complexity between classical and quantum approaches to find the period in different types of groups, highlighting that while quantum algorithms offer exponential speedup for Abelian cases, non-Abelian structures remain a frontier for further research. The conclusion calls for continued research in quantum representation theory and cryptanalysis, especially for non-Abelian groups where current quantum methods have not yet provided efficient solutions. The problem of finding the period has been identified as critical to the advancement of both quantum computing and cryptographic applications.