Isogeny
Half the field collapsed classically in 2022. What survives is non-commutative, and Kuperberg can't reach it cleanly.
State of the art
The 2022 Castryck–Decru–Maino–Martindale–Robert classical attack demolished SIDH/SIKE in polynomial time via genus-2 isogenies and Kani's glue-and-split — no quantum computer needed. CSIDH, the surviving commutative scheme, encodes its secret as a hidden shift in Cl(𝒪_K) and is directly attackable by Kuperberg's sieve. Bonnetain–Schrottenloher 2018 (concrete cost analysis) found CSIDH-512 achieves only ~62 quantum-security bits, not the claimed 128; Peikert 2020 C-sieves tightened this further. Surviving non-commutative schemes (SQIsign, SQIsignHD) live in the genuinely non-abelian regime — no abelian group action is exposed in the verifier's view, so Kuperberg does not apply. Security rests on the endomorphism-ring problem, whose quantum hardness is open beyond trivial Grover.
Known dead ends (read first)
- ×Direct Shor / abelian-HSP attack on SQIsign or the endomorphism-ring problem — the supersingular isogeny graph is an expander with no known abelian group law on its vertices. — De Feo, Kohel, Leroux, Petit, Wesolowski ePrint 2020/1240
- ×Patched SIDH variants (FESTA, M-SIDH) — broken within months. The 'publish auxiliary torsion-point data' design paradigm appears structurally unfixable against Kani-type attacks. — Castryck et al. FESTA attack ePrint 2023/190
- ×Black-box quantum walks on the supersingular isogeny graph — achieves only O(p^{1/4}) query complexity (same as Grover) with large constants. No structural improvement beyond the quadratic barrier. — Childs–Jao–Soukharev arXiv:1012.4019
Open sub-problems
Tight T-gate and qubit count for Kuperberg's second sieve against CSIDH-512 class group Cl(ℤ[√−p]) — definitively close or widen the security gap with QEC-realistic accounting.
Lower bound Ω(p^{1/4}) on quantum queries for the endomorphism-ring problem via polynomial / adversary method, or conditional reduction from a well-studied quantum-hard problem.
Characterize SQIsign's signing-response distribution as a hidden-shift instance over a non-abelian group (wreath / affine); rule out or find efficient quantum algorithms for that class.
Paired donor analogies
Key papers
ia.cr/2018/383acceptedDefines CSIDH and packages the abelian HSP structure that makes Kuperberg directly applicable.
ia.cr/2018/537acceptedFirst rigorous concrete-cost analysis of Kuperberg/Regev against CSIDH-512: ~62 quantumbits of security, far below claimed 128. EUROCRYPT 2020.
ia.cr/2019/725acceptedC-sieve lattice techniques inside Kuperberg, tightening quantum attack costs against CSIDH.
ia.cr/2022/975acceptedCLASSICAL polynomial-time break of SIDH via Kani's theorem on abelian surfaces. EUROCRYPT 2023 Best Paper.
ia.cr/2022/1026acceptedExtends Castryck–Decru to arbitrary starting curves; subexponential complexity in the general case. EUROCRYPT 2023.
ia.cr/2022/1038acceptedCompletes the trilogy: full polynomial-time break for any starting curve via symplectic pairings on 2D abelian varieties.
ia.cr/2020/1240acceptedNon-commutative isogeny signature based on the Deuring correspondence. The survivor; immune to Kuperberg by construction.
ia.cr/2023/436acceptedRepurposes the SIDH-breaking higher-dimensional machinery as a signing primitive — faster SQIsign variant with cleaner reduction. EUROCRYPT 2024.