The Mathematics behind PQC: Isogenies of Elliptic Curves

19 May 2025

Elliptic curves cryptography

After presenting the main PQC algorithms based on lattices, error correcting codes, hash functions, and multivariate systems, this article is focused on the topic of isogenies of elliptic curves, on which some of the schemes participating in the NIST standardization processes are built.

The application of elliptic curves to cryptography first started in the 1980s, when Miller and Koblitz proposed building a variant of the Diffie-Hellman key exchange (which until then had been constructed over finite fields) based on these mathematical objects. The result, known as ECDH (Elliptic-Curve Diffie-Hellman), is characterized by excellent performance and small key sizes, and it remains the most widely used DH key exchange variant to this day. Around the year 2000, the idea of constructing cryptographic schemes based on isogenies of elliptic curves (which, as will be defined later, are functions between elliptic curves) began to develop, particularly through the work of Couveignes, Teske, Rostovtsev, and Stolbunov. Interest in isogenies and their applicability in the development of PQC algorithms then increased starting in 2010, receiving a significant boost from the initiatives launched by NIST in 2016 and 2023.

It can thus be observed that, compared to cryptosystems based on the mathematical problems described in previous articles of this series, cryptographic schemes built from isogenies of elliptic curves are of more recent development and therefore generally characterized by a shorter history of cryptanalytic scrutiny. The smaller amount of research aimed at investigating potential vulnerabilities of isogeny-based cryptography algorithms increases the risk of new attacks that could reduce or completely compromise the security of such schemes: a notable example in this regard is what happened to SIKE, a KEM based on elliptic curve isogenies that participated in the first NIST call on PQC, whose security was completely broken by an attack presented in 2022 by Castryck and Decru.

The complete compromise of SIKE, the only isogeny-based scheme still under evaluation at that point, had a significant media impact and certainly represented a major blow to isogeny-based cryptography. However, it must be noted that the attack in question is not applicable to all isogeny-based schemes and that there are currently other important cryptosystems in this family considered secure, including CSIDH (key exchange) and SQIsign, a digital signature algorithm that was admitted to the second round of the NIST standardization process launched in 2023.

The greater immaturity of isogeny-based cryptography makes it a less conservative choice, especially when compared with schemes based on lattices or error-correcting codes. Nevertheless, cryptosystems based on isogenies of elliptic curves have attracted significant attention from the cryptographic community, mainly due to the fact that such algorithms feature extremely small public keys and signatures, which would allow their use in contexts where bandwidth is highly constrained. The applicability of isogeny-based schemes in such scenarios, however, is still limited by the poor performance of these algorithms, which are inferior not only to those offered by ECDH, but also to those of other families of cryptosystems.

Isogenies of elliptic curves

For the sake of simplicity, we present the objects involved through their operational definitions.
Let $\mathbb{K}$ be a field; aside from technical conditions on $\mathbb{K}$ , an elliptic curve $E$ defined over $\mathbb{K}$ is the set of points $(x,y)$ that satisfy the so-called Weierstrass equation

$y^2 = x^3 + ax +b,\quad a,b\in\mathbb{K}\quad\text{e}\quad 4a^3+27b^2\neq0,$

with the addition of a special point $\mathcal{O}$ , called the point at infinity. The nature of an elliptic curve depends on the field over which it is defined. For example, in the following figure we observe elliptic curves defined by the same Weierstrass equation over different fields.

La matematica dietro la PQC Isogenie di Curve Ellittiche fig1 — $y^2=x^3-3x+3$ su $\mathbb{R}$

La matematica dietro la PQC Isogenie di Curve Ellittiche fig2 — $y^2=x^3-3x+3$ su $\mathbb{F}_{401}$

The $j$ -invariant of an elliptic curve $E$ defined by the above equation is

$j(E) = \frac{4a^3}{4a^3 + 27b^2}1728.$

It is possible to define on $E$ an operation $+$ that turns the set of its points into a commutative group with the identity element being the point at infinity $\mathcal{O}$ . We denote the $m$ -fold sum of a point $P \in E$ as

$[m]P:=\underbrace{P+...+P}_{m\text{ volte}}.$

This algebraic structure is the foundation of “classical” elliptic curve cryptography, such as ECDH. The public key in a classical scheme essentially consists of a pair of points $(P, Q)$ in $E$ , and the private key is an integer $m$ such that $Q = [m]P$ .

In isogeny-based cryptography, there is a substantial shift in perspective: the manipulated objects are no longer points on a fixed elliptic curve, but the set of elliptic curves themselves. The public key is now a pair of elliptic curves $(E_1, E_2)$ , and the secret key is a certain map between $E_1$ and $E_2$ , called an isogeny.

An isogeny $\phi: E_1 \rightarrow E_2$ is a map between elliptic curves $E_1$ and $E_2$ that preserves their structure, specifically:

for every pair of points $P, Q$ in $E_1$ , it holds $\phi(P+Q) = \phi(P) + \phi(Q)$ ;
$\phi(\mathcal{O}_1) = \mathcal{O}_2$ , where $\mathcal{O}_1$ and $\mathcal{O}_2$ are the points at infinity of $E_1$ and $E_2$ , respectively.

An isomorphism is an isogeny that admits an inverse map. The $j$ -invariant identifies an elliptic curve up to isomorphism, meaning that two elliptic curves defined over $\mathbb{K}$ have the same $j$ -invariant if and only if there exists an isomorphism between them.

