Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Design, Analysis, and Optimization of Isogeny-Based Key Establishment Protocols

Jason T. LeGrow

Published Aug 19, 2020• 0 citations
OpenAlex

Abstract

We analyze the Commutative Supersingular Isogeny Diffie-Hellman protocol (CSIDH), a novel supersingular isogeny-based key establishment protocol. Our analysis is from three perspectives: \n \nQuantum Cryptanalysis. Building upon quantum attacks on ordinary isogeny-based cryptography, we propose a subexponential-time quantum algorithm for inverting the complex multiplication group action for supersingular elliptic curves, which uses only polynomial quantum space. This improves upon previously-known algorithms which required subexponential quantum space. \n \nOptimization. We develop more efficient algorithms for evaluating the class group action in the context of CSIDH. We consider "strategies"—formerly only considered for Supersingular Isogeny Diffie-Hellman (SIDH)—in the context of CSIDH, and develop systematic methods for optimizing "permutations" of the small primes used in CSIDH, which previously had been treated only in an ad hoc fashion. We also develop a systematic technique to optimize the CSIDH keyspace. These optimizations are complementary to prior work on optimizing CSIDH, including improved field arithmetic, Splitting Isogenies into Multiple Batches (SIMBA), and the two-point method. We apply our optimizations to the CSIDH-512 parameter set and give experimental results. \n \nFault Attacks. We consider physical attacks on static/ephemeral CSIDH in which limited information about which isogenies are "real" and which are "dummy" is revealed. We determine bounds on the number of fault injections required to recover the static secret key, and show that simply reordering the real and dummy isogenies from the ubiquitous "real-then-dummy" ordering to a dynamic random ordering dramatically increases the number of faults required, with negligible impact on the running time of the key exchange protocol (in contrast with prior fault attack countermeasures, which prevent fault attacks entirely at the cost of doubling the running time for key exchange).

Related papers

Isogeny-based post-quantum key exchange protocols

Ernest Sorinas Capdevila

The goal of this project is to understand and analyze the supersingular isogeny Diffie Hellman (SIDH), a post-quantum key exchange protocol which security lies on the isogeny-finding problem between supersingular elliptic curves. In order to do so, we first introduce the reader to cryptography focusing on key agreement protocols and motivate the rise of post-quantum cryptography as a necessity with the existence of the model of quantum computation. We review some of the known attacks on the SIDH and finally study some algorithmic aspects to understand how the protocol can be implemented.

•Jan 1, 2020•0 citations

Construction of IND-CPA Secure Isogeny-based Cryptosystem SiGamal and Unified Coordinate Formulas for Efficient Isogeny Computation

共起 守谷

