Thesis
The 'next Shor in cryptanalysis' is not one algorithm but a family of attacks on the post-quantum crypto problems Shor doesn't break: lattices (LWE, NTRU), isogenies (CSIDH), and the dihedral hidden subgroup problem. Regev's 2023 reduction of factoring to a small number of d-dimensional lattice instances cuts the asymptotic qubit cost of Shor itself; Kuperberg's subexponential dihedral HSP algorithm threatens isogeny-based schemes; and a wave of 2024–2026 LWE quantum attack claims (some withdrawn, some standing) keeps the lattice question genuinely open. Unlike a unifying meta-framework, this axis is bet on a single decisive cryptanalytic event — a polynomial-time quantum attack on LWE or Module-LWE would be a true second Shor-moment.
Scoring
Highest dequantization resilience by definition — cryptanalytic problems are adversarial. Speedup is real (Regev compresses Shor's qubit cost; Kuperberg breaks dihedral HSP), but breadth is narrow: each result targets one cryptosystem. Traction tempered by the Chen 2024 withdrawal showing how fragile lattice claims remain.
Open problems
- ·Polynomial-time quantum algorithm for LWE / Module-LWE (Chen 2024 withdrawn).
- ·Beating Kuperberg's 2^O(√log N) bound for dihedral HSP — sub-polynomial attack on CSIDH.
- ·End-to-end resource estimate for Regev's algorithm on RSA-2048 with realistic decoders.
- ·Quantum attacks on Module-LWE structured ideals beyond search-LWE.
- ·Concrete quantum sieves outperforming classical BKZ on cryptographic lattice dimensions.
Demo · pre-computed on the Selene emulator
QFT spectral fingerprint (Shor toy)
3-qubit QFT applied to a period-2 superposition. Peaks at the binary representations of N/r expose the hidden period — the same fingerprint Shor extracts in order-finding. Full RSA-2048 needs ~6000 logical qubits (Gidney–Ekerå) or ~1700 with Regev's 2023 variant.
Key papers (8)
arXiv:2308.06572Cuts qubit count of Shor-style factoring of n-bit integers from O(n) to O(√n · log n) by reducing to a small number of d-dimensional lattice instances — first major asymptotic improvement on Shor in 30 years.
arXiv:2310.00899Practical follow-up to Regev: makes the lattice step explicit and noise-robust, with concrete resource estimates competitive with Gidney–Ekerå for RSA-2048.
arXiv:1702.00249Reference variant powering most concrete RSA resource estimates — shortens the quantum register from 2n to ~n/2 bits for short-exponent RSA.
arXiv:1905.09749Canonical FT resource estimate for Shor on RSA-2048 — yardstick every post-Shor proposal compares against.
arXiv:quant-ph/0302112Solves dihedral HSP in 2^O(√log N) — the closest existing 'second Shor'. Concretely weakens CSIDH (Peikert/Bonnetain–Schrottenloher show CSIDH-512 has only ~62 bits of quantum security).
arXiv:ePrint 2024/555April 2024 claim of polynomial-time quantum LWE attack; withdrawn within two weeks after a fatal flaw in Gaussian phase-estimation was found (ePrint 2024/583). NIST PQC standards considered unaffected — but the episode shows how live the lattice question is.
arXiv:2105.05608Best known quantum SVP sieve: 2^{0.2570d} vs Laarhoven's 2^{0.2653d}. Erodes — but does not eliminate — concrete security margins of lattice schemes.
arXiv:0812.0380Canonical survey of quantum algorithms with superpolynomial speedup via the HSP framework — defines the theoretical boundary of Shor-like attacks.