An isogeny from $E$ to itself is called an endomorphism; the set of endomorphisms of an elliptic curve $E$ — together with the zero map — has a ring structure and is denoted by $\text{End}(E)$ . An example of an endomorphism is the $m$ -fold sum $[m]$ defined above; since the family $\{[m]\,:\, m\in\mathbb{Z}\}$ belongs to $\mathrm{End}(E)$ for every elliptic curve $E$ , these maps are called trivial endomorphisms.

To each isogeny $\phi$ is associated a positive integer $\deg \phi$ , called the degree, which in cryptographic contexts coincides with the cardinality of the kernel of $\phi$ , that is, the set of points mapped to the point at infinity by $\phi$ .

A Visual Approach: Isogeny Graphs

Given a field $\mathbb{K}$ and a fixed integer $\ell$ , the isogeny graph of degree $\ell$ is the graph $\mathcal{G}_{\mathbb{K},\ell}=(V,A)$ whose vertices $V$ are the set of elliptic curves up to isomorphism, and where there is an edge between two vertices $(E_1, E_2)$ if and only if there exists an isogeny of degree $\ell$ between the two curves.

In practice, the isomorphism classes of elliptic curves that form the vertices of an isogeny graph are represented via their $j$ -invariant.

The following figures show two connected components of the degree-3 isogeny graph over the field $\mathbb{F}_{401^2}$ .

La matematica dietro la PQC Isogenie di Curve Ellittiche fig3 — Ordinary component

La matematica dietro la PQC Isogenie di Curve Ellittiche fig4 — Supersingular component

A strong symmetry can be observed in the image on the left, which is missing in the one on the right. This is due to the different nature of the elliptic curves involved: in the first, the nodes correspond to $j$ -invariants of so-called ordinary curves; in the second, to $j$ -invariants of so-called supersingular curves. An elliptic curve $E$ is defined as ordinary if $\mathrm{End}(E)$ is commutative; otherwise, it is called supersingular.

Isogenies and hard problems

The security of public key cryptography schemes is based on computational problems believed to be intractable. The theory of isogenies of elliptic curves allows us to define problems that are conjectured to be hard even for a quantum computer. The main problem in isogeny-based cryptography is the so-called Isogeny Problem: given two elliptic curves $E$ and $E'$ defined over $\mathbb{K}$ , find, if it exists, an isogeny $\phi: E \rightarrow E'$ .
Several isogeny-based cryptosystems rely on a variant of this problem, called $\ell$ –IsogenyPath, where the goal is to find an isogeny of fixed degree. Formally, given two elliptic curves $E$ and $E'$ defined over $\mathbb{K}$ and a prime number $\ell$ , the problem asks to find, if it exists, an isogeny $\phi: E \rightarrow E'$ such that $\phi = \phi_1 \circ \ldots \circ \phi_n$ with $\deg \phi_i = \ell$ for $i = 1, \ldots, n$ .

The name of the problem comes from the fact that a solution is equivalent to finding a path of length $n$ in the isogeny graph of degree $\ell$ :

$E = E_1 \xrightarrow{; \phi_1; } E_2 \xrightarrow{; \phi_2; } \cdots \xrightarrow{\phi_{i-1}} E_i \xrightarrow{; \phi_i; } E_{i+1} \xrightarrow{\phi_{i+1}} \cdots \xrightarrow{; \phi_n; } E_{n+1} = E'.$

The formulation of these problems gives an initial intuition as to why supersingular elliptic curves are primarily used in cryptography: the lack of a clear structure makes the search for such paths more complex.

Historically, a second category of problems from isogeny theory has been studied, which concerns the endomorphism ring. This category includes the EndRing Problem, where, given an elliptic curve $E$ defined over $\mathbb{K}$ , one is asked to compute $\mathrm{End}(E)$ .

Recently, cryptographic primitives have also been defined that base their security on the assumption that even finding a single non-trivial endomorphism is difficult. This is formalized in the OneEnd Problem, which requires computing an isogeny $\phi: E \to E$ different from $[m]$ for any integer $m$ .

In fact, the two classes of problems presented here are more closely connected than they might appear. Indeed, it has been surprisingly shown that the Isogeny, EndRing, and OneEnd problems are equivalent.

The digital signature scheme SQIsign bases its security on this latter problem. It is the only isogeny-based proposal submitted to the NIST post-quantum standardization call in 2023, and it will be presented in the next article in this series.

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Elena Broggini, MSc in Mathematics at University of Milan. She is currently a PhD student in the Number Theory and Cryptography group at the Polytechnic University of Turin with a scholarship on Post-Quantum Cryptography and Fully Homomorphic Encryption in collaboration with the Telsy research group.

Giuseppe D’Alconzo is a research fellow at the Polytechnic University of Turin. He received his Ph.D. in Mathematics with a grant themed “Post-Quantum Cryptography” under the UniversiTIM program and in collaboration with the Telsy Research Group. He graduated in Mathematics with a specialization in Cryptography from the University of Trento, and he did an internship at Telsy in 2019, working on Multi-party Computation and Attribute Based Encryption.

Marco Rinaudo, a bachelor’s degree in Mathematics from the University of Turin and a master’s degree with a specialization in Cryptography from the University of Trento. Following a 2022 curricular internship at Telsy, he has been part of the Cryptography Research Group since January 2023.