The applications of isogenies in Post Quantum Cryptography

14 Jul 2025

After introducing the theory of elliptic curves and defining the necessary tools, we present some classical schemes in isogeny-based cryptography. As mentioned in the previous article, this part of Post Quantum Cryptography began in the early 2000s thanks to the work of Couveignes, Teske, Rostovtsev, and Stolbunov. In the following decade, interest from the cryptographic community increased, and after proposals were submitted to the NIST calls in 2016 and 2023, we can now say that isogeny-based cryptography has reached a promising level of maturity in the post-quantum landscape.

The CGL Hash Function

In 2006, Charles, Goren, and Lauter introduced a collision-resistant hash function $H_{\mathrm{CGL}}$ , whose security is based on the $2$ –IsogenyPath Problem.

Recall that a hash function is an algorithm that takes as input a string of arbitrary length and returns a fixed-length output. A hash function $H$ is said to be collision-resistant if it is computationally infeasible to find distinct values $x$ and $y$ such that $H(x)=H(y)$ .

The idea is to use the bits of the message to be hashed as a guide to explore an isogeny graph. The $H_{\mathrm{CGL}}$ hash function exploits a specific property of these graphs: apart from vertices corresponding to $j$ -invariants 0 and 1728, the supersingular component of the isogeny graph of degree $\ell$ is shown to be $\ell+1$ -regular, meaning each vertex has $\ell+1$ edges. The $j$ -invariant of the endpoint of the path will be the hash of the message.

Le applicazioni delle isogenie nella Post Quantum Cryptography Componente supersingolare di un isogeny graph di grado 3 — Supersingular component of an isogeny graph of degree 3.

We begin by selecting the supersingular component of an isogeny graph of degree 2. Among the parameters of the hash function are the graph, a vertex $V_0$ — the starting point of the path — and two of its three edges $e_0^{(0)},e_1^{(0)}$ .

To compute the output of $H_{\mathrm{CGL}}$ on a message $m$ , whose bits are $(m_0,\dots,m_N)$ , we proceed as follows:

Move from vertex $V_0$ to vertex $V_1$ , defined as the second vertex of edge $e_{m_0}^{(0)}$ . Due to the regularity of the graph, vertex $V_1$ has three edges: $e_{m_0}^{(0)}$ , which we just traversed, and two others, denoted $e_{0}^{(1)}$ and $e_{1}^{(1)}$ .
Iteratively, for each $i=1,\dots,N$ , bit $m_i$ determines which edge $e_{m_i}^{(i)}$ from $V_{i-1}$ must be followed, thus obtaining the $i$ -th vertex $V_i$ of the path.
Once all bits of message $m$ have been used, the output of the hash function is defined as the $j$ -invariant of the final vertex, that is, $H_{\mathrm{CGL}}(m)=V_{N+1}$ .

This method explores the isogeny graph deterministically using the input message bits. As mentioned, the $2$ –IsogenyPath problem ensures the collision resistance of $H_{\mathrm{CGL}}$ : intuitively, finding a collision means finding two bit strings that, when used to explore the isogeny graph, reach the same vertex. Fixing one of the two paths, finding the other corresponds to producing a degree- $2^k$ isogeny between two fixed elliptic curves — precisely the $2$ –IsogenyPath problem.

The favorable properties of isogeny graphs not only guarantee that $H_{\mathrm{CGL}}$ satisfies the security properties of a hash function, but also provide additional features that make it particularly appealing in practice. For example, $H_{\mathrm{CGL}}$ produces outputs that are uniformly distributed in the degree-2 isogeny graph. This follows from the fact that in isogeny graphs, random walks converge very quickly to the uniform distribution. More precisely, the final vertex of a path in an isogeny graph tends toward the uniform distribution after a number of steps logarithmic in the number of vertices of the graph.

Key Exchange

Another application that has sparked interest in isogeny-based cryptography is the possibility of performing a key exchange similar to Diffie-Hellman.

