CSIDH
Every other post-quantum key exchange is a key encapsulation: one side sends a ciphertext to the other. CSIDH is a drop-in replacement for Diffie–Hellman instead, with static public keys that anyone can combine without interaction. That property comes from a commutative group action, and the same commutativity is what gives quantum computers a subexponential attack on it.
- Rests on
- Inverting a commutative class-group action on supersingular curves over Fp
- Standards
- None; a research scheme
- Sizes
- CSIDH-512: 64-byte public keys
- Best known attack
- Classically about p1/4; quantumly, Kuperberg's subexponential algorithm, whose concrete cost is disputed
- Toy example here
- p = 419: 27 curves in one orbit, equal to the class number h(−4p) = 27
A group acting on curves
Diffie–Hellman works because exponentiation commutes: (ga)b = (gb)a. CSIDH, by Castryck, Lange, Martindale, Panny and Renes, gets the same property from a group action. The set is the supersingular elliptic curves defined over Fp whose endomorphism ring is Z[√−p], written as Montgomery curves y2 = x3 + Ax2 + x and identified by the single number A. The group is the class group of Z[√−p]. It acts by isogenies: an ideal of norm ℓ sends a curve to its image under an isogeny of degree ℓ, and the group is commutative, so the order of the steps does not matter.
The prime is chosen as p = 4·ℓ1···ℓn − 1 for small odd primes ℓi. Then every such curve has p + 1 points, so points of order ℓi exist over Fp and each step can be computed with Vélu's formulas on rational points. A step in the direction of the ideal li uses a point on the curve, and a step in the direction of its inverse uses a point on the quadratic twist.
A key exchange with p = 419
The paper's toy example uses p = 4·3·5·7 − 1 = 419, with the ideals above 3, 5 and 7. The code that builds this page implements the paper's evaluation algorithm, with x-only Montgomery arithmetic and odd-degree Vélu formulas, and runs a key exchange starting from the curve A = 0:
- Alice's secret is an exponent vector a = (2, 2, -1): apply the ideal above 3 twice, the one above 5 twice, and the inverse of the one above 7 once. Starting from A = 0 this gives her public curve A = 275.
- Bob's secret is b = (0, 2, 2), and his public curve is A = 191.
- Alice applies a to Bob's curve and Bob applies b to Alice's. Both arrive at A = 158, the shared secret.
The build checks the implementation three ways. Applying the negated vector to Alice's public curve returns A = 0. Every curve reached passes a supersingularity test: multiplying random points on the curve and on its twist by p + 1 gives the identity. And exploring every step from A = 0 reaches exactly 27 distinct curves. That is the class number h(−4p) = 27, which the build counts independently from reduced quadratic forms. An action of a group of order 27 that reaches 27 curves is acting freely and transitively, as the theory says it must.
The toy also shows why exponent vectors are not the key space. With exponents in [−2, 2] there are 125 vectors but only 27 curves, so many vectors give the same public key. Real parameters choose the prime and the exponent range so that the vectors cover the class group roughly evenly.
Real parameters
CSIDH-512 uses the product of the first 74 odd primes, with 587 in place of the largest, giving a prime of 511 bits, and exponents in [−5, 5]. A public key is one element of Fp, 64 bytes, and validating that a received curve is supersingular is cheap, which is what makes static keys safe. Beullens, Kleinjung and Vercauteren later computed the full class group of CSIDH-512, which turned it into a signature scheme, CSI-FiSh, and let keys be sampled uniformly.
The cost is speed. A key exchange takes tens to hundreds of milliseconds, depending on how much the implementation pays for constant time, orders of magnitude slower than X25519 or ML-KEM, and constant-time implementation is harder than for other schemes because the number of isogeny steps depends on the secret.
Security, and the commutativity problem
Classically, recovering a secret means finding a path through the class group between two known curves. The best known attacks are meet-in-the-middle searches costing about p1/4, well beyond reach for CSIDH-512.
Quantum computers change this, and because of the very property that makes CSIDH useful. Recovering the key of a commutative group action is an instance of the abelian hidden shift problem, for which Kuperberg's algorithm runs in subexponential time. How large p must be for a given quantum security level has been argued in detail. Peikert, and Bonnetain and Schrottenloher, concluded independently in 2020 that CSIDH-512 falls well short of NIST level 1. Other teams have proposed much larger primes, of thousands of bits. The Kuperberg page covers the dispute.
CSIDH's curves are supersingular, but the attacks that broke SIDH needed torsion-point images that CSIDH never publishes, and they do not apply. For the non-commutative supersingular problems behind SQIsign no subexponential quantum algorithm is known.
Primary sources
- W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, "CSIDH: an efficient post-quantum commutative group action", ASIACRYPT 2018
- W. Beullens, T. Kleinjung and F. Vercauteren, "CSI-FiSh: efficient isogeny based signatures through class group computations", ASIACRYPT 2019
- C. Peikert, "He gives C-sieves on the CSIDH", EUROCRYPT 2020
- X. Bonnetain and A. Schrottenloher, "Quantum security analysis of CSIDH", EUROCRYPT 2020