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

Cryptography

Efficient Commutative PQC Algorithms on Isogenies of Edwards Curves

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

Published Aug 27, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.3390/cryptography8030038

Related papers

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

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

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

Jason T. LeGrow

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).

•Aug 19, 2020•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

Elliptic Curve Isogenies: A New Frontier for Post-Quantum Cryptography

PAULO SÉRGIO DE ANDRADE

The rise of quantum computing poses a significant threat to contemporary public-key cryptography, which relies on problems like integer factorization and the discrete logarithm, both of which are solvable in polynomial time by Shor's algorithm. This has prompted a global effort to develop and standardize post-quantum cryptographic primitives that are resistant to attacks by both classical and quantum computers. Among the various families of post-quantum candidates, isogeny-based cryptography has emerged as a particularly compelling, albeit challenging, alternative. This paper explores the mathematical foundations of elliptic curve isogenies and their application as a basis for quantum-resistant cryptographic protocols. We delve into the structure of supersingular elliptic curves and the associated isogeny graphs, which form the basis for the conjectured hardness of the underlying computational problems. The Supersingular Isogeny Diffie-Hellman (SIDH) protocol and its derivative, Supersingular Isogeny Key Encapsulation (SIKE), are examined in detail as principal examples of this cryptographic paradigm. We analyze their key advantages, most notably their exceptionally small key sizes, which offer significant benefits for constrained environments. However, the security landscape of isogeny-based cryptography has been dramatically reshaped by recent cryptanalytic breakthroughs that completely broke the SIKE protocol. This paper analyzes the nature of these attacks, discussing the vulnerabilities they exploited and the profound implications for the field. We conclude by surveying the current state of isogeny-based cryptography in the aftermath of these developments, outlining the proposed countermeasures, alternative designs, and the open research questions that define the new frontier for this promising area of post-quantum cryptography.

•Nov 14, 2025•0 citations

Isogeny-Based Post-Quantum Cryptography

Ashneet Khandpur Singh

The present thesis focus on one of the post-quantum cryptosystems, in particular, the isogenybased cryptography. Because of its certain properties like the hard problem of computing isogenies between two elliptic curves, it makes it to be one of the few candidates for post-quantum cryptography. We will study the algorithms based on this isogeny-based cryptography and why they are useful against quantum computers. One of these algorithms is the Supersingular Isogeny Diffie Hellman (SIDH), a candidate for substituing ECDH in the Signal protocol to make it quantum safe.

•Oct 1, 2019•0 citations
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.
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.
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 . . . . . . . . . . . .
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 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.
The rise of quantum computing poses a significant threat to contemporary public-key cryptography, which relies on problems like integer factorization and the discrete logarithm, both of which are solvable in polynomial time by Shor's algorithm. This has prompted a global effort to develop and standardize post-quantum cryptographic primitives that are resistant to attacks by both classical and quantum computers. Among the various families of post-quantum candidates, isogeny-based cryptography has emerged as a particularly compelling, albeit challenging, alternative. This paper explores the mathematical foundations of elliptic curve isogenies and their application as a basis for quantum-resistant cryptographic protocols. We delve into the structure of supersingular elliptic curves and the associated isogeny graphs, which form the basis for the conjectured hardness of the underlying computational problems. The Supersingular Isogeny Diffie-Hellman (SIDH) protocol and its derivative, Supersingular Isogeny Key Encapsulation (SIKE), are examined in detail as principal examples of this cryptographic paradigm. We analyze their key advantages, most notably their exceptionally small key sizes, which offer significant benefits for constrained environments. However, the security landscape of isogeny-based cryptography has been dramatically reshaped by recent cryptanalytic breakthroughs that completely broke the SIKE protocol. This paper analyzes the nature of these attacks, discussing the vulnerabilities they exploited and the profound implications for the field. We conclude by surveying the current state of isogeny-based cryptography in the aftermath of these developments, outlining the proposed countermeasures, alternative designs, and the open research questions that define the new frontier for this promising area of post-quantum cryptography.
The present thesis focus on one of the post-quantum cryptosystems, in particular, the isogenybased cryptography. Because of its certain properties like the hard problem of computing isogenies between two elliptic curves, it makes it to be one of the few candidates for post-quantum cryptography. We will study the algorithms based on this isogeny-based cryptography and why they are useful against quantum computers. One of these algorithms is the Supersingular Isogeny Diffie Hellman (SIDH), a candidate for substituing ECDH in the Signal protocol to make it quantum safe.