CSIDH: Commutative Supersingular Isogenies

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck et al., 2018) is an isogeny-based key exchange that avoids the SIDH torsion-point leakage entirely by using a fundamentally different algebraic structure. CSIDH works with supersingular curves over Fp (not Fp2 as in SIDH). The hardness assumption is the commutativity of the class group action: two parties each apply a secret class group element to a common starting curve, and commutativity ensures both arrive at the same shared curve. No auxiliary torsion point information is published — the public key is just a single j-invariant. This design survived the Castryck-Decru attack on SIDH.

Over Fp with p = 3 mod 4, the supersingular curves E have a distinguished endomorphism pi (the Frobenius), and their endomorphism algebra contains the imaginary quadratic order Z[pi]. The ideal class group Cl(Z[pi]) acts freely and transitively on the set of supersingular curves over Fp (up to isomorphism). An ideal a in Cl(Z[pi]) acts on a curve E to produce a new curve a * E, computed as the curve E/E[a] where E[a] is the torsion subgroup corresponding to ideal a. This action is commutative: a * (b * E) = b * (a * E) = [ab] * E. This is the CSIDH group action, providing a commutative analog of Diffie-Hellman.

CSIDH key exchange proceeds as follows. Public parameters: a supersingular curve E0 over Fp and small odd primes l_1, ..., l_n. Secret keys: Alice picks a = (a_1, ..., a_n) with each a_i in {-m, ..., m} (random small integers). Bob picks b = (b_1, ..., b_n). Alice's public key: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Bob's public key: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Shared secret: Alice applies her secret exponents to E_B; Bob applies his to E_A. Commutativity ensures both get E_AB = [product(l_i^(a_i + b_i))] * E0. The shared secret is j(E_AB). No auxiliary points are published.

The reference CSIDH implementation uses p = 4 * l_1 * l_2 * ... * l_74 - 1 where l_1 through l_74 are the first 74 odd primes (3, 5, 7, ..., 373). This gives p of approximately 512 bits. Each secret key component a_i is in {-5, ..., 5} (11 choices per component, 74 components). The class group order is approximately sqrt(p), and the keyspace has size 11^74. Computing each isogeny step: for each prime l_i, find the l_i-torsion subgroup and compute the l_i-isogeny using Velu's formulas. With sqrt-Velu, each large prime isogeny step takes O(sqrt(l_i)) operations. Total key exchange: approximately 1-5 ms on modern hardware for CSIDH-512.

The original CSIDH is not constant-time: the number of Velu steps depends on the secret key values a_i, leaking information via timing side channels. CTIDH (Constant-Time ISOGENY Diffie-Hellman, Bernstein et al., 2021) fixes this by using a fixed-weight key format and carefully designed constant-time isogeny computation. CTIDH secret keys are restricted to vectors where the sum of absolute values is fixed (e.g., sum |a_i| = 130). The isogeny computation proceeds in a fixed number of steps regardless of the secret key values, using dummy isogeny computations to fill steps where the secret exponent is zero. CTIDH achieves similar security to CSIDH-512 with strict constant-time guarantees suitable for embedded deployments.

The quantum security of CSIDH is more nuanced than for lattice-based schemes. The best quantum attack uses Kuperberg's algorithm (2005) for the hidden shift problem, which breaks the class group action structure in subexponential time L(1/2) = exp(O(sqrt(log p))). This is substantially better than the sqrt(p) classical best attack, meaning quantum computers significantly weaken CSIDH compared to classical attackers. For 128-bit post-quantum security (against L(1/2) attack), CSIDH requires a prime p of approximately 5000 bits (CSIDH-5000) — compared to 512 bits for 128-bit classical security. CSIDH-512 is estimated at only 62-72 bits of quantum security, well below NIST Level 1 requirements.

CSIDH's security relies on the Group Action Inverse Problem (GAIP): given E_A = a * E0 and E0, find a. The best known algorithm is Pohlig-Hellman-like reduction combined with baby-step-giant-step, running in O(sqrt(|Cl|)) ~ O(p^{1/4}) classically. The quantum hardness (Kuperberg) makes CSIDH less quantum-secure than LWE-based schemes. LWE's best quantum attack (lattice sieving) provides more conservative security margins. CSIDH's advantage is its compactness: CSIDH-512 has 64-byte public keys (just j-invariant), versus ML-KEM-512's 800 bytes. For applications requiring the smallest possible keys and accepting lower quantum security margins, CSIDH remains interesting.

Several CSIDH variants address its quantum security limitations. BSIDH (B for "better") uses higher-degree base curves and products of elliptic curves to increase the class group size while keeping computation fast. Csurf (CSIDH on the surface) works with a different set of supersingular curves to enable faster group action computation. Higher-genus CSIDH proposals use Jacobians of genus-2 curves over Fp, providing a larger group action space with potentially better quantum security margins. None of these variants have achieved widespread adoption or NIST consideration, partly because the quantum security analysis of CSIDH variants is still evolving and less mature than for lattice-based schemes.

CSIDH and SIDH differ in fundamental ways. Commutativity: CSIDH uses a commutative group action (class group); SIDH is non-interactive key exchange using non-commutative isogenies with auxiliary torsion points. Base field: CSIDH works over Fp; SIDH over Fp2 (quadratic extension). Public key size: CSIDH is 64 bytes (single j-invariant over Fp); SIDH is 324+ bytes (curve + two Fp2 points). Security: CSIDH survived the Castryck-Decru attack; SIDH was broken. Quantum security: CSIDH requires 5000-bit primes for 128-bit quantum security; SIDH had comparable quantum resistance before the classical break. Performance: CSIDH-512 is ~1-5 ms; SIDH was similar but CSIDH-5000 would be much slower.

CSIDH's commutativity enables non-interactive key exchange (NIKE): Alice publishes E_A = a * E0; Bob publishes E_B = b * E0. Later, without any further communication, anyone can compute the shared secret from either public key: Alice computes a * E_B = a * (b * E0) = ab * E0; Bob computes b * E_A = b * (a * E0) = ab * E0. This NIKE property is valuable for applications where interactive key exchange is impractical — for example, email encryption where sender and recipient are not online simultaneously. NIKE from CSIDH is analogous to Diffie-Hellman NIKE but post-quantum. ML-KEM (based on LWE) does not naturally support NIKE without additional protocol design.

CSIDH has not been standardized and is not yet deployed in production systems. It is an active research topic with implementations available: CTIDH (constant-time), csidh-reference (Python, for pedagogy), and supersingular-isogeny-toolbox (optimized C). The primary barrier to deployment is quantum security: CSIDH-512's estimated 62-72 bits of quantum security falls below NIST Level 1 (128 bits), making it unsuitable for post-quantum applications requiring NIST compliance. CSIDH-5000 would meet the security bar but would be dramatically slower. Research continues on improving the quantum security analysis and on variants that close the gap, but CSIDH remains a research prototype rather than a deployment-ready primitive as of 2024.

Why does CSIDH's commutative class group action enable non-interactive key exchange?

CSIDH uses the commutative class group action of Cl(Z[pi]) on supersingular curves over Fp, where pi is the Frobenius endomorphism. Public keys are single j-invariants (64 bytes). No auxiliary torsion points are published, avoiding the SIDH vulnerability. The class group action is commutative, enabling NIKE. Best classical attack is O(p^{1/4}); best quantum attack (Kuperberg) runs in subexponential L(1/2) time, requiring 5000-bit primes for 128-bit quantum security. CTIDH provides constant-time implementation. CSIDH-512 has only ~65 bits of quantum security. CSIDH is not standardized; research focuses on variants improving quantum resistance while maintaining compact keys.