Kuperberg's algorithm and CSIDH

CSIDH was not broken. It was repriced, repeatedly, by analyses that disagree about what a quantum computer costs to run — and the disagreement is a more instructive object than either answer, because it is about cost models rather than about mathematics.

Scheme
CSIDH — commutative supersingular isogeny Diffie–Hellman
Underlying problem
Abelian hidden shift / group-action inversion
Classical cost
Õ(√|cl(O)|) ≈ p1/4, by meet-in-the-middle or random walk
Quantum cost
Subexponential: 2O(√log N) — not polynomial
Status
Unbroken; parameter sizes contested, CSIDH-512 widely considered insufficient
Not affected by
The SIDH torsion attacks — no torsion images are published

The structure CSIDH chose

CSIDH, introduced by Castryck, Lange, Martindale, Panny and Renes, works with supersingular elliptic curves defined over Fp rather than over Fp2. Restricting to the prime field makes the endomorphism ring commutative — an order O in an imaginary quadratic field — and its ideal class group then acts on the set of such curves, freely and transitively:

cl(O) × Ellp(O) → Ellp(O),  ([a], E) ↦ [a] · E A free, transitive group action — a torsor, not a group

That action commutes, so key exchange is the obvious thing: Alice publishes [a]·E0, Bob publishes [b]·E0, and both compute [a][b]·E0. Nothing else is transmitted — and that absence is why CSIDH survived the attacks that ended SIDH. The prize is real: very small public keys, and genuine non-interactive key exchange, which no lattice-based KEM provides.

The price is the same commutativity. A group action whose group is abelian is precisely the setting of the abelian hidden shift problem, and that problem has a subexponential quantum algorithm.

The mechanism

Recovering Alice's secret from [a]·E0 means inverting the group action. Define two functions on the group, one built from E0 and one from [a]·E0; they are equal up to a shift by the unknown [a]. Finding that shift is the abelian hidden shift problem, and Kuperberg gave a quantum sieve for it running in

2O(√(log N)) quantum queries and time, for a group of order N Subexponential — between Grover's √N and Shor's polynomial time

The sieve prepares many phase-encoded states over the group and combines them pairwise, each combination concentrating the unknown shift into fewer, more useful bits, until the shift can be read out. Regev gave a variant using polynomial quantum space at somewhat greater time; Kuperberg's second algorithm improved the tradeoff again. The important structural point is what the algorithm is not: it is not Shor. Commutativity is enough for a subexponential quantum attack and not enough for a polynomial-time one, which is exactly the narrow ledge CSIDH stands on.

Classically the picture is unremarkable. Inverting the action is a search over the class group, done by meet-in-the-middle or a random-walk collision search in Õ(√|cl(O)|), which for CSIDH parameters is about p1/4. Classical security therefore scales the way generic attacks always do.

The dispute

The exponent is agreed. What is contested is the constant, the query count, and above all what a quantum query costs — and at subexponential asymptotics those decide everything at real parameter sizes.

  • The original proposal offered CSIDH-512 as a NIST level 1 parameter set, on an analysis of Kuperberg-style attacks available at the time.
  • Peikert gave a concrete analysis of the collimation sieve applied to CSIDH and concluded that CSIDH-512 falls well short of that claim — that the quantum work is far smaller than the proposers had estimated.
  • Bonnetain and Schrottenloher reached similarly reduced security estimates by a different route.
  • Bernstein, Lange, Martindale and Panny costed the quantum circuits for evaluating the group action in detail, arguing that the per-query cost of a real implementation is high enough to change the conclusion substantially.
  • Chávez-Saab, Chi-Domínguez, Jaques and Rodríguez-Henríquez took the conservative branch and showed that much larger parameters — CSIDH-4096 and beyond — remain implementable, if slower.

The disagreement is not about the mathematics. It is about the cost model: whether quantum random access memory is free or expensive, whether an attack is allowed unbounded circuit depth or must fit within a realistic time limit, and how much error-correction overhead a long-running quantum computation carries. Different defensible answers to those questions produce security estimates that differ by tens of bits.

The practical consequence today is a consensus that CSIDH-512 is not a level 1 parameter set, and disagreement about exactly how much larger is enough. CSIDH is not a NIST candidate and is not deployed at scale; it remains an active research object, valued for the non-interactive key exchange that nothing else in the post-quantum portfolio offers.

The boundary

Kuperberg's algorithm needs the group to be abelian. That single hypothesis partitions the isogeny landscape cleanly:

  • CSIDH and CSI-FiSh use a commutative class-group action, so the attack applies and sets their quantum parameters.
  • SIDH and SIKE used the non-commutative supersingular graph over Fp2, so Kuperberg never applied to them — they fell to something else entirely, the torsion-point attacks.
  • SQIsign is likewise non-commutative, resting on the endomorphism-ring problem via the Deuring correspondence. Kuperberg does not reach it.
  • The general supersingular isogeny path problem over Fp2 has no known subexponential quantum attack. Classically, Wesolowski's 2026 algorithm brought the best exponent from p1/2 to p1/3+o(1) in both time and memory; quantum claw-finding bounds of the same shape exist, but only as query counts in idealised models with free quantum memory.

Read the two isogeny pages in this library together and the trade is explicit. SIDH published extra data to make its non-commutative walk usable, and the extra data is what killed it. CSIDH needs no extra data because commutativity does that work — and commutativity is what exposes it to Kuperberg. Each scheme paid for its key exchange in a different currency, and the community found out what each price was, in one case abruptly and in the other by a decade of argument that is still running.

Primary sources

  1. W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, "CSIDH: an efficient post-quantum commutative group action", ASIACRYPT 2018
  2. G. Kuperberg, "A subexponential-time quantum algorithm for the dihedral hidden subgroup problem", SIAM J. Comput. 35 (2005)
  3. G. Kuperberg, "Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem", TQC 2013
  4. C. Peikert, "He gives C-sieves on the CSIDH", EUROCRYPT 2020
  5. X. Bonnetain and A. Schrottenloher, "Quantum security analysis of CSIDH", EUROCRYPT 2020
  6. D. J. Bernstein, T. Lange, C. Martindale and L. Panny, "Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies", EUROCRYPT 2019
  7. J. Chávez-Saab, J.-J. Chi-Domínguez, S. Jaques and F. Rodríguez-Henríquez, "The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents", JCEN 12 (2022)
  8. B. Wesolowski, "The supersingular isogeny problem in time and memory p1/3+o(1)" (2026)