Elliptic Curve Isogenies: Mathematical Foundation

An isogeny between two elliptic curves E and E' over a field k is a non-constant rational map phi: E -> E' that is also a group homomorphism — it maps the group law of E to the group law of E'. Every isogeny phi has a dual isogeny phi_hat: E' -> E such that phi_hat composed with phi equals multiplication-by-deg(phi) on E. The degree of an isogeny is the size of its kernel: a degree-l isogeny has a kernel of size l. Isogenies generalize scalar multiplication: multiplication by n is an isogeny from E to itself of degree n^2. Isogenies over finite fields are computed as rational functions (polynomials) that can be evaluated efficiently.

Velu's formulas (1971) provide explicit formulas for computing an isogeny phi: E -> E/G given a subgroup G of E. The image curve E/G = E' and the rational map phi are completely determined by G. Velu's formulas compute the image curve coefficients and the rational map as rational functions of degree equal to |G|. For a kernel subgroup G of prime order l, the isogeny has degree l and can be computed in O(l) operations. sqrt-Velu algorithms (Bernstein et al., 2019) reduce this to O(sqrt(l)) operations for large l, enabling CSIDH's efficient large-prime isogenies. Velu's formulas are the computational workhorse of all isogeny-based cryptography.

Elliptic curves over a finite field Fp can be organized into an isogeny graph. The vertices are j-invariants of elliptic curves (a canonical invariant that determines the curve up to isomorphism). The edges are l-isogenies: each ordinary curve has exactly l+1 outgoing l-isogenies for small prime l (by the structure of l-torsion subgroups). The l-isogeny graph over Fp is an (l+1)-regular graph. The Ramanujan property of these graphs (expander graphs) means random walks on them mix quickly, providing the hardness assumption underlying isogeny-based cryptography: random walks of length O(log p) produce uniform distributions over j-invariants.

Elliptic curves over Fp fall into two categories. Ordinary curves have a non-trivial p-rank, meaning there are p^2 isomorphism classes and a complex isogeny graph with a volcano structure (craters and floors). Supersingular curves have p-rank 0 and all live in a single connected isogeny graph over Fp2. The number of supersingular j-invariants over Fp is approximately p/12. SIDH and SIKE use supersingular curves because their isogeny graph is a Ramanujan graph with strong expansion properties and no volcano structure that could reveal walk direction. CSIDH also uses supersingular curves but over Fp (not Fp2), exploiting different algebraic structure.

Isogeny-based cryptography is founded on two related hard problems. Supersingular Isogeny Problem (SSIP): given two supersingular elliptic curves E and E' over Fp2, find an isogeny phi: E -> E'. Computational Supersingular Isogeny (CSSI) problem: given E, E' = phi(E), and the degree of phi, find phi. The best classical algorithm for SSIP runs in O(p^{1/4}) time. The best quantum algorithm (Tani's claw-finding) runs in O(p^{1/6}) time. For p = 2^{434}, this gives 128-bit classical security. These are significantly worse quantum speedups than the exponential speedup of Shor's algorithm against RSA/ECC, making isogeny-based schemes post-quantum secure.

SIDH (Supersingular Isogeny Diffie-Hellman) uses a specially structured prime p = 2^a * 3^b - 1 that ensures the curve E over Fp2 has 2^a-torsion points (the set of points P with 2^a * P = 0) and 3^b-torsion points accessible. Alice's secret is a 2^a-isogeny phi_A: E -> E_A with kernel generated by a random element of the 2^a-torsion. Bob's secret is a 3^b-isogeny phi_B: E -> E_B. They exchange torsion point images: Alice publishes E_A and phi_A(P_B), phi_A(Q_B). Bob publishes E_B and phi_B(P_A), phi_B(Q_A). This allows each party to compute isogenies from the other's curve, arriving at the same shared j-invariant.