Suppose Alice and Bob want to establish a shared secret. After agreeing on a common elliptic curve $E_0$ , they choose their secret isogenies $\phi_A$ and $\phi_B$ and compute their respective public keys as $E_A=\phi_A(E_0)$ and $E_B=\phi_B(E_0)$ . The classic Diffie-Hellman scheme would allow the parties, from this information, to compute a shared secret, which in our case is the $j$ -invariant of a curve $E$ . However, to instantiate an isogeny-based version of Diffie-Hellman, some modifications are necessary.

Two Practical Proposals: SIDH and CSIDH

In 2011, De Feo, Jao, and Plût proposed the SIDH (Supersingular Isogeny Diffie-Hellman) key exchange, which was later submitted to the NIST call under the name SIKE (Supersingular Isogeny Key Encapsulation). In SIDH, to enable the counterpart to compute the shared secret $E$ , both Alice and Bob must publish the image of certain points through their private isogeny, in addition to the curves $E_A$ and $E_B$ . Although these protocols were considered secure against quantum adversaries for more than a decade, in 2023 the additional public information became the basis of classical (non-quantum) attacks against SIDH and SIKE. These attacks used techniques previously unexplored in isogeny-based cryptography and, surprisingly, those same techniques were later used constructively to design new schemes.

Another approach to the problem is to restrict the set of elliptic curves considered, so that the shared secret can be computed without publishing extra information. In 2018, Castryck, Lange, Martindale, Panny, and Renes published the CSIDH key exchange [1] (Commutative SIDH), which reformulates the protocol using the language of commutative group actions. In particular, only supersingular elliptic curves defined over a certain subfield are considered, on which the so-called ideal class group acts. This setting not only enabled a practical Diffie-Hellman-style key exchange but also facilitated several constructions, including digital signatures.

Digital Signatures

The construction of digital signatures based on isogeny assumptions dates back to theoretical work done in 2012 by Stolbunov, who, after presenting an identification scheme, transformed it into a digital signature using the Fiat-Shamir paradigm.

The identification scheme introduced by Stolbunov is the basis of later signatures such as SeaSign (2018) and CSI-FiSh (2019), and is inspired by the 1991 protocol of Goldreich, Micali, and Wigderson for proving knowledge of an isomorphism between two public graphs. Similarly, Stolbunov published a three-step protocol allowing a prover to demonstrate to a verifier knowledge of a secret isogeny between two public elliptic curves. This proposal bases its security on the action of the ideal class group, in a way similar to CSIDH. At the time, its interest was more theoretical than practical, as instantiating the protocol required knowledge of the structure of the ideal class group, which is not obvious for cryptographically relevant parameters.

SeaSign and CSI-FiSh: digital signatures Based on CSIDH

In 2018, following the release of CSIDH, De Feo and Galbraith published SeaSign [2], an instantiation of Stolbunov’s signature using tools provided by CSIDH. The structure of the ideal class group was still unknown, but this technical issue was overcome using the Fiat-Shamir with aborts paradigm, also used in the CRYSTALS-Dilithium signature scheme. This technique enabled a working digital signature, although not yet fully usable: signing and verification times were still on the order of minutes.

In 2019, Beullens, Kleinjung, and Vercauteren, following what was described as a record computation, calculated the structure of the ideal class group used in CSIDH and published CSI-FiSh (Commutative Supersingular Isogeny based Fiat-Shamir), the natural evolution of SeaSign, which no longer requires abort operations. This results in a more efficient and streamlined protocol, with signature times on the order of hundreds of milliseconds: isogeny-based signatures are therefore coming ever closer to being practical and usable.

[1] Pronounced “Seaside”, as the authors began working on it while near a well-known large body of salt water (https://csidh.isogeny.org)
[2] Both the name and pronunciation are a reference to CSIDH (Seaside).

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.