A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective

• URL: http://arxiv.org/abs/2512.02087v1
• Date: Mon, 01 Dec 2025 12:48:34 GMT
• Title: A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• Authors: Simone Dutto, Pietro Mercuri, Nadir Murru, Lorenzo Romano,
• Abstract summary: The Hidden Subgroup Problem (HSP) plays an important role in studying the security of public-key cryptosystems.<n>We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP.<n>We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a survey on the Hidden Subgroup Problem (HSP), which plays an important role in studying the security of public-key cryptosystems. We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP, recalling how classical problems (such as order finding, integer factorization, and discrete logarithm) can be formulated as abelian HSP instances. We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known, focusing on some relevant groups including dihedral group (connected to the shortest vector problem), symmetric groups (connected to the graph isomorphism problem), and semidirect product constructions (connected, in a special case, to the code equivalence problem). We also describe the main techniques for addressing the HSP in non-abelian cases, namely Fourier sampling and the black-box approach. Throughout the paper, we highlight the mathematical notions required and exploited in this context, providing a cryptography-oriented perspective.

Related papers

• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP [0.25956507689419356]
  We present an algorithm that solves the non-abelian StateHSP over $N$ copies of the dihedral group of order $8$ (the symmetries of a square)<n>This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy.
  arXiv  Detail & Related papers  (2025-10-09T07:23:53Z)
• The hidden subgroup problem for infinite groups [0.0]
  We show that HSP is NP-hard for the additive group of rational numbers, and for normal subgroups of non-abelian free groups.<n>We generalize the ShorKitev algorithm for HSP in $mathbbZk$ with standard query cost.<n>It follows that HSP in any finitely generated, virtually abelian group also has a stretched exponential time algorithm.
  arXiv  Detail & Related papers  (2025-07-24T15:16:20Z)
• On the privacy of federated Clustering: A Cryptographic View [2.209921757303168]
  Many privacy-preserving clustering algorithms leverage cryptographic techniques like homomorphic encryption or secure multiparty computation to guarantee full privacy. This paper delves into this intricate trade-off, questioning the necessity of continuous encryption in iterative algorithms. We show that existing lattice-based HSSP attacks fail in reconstructing the private data given the knowledge of intermediate centroids, thus it is secure to reveal them for the sake of efficiency.
  arXiv  Detail & Related papers  (2023-12-13T09:04:14Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Polynomial-time quantum algorithm for solving the hidden subgroup problem [0.0]
  The hidden subgroup problem(HSP) is one of the most important problems in quantum computation. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum algorithm.
  arXiv  Detail & Related papers  (2022-04-07T08:50:50Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
  The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete discrete problem, graph isomorphism, and the shortest vector problem.
  arXiv  Detail & Related papers  (2020-01-30T13:09:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.