A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below $1/2$, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.
A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below 1/2, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.
The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems.
In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let ζp be a primitive p-th root of unity, let π=ζp−1, and write q=pt and L=t(p−1). We work over Rq=Zq[ζp]≅Z[ζp]/(πL), where the isomorphism follows from the total ramification identity (p)=(π)p−1. We exploit the resulting π-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo πL,πL−1,…,π. For every fixed prime p and modulus q=pt, our algorithm solves the CCP in time and sample complexity 2Op(lognlogq), using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when q=poly(n). This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting.
However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.
Background: The imminent threat posed by cryptographically relevant quantum computers to classical public-key infrastructure specifically RSA and Elliptic-Curve Cryptography (ECC), whose security rests on the conjectured computational intractability of integer factorisation and the discrete logarithm problem respectively has propelled lattice-based cryptography to the centre of global post-quantum standardisation efforts. On 13 August 2024, the United States National Institute of Standards and Technology (NIST) published three landmark Federal Information Processing Standards (FIPS): FIPS 203 (ML-KEM, derived from CRYSTALS-Kyber), FIPS 204 (ML-DSA, derived from CRYSTALS-Dilithium), and FIPS 205 (SLH-DSA, derived from SPHINCS+), with FIPS 206 (FN-DSA, derived from FALCON) in advanced draft. The first three of these standards rest on algebraic structures intimately connected to classical number theory: polynomial rings over integer quotients, cyclotomic fields, and the algebraic geometry of ideal lattices in rings of integers of number fields. Objectives: This article provides: (1) a rigorous mathematical exposition of the lattice problems underpinning NIST’s post-quantum standards, specifically the Learning With Errors (LWE), Ring-LWE (RLWE), Module-LWE (MLWE), Short Integer Solution (SIS), and NTRU problems, and their connections to algebraic number theory; (2) a comparative performance analysis of NIST-standardised lattice-based algorithms against classical RSA and ECC benchmarks; (3) a security analysis examining known classical and quantum attacks on each hard problem; (4) a comparative evaluation of the four NIST-selected algorithms across key size, signature size, and computational benchmarks; and (5) a strategic assessment of the migration challenges facing deployed cryptographic infrastructure. Methods: The study synthesises peer-reviewed literature, NIST official standards documentation (FIPS 203, 204, 205, and draft FIPS 206), and independently published performance benchmarks published between June 2024 and June 2026. Mathematical security analysis is grounded in the worst-case to average-case reductions established by Regev (2005) for LWE and by Lyubashevsky, Peikert, and Regev (2013) [11, 18] for Ring-LWE. Performance data are drawn from Garani (2024) [8], the ARM Cortex-M0+ benchmarking study of Ratnayaka and Fischer (2026) [4], and the cross-platform evaluation by Alzahrani et al. (2025) [2]. Results: NIST’s three August 2024 standards establish a comprehensive lattice-based post-quantum portfolio. ML-KEM-768 produces a 1,184-byte public key and 1,088-byte ciphertext, achieving IND-CCA2 security under the MLWE assumption at NIST Level 3 (AES-192 equivalent). ML-DSA-65 produces 1,952-byte public keys and 3,309-byte signatures under the Module-LWE and Module-SIS assumptions at Level 3. FN-DSA-512 (FALCON, draft FIPS 206) produces 897-byte public keys and 666-byte signatures under the NTRU assumption, offering the most compact lattice-based signatures. Performance benchmarks on an Intel Core i7-12700K (3.6 GHz) confirm that ML-KEM key generation is orders of magnitude faster than RSA-3072 key generation. The algebraic structure of cyclotomic polynomial rings ∑₂ⁿ = Z[x]/(x^n + 1) is central to the efficiency of all three lattice-based NIST standards. Conclusion: Lattice-based cryptography, grounded in the algebraic number theory of ideal lattices over cyclotomic fields, provides the most comprehensive and mathematically well-founded response to the quantum computational threat. The August 2024 NIST standardisation of ML-KEM, ML-DSA, and SLH-DSA represents a landmark in cryptographic history, and the imminent finalisation of FN-DSA will complete the post-quantum toolbox. Organisations should prioritise immediate migration planning, leveraging hybrid classical-quantum schemes during transition, with full transition to NIST post-quantum standards recommended by 2030 per NSA and CISA guidance.
We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower n−1 bits of the subset sum, the algorithm discards any ω(logn) bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP.
As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.
Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.
The first generation of post-quantum cryptographic standards from the U.S. National Institute of Standards and Technology (NIST) rests on one mathematical foundation. Three of the four schemes standardized or in development, ML-KEM, ML-DSA, and FN-DSA, rest on the hardness of finding short vectors in structured lattices, while only SLH-DSA departs from it; the first two use Module Learning With Errors (Module-LWE) and the third the related but distinct NTRU assumption. This paper examines that concentration as a systemic risk. Drawing on the computer-security literature on software monoculture and design diversity, it argues by analogy that algorithmic homogeneity creates conditions for correlated failure of much deployed public-key cryptography. It makes the mechanism concrete: the security of all three schemes is estimated under one lattice-reduction cost model, so a sufficiently general advance in lattice reduction could move their security margins together while the non-lattice options stay untouched, as a cross-family correlation matrix and a sensitivity analysis show. It then separates three hazards often conflated in the debate, transition risk, assumption-monoculture risk, and implementation risk, and shows that the classical-plus-lattice hybrids now carrying most post-quantum Web traffic hedge the first but not the second. The claim is one of risk management, not mathematical certainty: no standardized lattice scheme is broken at its parameters as of mid-2026, and Module-LWE enjoys strong worst-case-to-average-case reductions. The case for diversification rests on the irreducible uncertainty of cryptanalysis, the fragility of implementation security, and the severe, potentially unrecoverable cost of a correlated failure.
We revisit the post-processing phase of Chen's Karst-wave quantum lattice algorithm (Chen, 2024) in the Learning with Errors (LWE) parameter regime. Conditioned on a transcript E, the post-Step 7 coordinate state on (ZM)n is supported on an affine grid line {jΔ+v∗(E)+M2kmodM:j∈Z,k∈K}, with Δ=2D2b, M=2M2=2D2Q, and Q odd. The amplitudes include a quadratic Karst-wave chirp exp(−2πij2/Q) and an unknown run-dependent offset v∗(E). We show that Chen's Steps 8-9 can be replaced by a single exact post-processing routine: measure the deterministic residue τ:=X1modD2, obtain the run-local class v1,Q:=v1∗(E)modQ as explicit side information in our access model, apply a v1,Q-dependent diagonal quadratic phase on X1 to cancel the chirp, and then apply QFTZM⊗n to the coordinate registers. The routine never needs the full offset v∗(E). Under Additional Conditions AC1-AC5 on the front end, a measured Fourier outcome u∈ZMn satisfies the resonance ⟨b,u⟩≡0(modQ) with probability 1−o(1). Moreover, conditioned on resonance, the reduced outcome umodQ is exactly uniform on the dual hyperplane H={v∈ZQn:⟨b,v⟩≡0(modQ)}.