PDF LaTeX source Comments

Chapter 25Isogeny-Based Cryptography

25.1Learning objectives#

The families covered so far – lattices, hashes, and codes – account for every scheme NIST has standardized, but they do not exhaust the landscape of post-quantum cryptography. The standard taxonomy names five broad families [1], and this chapter surveys the youngest and most mathematically demanding of them: isogeny-based cryptography, whose hardness comes not from decoding or short vectors but from navigating a vast graph of elliptic curves. It is the family with the smallest keys and signatures of any post-quantum approach, and also the one that produced the field’s most dramatic cautionary tale – a flagship scheme that reached the final round of the NIST competition and was then broken outright in an afternoon. Both facts are worth understanding, and they are connected.

This chapter is a survey, not an implementation guide. The mathematics of isogenies runs deep, and we deliberately trade rigour for intuition: the aim is to convey what the objects are, why the underlying problem is believed hard, how the schemes use it, and what the 2022 break did and did not destroy.

After finishing this chapter, you should be able to:

1. recall what an elliptic curve over a finite field is, and describe an isogeny as a structure-preserving map between two such curves;

2. explain what makes a curve supersingular and picture the supersingular isogeny graph, whose rapid mixing is the source of cryptographic hardness;

3. state the supersingular isogeny path problem and explain why it is believed hard for classical and quantum computers alike, and why it yields the smallest parameters of any post-quantum family;

4. describe SIDH/SIKE as a Diffie–Hellman-style key exchange on the graph, and explain how the Castryck–Decru attack recovered its secret key in polynomial time by exploiting the auxiliary torsion-point information the protocol reveals;

5. place what survives the break – CSIDH and SQIsign – and explain why isogeny signatures are the smallest known, even though no isogeny scheme is yet a FIPS standard.

Why this chapter matters.#

The value of a portfolio of post-quantum families is that they fail independently: a breakthrough against lattices would say nothing about codes or isogenies. Isogeny-based cryptography is the most extreme point in that portfolio – the smallest bandwidth by a wide margin, resting on a problem with no known subexponential attack, but built on machinery only a couple of decades old and probed far less than lattices or codes. The story of SIDH is the sharpest illustration in this book of a general principle: a hard problem can be quietly undermined not by attacking it head-on, but by the extra information a protocol hands the attacker for free. That lesson outlives the scheme that taught it.

25.2A crash course in elliptic curves and isogenies#

The reader has met finite fields and polynomial rings, but not the geometry this family is built on. This section introduces just enough of it. Everything lives over a finite field \(\mathbb{F}_q\), and for the cryptographically interesting case \(q = p^2\) for a large prime \(p\).

Elliptic curves.#

An elliptic curve is a particular kind of cubic equation whose solutions can be added to one another, turning a geometric object into an algebraic group.

Two facts about this group matter for us. First, its size is finite and close to \(q\); the group is where classical elliptic-curve cryptography (ECC) hides its secrets, in the difficulty of the discrete logarithm. That difficulty is exactly what Shor’s algorithm destroys, so ECC is not post-quantum. Isogeny-based cryptography reuses the curves but abandons the discrete logarithm entirely, hiding its secrets somewhere Shor cannot reach: in the maps between curves.

Second, each curve carries a single number, its \(j\)-invariant \(j(E) \in \mathbb{F}_q\), computed from \(a\) and \(b\). Two curves are isomorphic exactly when their \(j\)-invariants agree, so we may think of \(j(E)\) as a fingerprint that names the curve up to relabelling. The schemes in this chapter transmit \(j\)-invariants, not equations.

Isogenies.#

An isogeny is a map from one elliptic curve to another that respects both the geometry and the group structure – the natural notion of “morphism” for these objects.

The single most useful fact about isogenies is that they are pinned down by their kernels. Given any finite subgroup \(G \subseteq E_1\), there is an isogeny \(\varphi : E_1 \to E_2\) with kernel exactly \(G\), unique up to isomorphism of the target, and it can be computed efficiently from \(G\) by Vélu’s formulas. So “choosing an isogeny out of \(E_1\)” and “choosing a finite subgroup of \(E_1\)” are the same act. A secret isogeny is really a secret subgroup, and to walk a long isogeny is to compose many small ones.

