Hidden Subgroup Problem Survey Reveals Connections to Cryptosystems, Graph Isomorphism, and Code Equivalence

The Hidden Subgroup Problem, a central challenge in mathematical and computer science, underpins the security of many modern cryptographic systems, and Simone Dutto, Pietro Mercuri, and Nadir Murru, along with their colleagues, present a comprehensive survey of its current state. Their work explores both the well-understood abelian case, where efficient solutions already exist thanks to algorithms like Kitaev’s, and the far more complex non-abelian realm, where a general solution remains elusive. The researchers detail progress across various groups, including dihedral and symmetric groups, and examine techniques like Fourier sampling and the black-box approach, revealing the deep connections between abstract mathematical concepts and practical cryptographic security. This survey, enriched by insights from the University of Trento and Politecnico of Torino, provides a valuable resource for understanding the mathematical foundations of cryptography and the ongoing quest to develop secure communication systems.

The core concept involves identifying a hidden subgroup within a larger group, given limited access to information about its elements. Solving the HSP efficiently with a quantum algorithm would compromise the security of many widely used classical cryptographic systems, including those based on factoring integers and computing discrete logarithms, as demonstrated by Shor’s algorithm. Numerous other problems can be reduced to the HSP, meaning a solution would also efficiently solve challenges such as Simon’s Problem, the Discrete Logarithm Problem, and the Shortest Vector Problem.

Investigations into the HSP have focused on various groups, revealing differing levels of complexity. Abelian groups, like integers and their products, are readily solved using the Quantum Fourier Transform. Dihedral groups, important in some cryptographic constructions, can be tackled with the Quantum Fourier Transform and algorithms designed for the Shortest Vector Problem. More complex groups, such as semidirect products and general linear groups, present greater challenges. The most common technique for solving the HSP in abelian groups is the Quantum Fourier Transform. For other groups, researchers employ algorithms based on the Shortest Vector Problem, or utilize black-box approaches that treat the underlying function as an unknown entity. Researchers established a solid foundation in group theory, defining key concepts like subgroups, quotient groups, and element order within finite groups. This groundwork enabled the exploration of various group products, including direct and semidirect products, crucial for constructing complex group structures relevant to cryptographic applications. The study delved into the specifics of semidirect products, defining homomorphisms that govern the interaction between groups.

Researchers utilized these tools to analyze the dihedral group, representing the symmetries of a regular polygon, and connected it to the shortest vector problem on lattices, a significant challenge in cryptography. They also examined symmetric groups, linking them to the graph isomorphism problem. To address the HSP, scientists developed a detailed mathematical framework, focusing on the properties of group elements and their representations. This rigorous approach allowed the team to explore the connections between the HSP and well-known cryptographic problems, such as integer factorization and the discrete logarithm problem, which can be formulated as instances of the abelian HSP. Researchers reviewed the well-understood abelian case, where Kitaev’s algorithm provides an efficient solution, demonstrating its connection to classical problems like order finding, integer factorization, and discrete logarithm calculations. The study then focused on the more challenging non-abelian HSP, examining relevant groups including the dihedral group and symmetric groups. Investigations into the dihedral group revealed its connection to the shortest vector problem on lattices, a critical area in cryptography, while analysis of the symmetric group established links to the graph isomorphism problem.

Researchers also explored groups constructed using semidirect products, with a specific case connected to the code equivalence problem, a challenge relevant to code-based cryptography. Algorithms developed to address the HSP in these cases consistently rely on a technique called Fourier sampling. The team reviewed results obtained using Fourier sampling across various groups and also investigated the black-box method. Researchers systematically reviewed the well-understood abelian case, where efficient solutions, such as Kitaev’s algorithm, already exist, and then turned to the more complex non-abelian HSP. This investigation encompassed several relevant groups, including dihedral and symmetric groups, and explored their connection to challenging problems like the shortest vector problem and graph isomorphism. The study highlights the primary techniques used to tackle the non-abelian HSP, namely Fourier sampling and the black-box approach, detailing how these methods are applied across different group structures.

By examining these approaches, the researchers provide a unified perspective on the mathematical foundations underpinning the HSP and its various instantiations. While acknowledging limitations in solving the general non-abelian HSP, the authors suggest that further research should explore refinements to existing methods and potentially novel algorithmic strategies. They also outline potential avenues for extending the analysis to other groups and problem instances, paving the way for future advancements in this critical area of computational research.