Public key cryptography is crucial in current Internet technology.In practice, Rivest, Shamir, Adleman (RSA) cryptography based on Prime Factorization Problem, and Elliptic Curve cryptography based on Discrete Logarithm Problem are typically used.However, both these systems are broken in polynomial time using quantum computers.Therefore, new cryptosystems that are secure against adversaries using quantum computers (postquantum cryptography) should be developed.Isogeny-based cryptography exhibits considerable potential for use in post-quantum cryptography.It is based on Isogeny Problem that is a problem finding an isogeny from two elliptic curves.The greatness of isogeny-based cryptography is that the key length is short and hence compact secure communication is realizable.However, isogeny-based cryptography is yet to mature, and some problems remain.Although isogeny-based cryptography is considered one of the notable candidates for post-quantum cryptography, it has several problems due to its short history.In this thesis, we focus on two problems.The first one is the lack of studies on the security of isogenybased cryptosystems.Another one is that isogeny-based cryptosystems are less efficient than other candidates for post-quantum cryptography.Because of the insufficiency of studies about security, an IND-CPA secure isogeny-based public key encryption scheme without using random functions (idealized hash functions) is yet to be obtained.Some schemes have been proposed for isogeny-based public key encryption schemes; however, these schemes are only OW-CPA secure, which is the minimum security for public key encryption.Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) key exchange is an isogeny-based key exchange scheme based on group actions.Because this scheme is similar to Diffie-Hellman key exchange that has many applications, CSIDH is considered a useful scheme.CSIDH plays a crucial role in cryptography that uses group actions, and there are some applications of CSIDH for signatures and high-level cryptosystems.However, a simple public key encryption scheme based on CSIDH does not have IND-CPA security, whereas ElGamal encryption derived from Diffie-Hellman key exchange has IND-CPA security.This is because CSIDH has less mathematical structure than Diffie-Hellman, and a mathematically natural construction of key encryption based on CSIDH is yet to be obtained.In this thesis, we propose a novel public key encryption scheme, namely SiGamal.This scheme is constructed by adding auxiliary points to CSIDH key exchange.These auxiliary points extend a mathematical structure of CSIDH, and SiGamal is compatible with this extended mathematical structure.Therefore, SiGamal is a more natural ElGamal-like key encryption scheme based on CSIDH.Because SiGamal requires auxiliary points, it requires larger data than CSIDH and is less efficient.However, SiGamal has IND-CPA security without using hash functions under a new security assumption, namely the P-CSSDDH assumption.As an application of this scheme, we proposed Naor-Reingold type pseudo random function based on SiGamal.This pseudo random function (PRF) does not require hash functions, and it costs approximately 8T 3π times SiGamal, where T is the Hamming weight of the input of the PRF.Finally, experiments are conducted to verify the efficiency of SiGamal.In our experiments, the computational costs of a group action in SiGamal-512 with a 256-bit plaintext space are approximately 2.62 times that in CSIDH-512.The second problem of isogeny-based cryptography is that isogeny-based cryptosystems are more inefficient than other candidates of post-quantum cryptosystems.The inefficiency of isogeny-based cryptography could be attributed to computations of group ficients . . . . . . . . . . . .

•Mar 23, 2023•0 citations

Masked torsion point supersingular isogeny Diffie-Hellman : A technique for preventing Castryck-Decru attack against SIDH

R. Krishnaprabha

Collision-resistant hashing and key exchange are two significant Post Quantum cryptography challenges based on isogeny. The challenge in isogeny-based encryption is to identify an isogeny ϕ : E1 → E2, between two given supersingular elliptic curves defined over a finite field Fq. Finding End(E1) and End(E2) is the analogous problem to this one. Supersingular isogeny Diffie Hellman (SIDH) key exchange is designed to be quantum secure. In this instance, we take advantage of the endomorphism ring’s non-commutative property. In SIDH, both the initiator and the response contribute equally to the shared secret. Here, we create both public and private keys and send them through an unsecured channel. Finding isogenies between supersingular elliptic curves is the fundamentally challenging problem. The needed isogeny is calculated using the torsion point information and the degree of the secret isogeny.In July 2022, Wouter Castryck and Thomas Decru devised a successful key recovery attack on SIDH/ SIKE. The attack heavily depends on the torsion point images that Alice and Bob communicate during the protocol and is based on Kani’s “reducibility criterion” for isogenies from products of elliptic curves. We shall present a successful technique to prevent the aforementioned attack in this paper.

AIP conference proceedings•Jan 1, 2025•0 citations

Supersingular Isogenies: A Quantum-Secure Paradigm for Elliptic Curve Cryptography

PAULO SÉRGIO DE ANDRADE