Two more properties make isogenies behave like the arrows of a well-connected network. Degrees multiply under composition, so a chain of \(\ell\)-degree steps is an isogeny of degree \(\ell^e\). And every isogeny \(\varphi\) of degree \(d\) has a dual isogeny \(\hat{\varphi}\) of the same degree running the other way, with \(\hat{\varphi} \circ \varphi = [d]\) (multiplication by \(d\)). Isogenies of a fixed small degree therefore come in matched pairs, which is what lets us regard them as undirected edges of a graph.

25.3The supersingular isogeny graph#

Among all elliptic curves over \(\mathbb{F}_{p^2}\), a special and comparatively rare class – the supersingular curves – provides the setting for cryptography. The precise definition (a curve whose ring of self-maps, its endomorphism ring, is unusually large – an order in a quaternion algebra rather than in an imaginary quadratic field) is beyond a survey. What matters is the consequence.

A small, tightly connected world.#

There are only about \(p/12\) supersingular \(j\)-invariants over \(\mathbb{F}_{p^2}\) – a finite set, but astronomically large for a cryptographic \(p\) of several hundred bits. Fix a small prime \(\ell\) (in practice \(\ell = 2\) or \(\ell = 3\)). Build a graph:

• the vertices are the supersingular curves over \(\mathbb{F}_{p^2}\), each named by its \(j\)-invariant;

• the edges are the isogenies of degree \(\ell\) between them; because every \(\ell\)-isogeny has a dual of degree \(\ell\), edges are undirected.

Each vertex has exactly \(\ell + 1\) neighbours, so this supersingular \(\ell\)-isogeny graph is \((\ell+1)\)-regular. It is also connected: from any supersingular curve you can reach any other by a sequence of \(\ell\)-isogeny steps.

Rapid mixing.#

The property that makes the graph cryptographically useful is that it is an optimal expander – in fact a Ramanujan graph, meeting the theoretical limit on how well-connected a regular graph can be. In plain terms, a random walk mixes extremely fast: after only about \(\log p\) steps, the endpoint of a random path is distributed almost uniformly over all \(\sim p/12\) vertices, with no detectable bias toward where it started. A secret path of a few hundred small steps therefore lands on a curve that reveals nothing about the route taken. This is the isogeny analogue of a one-way function: composing the steps forward is cheap, but the endpoint alone does not betray the path.

25.4The hard problem: finding an isogeny path#

The security of the entire family rests on the belief that the walk cannot be run backwards – that seeing only the two endpoints of a secret path gives no efficient way to reconstruct it.

Because the graph is an expander, the two endpoints look like an unrelated pair of curves; nothing local about \(E_t\) points back toward \(E_0\). The best known classical algorithms are generic path-finding (meet-in-the-middle) searches that cost on the order of \(\sqrt{p}\) work, and the best known quantum algorithms – claw-finding built on Grover-style search – cost on the order of \(p^{1/4}\). Both are fully exponential in the bit-length of \(p\): there is no known subexponential attack, classical or quantum, and in particular nothing resembling Shor’s collapse of factoring and discrete logarithms. The problem is closely tied to the difficulty of computing the endomorphism ring of a supersingular curve, which is believed equally hard.

This exponential hardness with tiny objects is the family’s headline advantage. Because attacks scale as \(\sqrt{p}\) or \(p^{1/4}\) rather than as a mild erosion of a large structured key, a few hundred bits of \(p\) already buy a comfortable security margin. The transmitted data are \(j\)-invariants and a handful of curve coordinates – a few dozen to a few hundred bytes. No other post-quantum family comes close on bandwidth. The catch, developed over the rest of the chapter, is that a protocol may have to reveal more than the two bare endpoints, and that “more” is where the danger lives.

25.5SIDH and SIKE: a Diffie–Hellman on the graph#

The first practical isogeny scheme was SIDH – Supersingular Isogeny Diffie–Hellman – proposed by Jao and De Feo in 2011 [2]. Its shape mirrors classical Diffie–Hellman exactly, with secret isogenies playing the role of secret exponents.

The commutative square.#

Fix a public starting curve \(E_0\) over \(\mathbb{F}_{p^2}\), where \(p\) is chosen so that \(E_0\) has plentiful torsion of two coprime orders – typically powers of \(2\) and of \(3\). The two parties walk in the two different graphs:

• Alice picks a secret subgroup of \(2\)-power order and computes her secret isogeny \(\varphi_A : E_0 \to E_A\);

