Consequences of a quantum break of the dihedral coset problem examined
Beyond LWE: Post-Quantum Assumptions under a Counterfactual Break of the Dihedral Coset Problem
Cryptography and Security
Summary
Solving a problem called the Dihedral Coset Problem efficiently with a quantum computer could impact many assumptions in cryptography. This paper surveys what would happen if such a breakthrough were real, comparing many cryptographic assumptions and highlighting which would be affected. The authors also clarify different solver types and how current cryptographic systems relate to them. They examine some withdrawn or unverified quantum algorithms and summarize how certain classical attacks affect cryptosystems like Classic McEliece. The survey closes with open questions and scenarios for future research.
What this means in practice
- •For cryptography engineers: Prepare for potential quantum breakthroughs by understanding which lattice assumptions might fail and how that impacts scheme security.
- •For security protocol designers: Assess and adjust post-quantum algorithm choices considering detailed surveys of quantum solver hypotheses and classical attacks.
A survey. It maps existing work.
Authors
Ramses Fernandez
Abstract
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.