Lattice / LWE
Where every NIST post-quantum standard rests, and where the last serious quantum attack visibly failed at extraction, not preparation.
State of the art
Best known quantum sieve for SVP is 2^(0.2570 n + o(n)) (Chailloux–Loyer 2021 via quantum random walks on Johnson graphs), tightened by Bonnetain–Chailloux–Schrottenloher–Shen 2023 (reusable quantum walks) and pushed slightly further into 3-tuple sieving by Engelberts et al. 2025. Classical baseline (BDGL 2016) is 2^(0.2920 n) — a modest ~10% exponent gap. Cho et al. 2024 prove the gap requires poly(n) QRAM; in a circuit-only model, no super-constant quantum advantage over classical sieve currently survives. Regev's 2005 quantum reduction runs in the hardness direction (GapSVP →_Q LWE) and is not an attack. Chen's April 2024 attempt (ePrint 2024/555) at a polynomial-time quantum LWE algorithm was withdrawn within a week; the surgical post-mortem (Hongxun Wu + Thomas Vidick, April 18 2024) located the bug in Step 9 / Section 3.5.9: the state exiting Step 8 is globally entangled, breaking the product-state assumption Step 9 needs. Steps 1–8 (complex Gaussian prep + windowed QFT) were not refuted and may contain salvageable primitives.
Known dead ends (read first)
- ×Chen 2024 Step 9 extraction loop — the state exiting Step 8 is globally entangled across the LWE secret coordinates; the iterative single-bit measurement collapses the joint state and destroys the bootstrap. — Chen ePrint 2024/555 §3.5.9 (WITHDRAWN); post-mortem Hongxun Wu & Thomas Vidick, 2024-04-18
- ×Eldar–Shor 2016 polynomial-time quantum lattice algorithm — flaw found by Regev within days, paper abandoned. Direct precedent for Chen 2024. — arXiv:1611.06999 (Eldar–Shor 2016, withdrawn/abandoned)
- ×DHSP route to polynomial-time LWE — 20+ years of effort hit the 2^O(√n) sieve wall; complexity evidence suggests DHSP is not in BQP. — Kuperberg quant-ph/0302112; Regev quant-ph/0406151
- ×Pure Grover-over-enumeration — gives only quadratic speedup, easily absorbed by parameter increase. — Laarhoven 2016 thesis; Aono–Nguyen–Shen 1709.01411
- ×Variational / QAOA approaches to SVP/CVP — NISQ heuristics with no proven exponential speedup and no convergence guarantees in high dimensions. — arXiv:2503.08403; arXiv:2505.08386
- ×Quantum sieve speedup without QRAM — proven to require poly(n)-width QRAM; in a circuit-only model the 0.265 vs 0.292 advantage vanishes. — Cho, Hhan, Kim, Lee, Shen arXiv:2410.15565
Open sub-problems
Rescue a narrow case of Chen's Step 9 for structured moduli (power-of-two cyclotomic / q = p^k with small p): formalize what algebraic condition on the post-Step-8 state would permit ring-aware single-coordinate measurement; check Ring-LWE.
QRAM-free quantum speedup for the dual attack via quantum rejection sampling on the lattice Gaussian sampling bottleneck — adapt sequential-query rejection sampling to the Klein/GPV sampler.
Tight quantum reduction from GapSVP_{√n·polylog(n)} to LWE — sharper Gaussian tail analysis inside Regev's dual-lattice sampling, shaving a polynomial factor and closing the dark zone around Kyber/Dilithium parameters.
Paired donor analogies
Key papers
2401.03703acceptedThe keystone. Quantum worst-case-to-average-case reduction GapSVP/SIVP →_Q LWE; a security argument, not an attack — flows in the wrong direction for the attacker.
ia.cr/2024/555withdrawnWITHDRAWN. Flaw at Step 9 / §3.5.9 — entangled state breaks the product-state assumption needed for iterative bit extraction. Hongxun Wu and Thomas Vidick identified the bug on 2024-04-18.
2105.05608acceptedQuantum walk on the Johnson graph over sieve lists. Current asymptotic frontier: 2^(0.2570 n) for SVP. Requires QRAM.
2205.14023acceptedReusable quantum walks amortize setup across many near-neighbor pairs. Matches / slightly improves the 0.265 barrier. EUROCRYPT 2023.
2510.08473preprintExtends reusable quantum walks to 3-tuple sieving — current frontier of quantum SVP algorithms, pushes slightly below 0.2570 n.
2410.15565preprintProves the leading quantum sieve speedups require poly(n) QRAM; without QRAM the quantum advantage over classical sieve vanishes. Critical caveat for real-world security estimates.
2205.13983acceptedQuantum speedup for the dual attack via QRACM; can outperform pure primal-sieve in some NIST PQC parameter regimes. CRYPTO 2022.
2308.06572preprintCuts Shor's gate count to Õ(n^{3/2}) by offloading CVP post-processing classically. Directly links lattice hardness to quantum factoring cost.
ia.cr/2015/939acceptedCanonical survey. Read before claiming any 'obvious' quantum attack — most have been tried.