• Bob picks a secret subgroup of \(3\)-power order and computes his secret isogeny \(\varphi_B : E_0 \to E_B\).

Each publishes the endpoint curve (\(E_A\), \(E_B\)) of their own walk. If each could now re-apply their own secret isogeny starting from the other’s curve, the two routes would commute and meet at a single shared curve \(E_{AB}\), whose \(j\)-invariant is the shared secret. This is the commutative square of Figure 25.2.

The auxiliary torsion points.#

Here lies the subtle ingredient. To let Bob re-apply Alice’s isogeny from his curve, Alice must publish not only \(E_A\) but also the images under \(\varphi_A\) of a fixed public basis of Bob’s torsion subgroup – two extra points on \(E_A\). Bob does the symmetric thing. These auxiliary torsion-point images are what allow each party to reconstruct the partner’s secret subgroup translated onto their own curve, and so to finish the square. They are essential to the protocol. They are also strictly more information than the bare path problem gives an attacker: alongside the endpoints \(E_0\) and \(E_A\), the adversary is handed the action of the secret isogeny on a known set of points.

SIKE.#

Wrapping SIDH in a Fujisaki–Okamoto-style transform (Section 16.13) yields SIKE (Supersingular Isogeny Key Encapsulation), a chosen-ciphertext-secure KEM. SIKE was a serious contender in the NIST competition: it advanced to the fourth round as one of the few remaining key-encapsulation candidates, prized above all for its exceptionally small keys and ciphertexts – on the order of a few hundred bytes, several times smaller than any lattice or code alternative. For a decade it was the poster child for how little bandwidth post-quantum security might cost.

25.6The 2022 break#

In the summer of 2022, SIDH and SIKE were broken. Castryck and Decru gave an efficient key-recovery attack [3]: given a party’s public key, it reconstructs the secret isogeny in polynomial time. For the actual SIKE parameters the attack runs in minutes to about an hour on a single ordinary computer – not a marginal weakening of the security level, but a total collapse. Independent refinements by others followed within weeks, generalizing and speeding up the result.

What the attack exploited.#

Crucially, the attack did not solve the supersingular isogeny path problem. It targeted the extra information SIDH reveals: the auxiliary torsion-point images. The core idea uses a theorem of Kani to relate Alice’s secret isogeny to an isogeny between higher-dimensional abelian varieties (products of elliptic curves), and the known torsion-point images provide exactly the data needed to build and evaluate that higher-dimensional object step by step. Each step tests and extends a guess about the secret walk, and because the auxiliary points pin the walk down so tightly, the search collapses from exponential to polynomial. The starting curve’s special structure, whose endomorphisms are known, made the construction concrete.

The lesson.#

This is the sharpest example in the book of a recurring hazard: side information volunteered by a protocol can undermine a hard problem without touching the problem itself. SIDH’s designers knew the torsion images were extra data, but for eleven years no one saw how to weaponize them; the mathematics that turned them into a break – higher-dimensional isogenies – simply had not been connected to the setting yet. It is a reminder that “the underlying problem is hard” is a necessary but not sufficient condition for a scheme’s security, and that young assumptions can hide such connections for a long time.

25.7What survives: CSIDH and SQIsign#

The break was specific to SIDH’s torsion-point construction. Isogeny schemes that do not publish the action of a secret isogeny on known points were untouched, and the family remains active. Two lines are worth naming.

CSIDH.#

CSIDH (“commutative SIDH”, pronounced “sea-side”) is a key exchange built on a different structure: a commutative group action of an ideal-class group on a set of supersingular curves defined over the prime field \(\mathbb{F}_p\). Because the shared secret is derived purely from composing group-action elements, CSIDH transmits only curves – no auxiliary torsion-point images – so the Castryck–Decru attack does not apply to it. Its distinctive feature is that the key exchange is non-interactive and commutative in the way classical Diffie–Hellman is, which SIDH never quite was. The trade-off is that a commutative group action is vulnerable to a subexponential quantum attack (Kuperberg’s hidden-shift algorithm), so CSIDH must use larger parameters than its exponential-hardness cousins, and it is computationally slow. Its exact security level remains debated.

SQIsign.#