The endomorphism ring End(E) of an elliptic curve is the ring of all isogenies from E to itself (including scalar multiplications). For ordinary curves over Fp, End(E) is an order in an imaginary quadratic field. For supersingular curves, End(E) is a maximal order in a quaternion algebra ramified at p and infinity. The structure of End(E) completely determines the curve up to isomorphism. The endomorphism ring problem — computing End(E) given E — is believed to be hard (equivalent to SSIP for supersingular curves). The Castryck-Decru attack on SIDH/SIKE exploited extra information leaked in the SIDH protocol to efficiently reconstruct part of the endomorphism ring, breaking the scheme.

A degree-l isogeny phi: E -> E' can be represented as a polynomial of degree l (or l/2 after symmetry optimization using the fact that point inverses have the same x-coordinate). Computing phi(P) for a given point P takes O(l) multiplications using Velu's formulas. For SIDH with l = 2^a around 2^216, this seems prohibitive, but SIDH uses the fact that 2^a-isogenies can be decomposed into a chain of a individual 2-isogenies — each 2-isogeny is cheap, and a chain of a steps produces a 2^a-isogeny. Similarly for 3^b. sqrt-Velu enables CSIDH's large odd-prime isogeny computations to run in O(sqrt(l)) rather than O(l), making CSIDH practical.

SIKE (Supersingular Isogeny Key Encapsulation) was a NIST PQC candidate that survived all rounds until the fourth round, when it was broken. SIKE was notable for the smallest key sizes of any NIST candidate: 374 bytes for SIKEp434 (NIST Level 1). For comparison, ML-KEM-512 has 800-byte public keys. SIKE achieved this compactness because the shared secret derives from a single j-invariant (a field element of ~430 bits). The compactness came at a cost: SIKE was 100-1000x slower than other candidates. When Castryck and Decru broke SIKE in July 2022 using a classical attack running in minutes on a laptop, SIKE was immediately eliminated from the NIST competition.

Isogeny-based cryptography occupies a unique position among post-quantum approaches. Key sizes: much smaller than lattice (ML-KEM: 800+ bytes) or hash-based signatures (SLH-DSA: 32-49 bytes public key, but 7856-49856 byte signatures). Performance: much slower than all alternatives (SIKE was 100-1000x slower than ML-KEM). Security assumption: distinct from LWE (used in ML-KEM/ML-DSA), SIS, or hash functions — provides cryptographic diversity. Post-quantum security basis: isogeny path problem has no known polynomial-time quantum algorithm, unlike RSA/ECC which Shor's algorithm breaks completely. SIKE's classical break demonstrates that isogeny hardness is still being understood, unlike the well-studied LWE problem.

Despite SIKE's break, isogeny-based cryptography remains an active research area. SQISign (Short Quaternion and Isogeny Signature) is an isogeny-based signature scheme with 177-byte signatures (vs ML-DSA's 2420 bytes for Level 2) — the smallest PQC signatures known. SQISign uses the hard problem of computing an isogeny of prescribed degree between two given supersingular curves, formalized as the endomorphism ring problem. FESTA (Fast Encryption from Supersingular Torsion Attacks) is a new KEM design that avoids the extra torsion-point auxiliary data that made SIDH vulnerable. CTIDH (Constant-Time CSIDH) improves CSIDH performance. These schemes keep isogeny research relevant even after SIKE's elimination.

What is an isogeny between elliptic curves?

An isogeny is a rational map phi: E -> E' that is a group homomorphism, with degree equal to its kernel size. Velu's formulas compute the image curve and map from the kernel subgroup. Isogeny graphs organize curves as vertices with l-isogeny edges forming (l+1)-regular Ramanujan graphs. Supersingular curves (used in SIDH/SIKE/CSIDH) have isogeny graphs with strong expansion. SSIP and CSSI problems underlie isogeny security. SIDH uses torsion point structure with alternating 2- and 3-isogeny chains. Endomorphism ring computation is equivalent to SSIP. SQISign and FESTA represent active post-SIKE research directions using endomorphism ring hardness.