The emergence of quantum computing poses a significant threat to the security of currently deployed public-key cryptosystems, including those based on elliptic curves (ECC). Shor's algorithm can solve the underlying integer factorization and discrete logarithm problems in polynomial time, rendering established cryptographic standards obsolete. This has catalyzed the development of post-quantum cryptography (PQC), a new generation of algorithms resistant to attacks by both classical and quantum computers. Among the most promising PQC candidates are systems based on supersingular isogeny graphs. This paper provides a comprehensive analysis of the supersingular isogeny paradigm as a quantum-secure evolution of elliptic curve cryptography. It begins by introducing the mathematical foundations of elliptic curves and isogenies, which are structure-preserving maps between them. The core of isogeny-based cryptography lies in the conjectured hardness of finding an isogeny path between two given supersingular elliptic curves in the vast isogeny graph. This is fundamentally different from the discrete logarithm problem that underpins traditional ECC. We review the foundational Supersingular Isogeny Diffie-Hellman (SIDH) key exchange protocol and its subsequent realization as the Supersingular Isogeny Key Encapsulation (SIKE) mechanism, which was a candidate in the NIST PQC standardization process. We discuss its advantages, such as small key sizes and perfect forward secrecy, which made it an attractive alternative. However, the paper also presents a balanced view by thoroughly examining the devastating cryptanalytic breakthroughs of 2022 that rendered the original SIDH/SIKE schemes insecure. These attacks, which exploit auxiliary point information, underscore the dynamic nature of PQC research. Despite this setback, the isogeny-based field remains active, with ongoing research into alternative constructions like CSIDH and other variants that are not vulnerable to the known attacks. We conclude that while the initial promise of SIDH/SIKE was broken, the underlying mathematical problem of finding isogenies remains a compelling basis for quantum-secure cryptography, representing a paradigm of active research rather than a discarded concept.

•Nov 11, 2025•0 citations

CSIDH: An Efficient Post-Quantum Commutative Group Action

Wouter Castryck, Tanja Lange, Chloe Martindale +2 more

We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field $$\mathbb F_p$$ , rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.

Lecture notes in computer science•Jan 1, 2018•549 citations

Efficient Commutative PQC Algorithms on Isogenies of Edwards Curves

A. V. Bessalov, Volodymyr Yu. Sokolov, Sergey Abramov

The article presents the author’s works in the field of modifications and modeling of the Post-Quantum Cryptography (PQC) Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) algorithm on non-cyclic supersingular Edwards curves and its predecessor Couveignes-Rostovtsev-Stolbunov (CRS) scheme on ordinary non-cyclic Edwards curves are reviewed. Lower estimates of the computational speed gains of the modified algorithms over the original ones are obtained. The most significant results were obtained by choosing classes of non-cyclic Edwards curves connected as quadratic twist pairs instead of cyclic complete Edwards curves, as well as the method of algorithm randomization as an alternative to “constant time CSIDH”. It is shown that in the CSIDH and Commutative Supersingular Isogeny Key Encapsulation (CSIKE) algorithms, there are two independent cryptosystems with the possibility of parallel computation, eliminating the threat of side-channel attacks. There are four such cryptosystems for the CRS scheme. Integral lower bound estimates of the performance gain of the modified CSIDH algorithm are obtained at 1.5 × 29, and for the CRS scheme are 3 × 29.