The most prominent survivor is SQIsign (“Short Quaternion and Isogeny Signature”), introduced by De Feo, Kohel, Leroux, Petit, and Wesolowski in 2020 [4]. It is a signature scheme, built from the correspondence between supersingular curves and quaternion orders (the Deuring correspondence), and it rests on the hardness of the endomorphism-ring / isogeny-path problem rather than on any torsion-point trick. Its headline property is size: SQIsign produces the smallest signatures and public keys of any post-quantum signature scheme by a wide margin – a signature of a couple of hundred bytes and a public key of a few dozen, where lattice signatures run to a kilobyte or more and hash-based signatures to many kilobytes. The price is speed: signing and verification are far slower than lattice schemes, historically on the order of seconds, though later variants have cut this substantially. As of writing, SQIsign is a candidate in NIST’s additional-signatures round (the “on-ramp” for signatures beyond the lattice and hash standards), where its tiny footprint is the main attraction and its performance and youth are the main concerns.

25.8Trade-offs and status#

Isogeny-based cryptography occupies a clear and unusual corner of the design space.

Status.#

No isogeny-based scheme is a FIPS standard. SIKE, once a NIST fourth-round KEM candidate, was withdrawn after the 2022 break. SQIsign is under evaluation in the additional-signatures round as of writing, valued for its unmatched compactness but held back by performance and by the relative youth of its security foundations; whether it advances to standardization is undecided. CSIDH remains a research-grade proposal with contested parameters. The honest summary is that isogeny-based cryptography is the most promising small-footprint post-quantum family and simultaneously the least mature – a live research area rather than a settled toolbox.

25.9Pitfalls#

Pitfall 1: assuming a hard underlying problem makes a scheme safe.#

This is the SIKE lesson, and it is the most important idea in the chapter. The supersingular isogeny path problem was never broken; SIDH was broken because it revealed more than that problem – the images of known torsion points under the secret isogeny – and that surplus was enough. A security proof is only as strong as the assumption it actually reduces to, and a protocol that leaks auxiliary structure may be reducing to a much easier problem than its designers intended.

Pitfall 2: treating “smallest keys” as “best.”#

Isogeny schemes win decisively on bandwidth, and it is tempting to read that as an overall verdict. It is not. They are slow, their assumptions are young, and one flagship has already fallen. Size is one axis among several; conservatism and speed pull the other way, and for most deployments a lattice scheme’s balance is the safer default today.

Pitfall 3: thinking the 2022 break killed the whole family.#

The Castryck–Decru attack was specific to the torsion-point construction of SIDH and SIKE. Schemes that do not publish such images – CSIDH, SQIsign – are not affected by it, and the family remains an active standardization candidate through SQIsign. “SIDH is broken” and “isogenies are broken” are very different statements; only the first is true.

Pitfall 4: forgetting how young the field is.#

Lattices and codes have been attacked for decades; the supersingular-isogeny assumptions have been under concentrated cryptanalysis for a far shorter time, and the mathematics involved – endomorphism rings, higher-dimensional isogenies, the Deuring correspondence – is deep enough to hide further connections. Youth is not a flaw, but it is a reason to demand hybrid deployment and to avoid betting long-lived secrets on isogenies alone.

25.10Summary#

Isogeny-based cryptography is the fifth and youngest of the post-quantum families, and the one that departs furthest from the rest of this book:

• its objects are elliptic curves over a finite field and the isogenies – structure-preserving maps – between them, organized into a supersingular isogeny graph that is a rapidly mixing expander;

• its hard problem is the supersingular isogeny path problem – recover a secret path from its two endpoint curves – which has no known subexponential attack, classical or quantum, and so yields the smallest keys and signatures of any family;

• SIDH/SIKE [2] turned this into a Diffie–Hellman-style key exchange, reached NIST’s fourth round, and was then broken in polynomial time in 2022 [3] – not by solving the path problem, but by exploiting the auxiliary torsion-point images the protocol reveals;

• what survives – CSIDH for key exchange and SQIsign [4] for the smallest signatures known – avoids that leak, and SQIsign is a live candidate in NIST’s additional-signatures round, though no isogeny scheme is yet a FIPS standard.

The lesson of the SIDH break is not that isogenies failed – the assumption at their core is intact – but that a hard problem can be undermined by the information a protocol publishes around it. Combined with the family’s compactness and its comparative youth, this places isogeny-based cryptography at the high-risk, high-reward end of the post-quantum portfolio: the smallest footprint available, resting on the least-settled ground.

References