Dihedral / non-abelian HSP
The structural cousin of Shor that has resisted polynomial-time quantum attack for 25 years.
State of the art
Kuperberg's 2003 sieve solves the dihedral HSP in 2^O(√log N) quantum queries and time; Regev's 2004 variant trades query count for polynomial quantum space; Kuperberg's 2011 'second algorithm' improves space further to O(log N) quantum / exp(O(√log N)) classical without moving the asymptotic exponent. Despite two decades of effort, the 2^O(√log N) wall has not been breached. The Brakerski–Kirshanova–Stehlé–Wen 2017 EDCP↔LWE equivalence sharpens Regev's 2003 dihedral→uSVP reduction: poly-time DHSP would imply poly-time LWE, breaking every NIST lattice standard (ML-KEM, ML-DSA, Falcon). The Bacon–Childs–van Dam 2005 density threshold ν = k / log₂ N > 1 pins down why polynomial sample complexity is impossible under standard Fourier sampling.
Known dead ends (read first)
- ×Standard / strong Fourier sampling on dihedral coset states — provably insufficient even with polynomially many copies under the optimal Pretty Good Measurement. — Moore–Russell–Schulman 2008 (quant-ph/0501056); Bacon–Childs–van Dam 2005 (quant-ph/0501044)
- ×Hidden subgroup over the symmetric group via non-abelian representation theory — the optimal measurement is #P-hard classically to describe. — Hallgren–Russell–Ta-Shma 2003 (cs/0205040)
- ×Polynomial-time DCP with smooth modulus — WITHDRAWN from IACR ePrint after the author found a fatal flaw in the quantum state discrimination step. — Doliskani ePrint 2021/419 (WITHDRAWN)
- ×Wang 2022 'multistep quantum computation' claim of poly-time non-abelian HSP — five revisions, no top-venue acceptance, not endorsed by community. — arXiv:2204.03295 (contested / unverified)
Open sub-problems
Windowed coset combination under a structured promise on Z_{2^k}: derive a 2-adic concentration lemma showing that label distributions after j sieve rounds admit a √log N → (log N)^{1/3} improvement in a restricted regime (binary lattices, NTRU-style moduli).
Sharp Pareto frontier for rounds r vs initial coset count k(r) at fixed success probability — model the sieve as a branching random walk over Z_N and apply optional stopping. First concrete resource-estimate table for quantum hardware groups.
Direct worst-case-to-DCP Turing reduction (not many-one) for a restricted lattice family (e.g. q-ary), strengthening Chia–Hallgren 2016 and the BKSW 2017 LWE equivalence.
Paired donor analogies
Key papers
quant-ph/0302112acceptedFounding sieve: 2^O(√log N) queries via coset-state combination. The benchmark every subsequent attempt is measured against.
quant-ph/0406151acceptedPolynomial quantum space variant — the modification that made Kuperberg's sieve physically plausible and raised CSIDH urgency.
1112.3333acceptedSecond-generation sieve: O(log N) quantum space, exp(O(√log N)) classical space. Same asymptotic exponent, better constants.
cs/0304005acceptedEstablishes the dihedral-HSP → poly(n)-uSVP reduction. The cryptographic stakes; one-way, gives no attack.
quant-ph/0501044acceptedProves PGM is optimal for DHSP and identifies the sharp density threshold ν = k/log₂N > 1 — quantifies why coset accumulation is hard.
quant-ph/0501056acceptedRules out polynomially many coset-state copies under strong Fourier sampling for dihedral and symmetric groups.
1710.08223acceptedTightens Regev: LWE is quantum-poly equivalent to the Extrapolated Dihedral Coset Problem. Direct link from DHSP hardness to ML-KEM / ML-DSA security.
1608.02003acceptedHardness for decision-DCP: random subset sum with density > 1 reduces to it. Decision-DCP hardness ↔ average-case lattice hardness.
0812.0380acceptedAuthoritative survey of non-abelian HSP status; the gap between query complexity (polynomial) and computational complexity (subexponential) for dihedral.
2503.06478preprint2025 distributed reformulation. No asymptotic improvement but illuminates the communication bottleneck in multi-node coset combination.