Cryptography•Aug 27, 2024•4 citations
We analyze the Commutative Supersingular Isogeny Diffie-Hellman protocol (CSIDH), a novel supersingular isogeny-based key establishment protocol. Our analysis is from three perspectives: \n \nQuantum Cryptanalysis. Building upon quantum attacks on ordinary isogeny-based cryptography, we propose a subexponential-time quantum algorithm for inverting the complex multiplication group action for supersingular elliptic curves, which uses only polynomial quantum space. This improves upon previously-known algorithms which required subexponential quantum space. \n \nOptimization. We develop more efficient algorithms for evaluating the class group action in the context of CSIDH. We consider "strategies"—formerly only considered for Supersingular Isogeny Diffie-Hellman (SIDH)—in the context of CSIDH, and develop systematic methods for optimizing "permutations" of the small primes used in CSIDH, which previously had been treated only in an ad hoc fashion. We also develop a systematic technique to optimize the CSIDH keyspace. These optimizations are complementary to prior work on optimizing CSIDH, including improved field arithmetic, Splitting Isogenies into Multiple Batches (SIMBA), and the two-point method. We apply our optimizations to the CSIDH-512 parameter set and give experimental results. \n \nFault Attacks. We consider physical attacks on static/ephemeral CSIDH in which limited information about which isogenies are "real" and which are "dummy" is revealed. We determine bounds on the number of fault injections required to recover the static secret key, and show that simply reordering the real and dummy isogenies from the ubiquitous "real-then-dummy" ordering to a dynamic random ordering dramatically increases the number of faults required, with negligible impact on the running time of the key exchange protocol (in contrast with prior fault attack countermeasures, which prevent fault attacks entirely at the cost of doubling the running time for key exchange).
The goal of this project is to understand and analyze the supersingular isogeny Diffie Hellman (SIDH), a post-quantum key exchange protocol which security lies on the isogeny-finding problem between supersingular elliptic curves. In order to do so, we first introduce the reader to cryptography focusing on key agreement protocols and motivate the rise of post-quantum cryptography as a necessity with the existence of the model of quantum computation. We review some of the known attacks on the SIDH and finally study some algorithmic aspects to understand how the protocol can be implemented.
Public key cryptography is crucial in current Internet technology.In practice, Rivest, Shamir, Adleman (RSA) cryptography based on Prime Factorization Problem, and Elliptic Curve cryptography based on Discrete Logarithm Problem are typically used.However, both these systems are broken in polynomial time using quantum computers.Therefore, new cryptosystems that are secure against adversaries using quantum computers (postquantum cryptography) should be developed.Isogeny-based cryptography exhibits considerable potential for use in post-quantum cryptography.It is based on Isogeny Problem that is a problem finding an isogeny from two elliptic curves.The greatness of isogeny-based cryptography is that the key length is short and hence compact secure communication is realizable.However, isogeny-based cryptography is yet to mature, and some problems remain.Although isogeny-based cryptography is considered one of the notable candidates for post-quantum cryptography, it has several problems due to its short history.In this thesis, we focus on two problems.The first one is the lack of studies on the security of isogenybased cryptosystems.Another one is that isogeny-based cryptosystems are less efficient than other candidates for post-quantum cryptography.Because of the insufficiency of studies about security, an IND-CPA secure isogeny-based public key encryption scheme without using random functions (idealized hash functions) is yet to be obtained.Some schemes have been proposed for isogeny-based public key encryption schemes; however, these schemes are only OW-CPA secure, which is the minimum security for public key encryption.Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) key exchange is an isogeny-based key exchange scheme based on group actions.Because this scheme is similar to Diffie-Hellman key exchange that has many applications, CSIDH is considered a useful scheme.CSIDH plays a crucial role in cryptography that uses group actions, and there are some applications of CSIDH for signatures and high-level cryptosystems.However, a simple public key encryption scheme based on CSIDH does not have IND-CPA security, whereas ElGamal encryption derived from Diffie-Hellman key exchange has IND-CPA security.This is because CSIDH has less mathematical structure than Diffie-Hellman, and a mathematically natural construction of key encryption based on CSIDH is yet to be obtained.In this thesis, we propose a novel public key encryption scheme, namely SiGamal.This scheme is constructed by adding auxiliary points to CSIDH key exchange.These auxiliary points extend a mathematical structure of CSIDH, and SiGamal is compatible with this extended mathematical structure.Therefore, SiGamal is a more natural ElGamal-like key encryption scheme based on CSIDH.Because SiGamal requires auxiliary points, it requires larger data than CSIDH and is less efficient.However, SiGamal has IND-CPA security without using hash functions under a new security assumption, namely the P-CSSDDH assumption.As an application of this scheme, we proposed Naor-Reingold type pseudo random function based on SiGamal.This pseudo random function (PRF) does not require hash functions, and it costs approximately 8T 3π times SiGamal, where T is the Hamming weight of the input of the PRF.Finally, experiments are conducted to verify the efficiency of SiGamal.In our experiments, the computational costs of a group action in SiGamal-512 with a 256-bit plaintext space are approximately 2.62 times that in CSIDH-512.The second problem of isogeny-based cryptography is that isogeny-based cryptosystems are more inefficient than other candidates of post-quantum cryptosystems.The inefficiency of isogeny-based cryptography could be attributed to computations of group ficients . . . . . . . . . . . .
Collision-resistant hashing and key exchange are two significant Post Quantum cryptography challenges based on isogeny. The challenge in isogeny-based encryption is to identify an isogeny ϕ : E1 → E2, between two given supersingular elliptic curves defined over a finite field Fq. Finding End(E1) and End(E2) is the analogous problem to this one. Supersingular isogeny Diffie Hellman (SIDH) key exchange is designed to be quantum secure. In this instance, we take advantage of the endomorphism ring’s non-commutative property. In SIDH, both the initiator and the response contribute equally to the shared secret. Here, we create both public and private keys and send them through an unsecured channel. Finding isogenies between supersingular elliptic curves is the fundamentally challenging problem. The needed isogeny is calculated using the torsion point information and the degree of the secret isogeny.In July 2022, Wouter Castryck and Thomas Decru devised a successful key recovery attack on SIDH/ SIKE. The attack heavily depends on the torsion point images that Alice and Bob communicate during the protocol and is based on Kani’s “reducibility criterion” for isogenies from products of elliptic curves. We shall present a successful technique to prevent the aforementioned attack in this paper.
The emergence of quantum computing poses a significant threat to the security of currently deployed public-key cryptosystems, including those based on elliptic curves (ECC). Shor's algorithm can solve the underlying integer factorization and discrete logarithm problems in polynomial time, rendering established cryptographic standards obsolete. This has catalyzed the development of post-quantum cryptography (PQC), a new generation of algorithms resistant to attacks by both classical and quantum computers. Among the most promising PQC candidates are systems based on supersingular isogeny graphs. This paper provides a comprehensive analysis of the supersingular isogeny paradigm as a quantum-secure evolution of elliptic curve cryptography. It begins by introducing the mathematical foundations of elliptic curves and isogenies, which are structure-preserving maps between them. The core of isogeny-based cryptography lies in the conjectured hardness of finding an isogeny path between two given supersingular elliptic curves in the vast isogeny graph. This is fundamentally different from the discrete logarithm problem that underpins traditional ECC. We review the foundational Supersingular Isogeny Diffie-Hellman (SIDH) key exchange protocol and its subsequent realization as the Supersingular Isogeny Key Encapsulation (SIKE) mechanism, which was a candidate in the NIST PQC standardization process. We discuss its advantages, such as small key sizes and perfect forward secrecy, which made it an attractive alternative. However, the paper also presents a balanced view by thoroughly examining the devastating cryptanalytic breakthroughs of 2022 that rendered the original SIDH/SIKE schemes insecure. These attacks, which exploit auxiliary point information, underscore the dynamic nature of PQC research. Despite this setback, the isogeny-based field remains active, with ongoing research into alternative constructions like CSIDH and other variants that are not vulnerable to the known attacks. We conclude that while the initial promise of SIDH/SIKE was broken, the underlying mathematical problem of finding isogenies remains a compelling basis for quantum-secure cryptography, representing a paradigm of active research rather than a discarded concept.
We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field Fp\mathbb F_pFp​ , rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.
The article presents the author’s works in the field of modifications and modeling of the Post-Quantum Cryptography (PQC) Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) algorithm on non-cyclic supersingular Edwards curves and its predecessor Couveignes-Rostovtsev-Stolbunov (CRS) scheme on ordinary non-cyclic Edwards curves are reviewed. Lower estimates of the computational speed gains of the modified algorithms over the original ones are obtained. The most significant results were obtained by choosing classes of non-cyclic Edwards curves connected as quadratic twist pairs instead of cyclic complete Edwards curves, as well as the method of algorithm randomization as an alternative to “constant time CSIDH”. It is shown that in the CSIDH and Commutative Supersingular Isogeny Key Encapsulation (CSIKE) algorithms, there are two independent cryptosystems with the possibility of parallel computation, eliminating the threat of side-channel attacks. There are four such cryptosystems for the CRS scheme. Integral lower bound estimates of the performance gain of the modified CSIDH algorithm are obtained at 1.5 × 29, and for the CRS scheme are 3 × 29.