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

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

共起 守谷

Published Mar 23, 2023• 0 citations
Publisher

Abstract

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

DOI
10.15083/0002011957

Related papers

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

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

Isogeny-based cryptosystems for post-quantum security

R. Kapgate, Dheeravath Raju, Chetansinh Vaghela +3 more

The fast progress of quantum computing is a serious threat to classical cryptographic schemes like RSA and elliptic curve cryptography, and it is time to come up with safe postquantum schemes.One of the new solutions is isogeny-based cryptography which has attracted attention because of its good-security basis and comparatively small key sizes.Nevertheless, currently used post-quantum cryptographic (PQC) designs, such as lattice-based and codebased ones, are typically characterized by the high key sizes, high computational costs, or scaling issues, with the necessity to have a well-balanced and efficient cryptographic design.This paper presents a powerful isogeny-based cryptosystem, which can allow safe communication in the post-quantum context.The mathematical complexity of isogenies over supersingular elliptic curves forms the foundation of the proposed framework and it has a structured architecture comprising of parameterization, key generation, encryption/decryption and communication layers.The design of the optimization of algorithms to generate keys, exchange keys securely and encrypt messages using shared secret derivation mechanisms is part of the methodology.Security analysis is also carried out to assess the resistance to quantum attacks and against known cryptanalytic vulnerabilities.The metrics used to conduct performance evaluation are computed cost, key size, and latency, and the results are compared to typical PQC schemes, like lattice-based (Kyber) and code-based (McEliece) systems.The results show that the model proposed has much smaller key sizes (330 bytes public key) with moderate computational efficiency although a little bit more latency than lattice-based methods.

Journal of Discrete Mathematical Sciences and Cryptography•Oct 31, 2026•0 citations

Elliptic Curve Cryptography Reimagined: Post-Quantum Resilience Through Isogeny Graphs

PAULO SÉRGIO DE ANDRADE

The impending arrival of large-scale quantum computers poses a significant threat to modern public-key cryptography, which is largely based on the hardness of integer factorization and the discrete logarithm problem. Elliptic Curve Cryptography (ECC), a cornerstone of current digital security, is particularly vulnerable to attacks by quantum algorithms, notably Shor's algorithm. This has catalyzed the development of Post-Quantum Cryptography (PQC), a new generation of cryptographic systems designed to be secure against both classical and quantum adversaries. Among the various PQC families, isogeny-based cryptography has emerged as a compelling, albeit complex, candidate. This paper explores the reimagination of elliptic curve principles for a post-quantum world through the lens of isogeny graphs. We provide a comprehensive overview of the transition from classical ECC to isogeny-based schemes, detailing the mathematical foundations of elliptic curve isogenies and the construction of supersingular isogeny graphs. The core of our analysis focuses on how the problem of finding a secret isogeny path between two curves in this graph forms the basis for quantum-resistant cryptographic protocols. We review the evolution of seminal protocols such as Supersingular Isogeny Diffie-Hellman (SIDH) and its variants, discussing their initial promise. Crucially, the paper also addresses the recent groundbreaking cryptanalytic attacks on SIDH, which have reshaped the landscape of isogeny-based cryptography. We analyze the implications of these attacks and the ongoing research to develop new, more secure isogeny-based schemes like SQISign. By comparing the performance metrics (key size, performance, security) of isogeny-based systems with other leading PQC candidates, such as those based on lattices and codes, this paper offers a balanced perspective on their potential role in future cryptographic standards.

•Nov 19, 2025•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

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
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 . . . . . . . . . . . .
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 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.
The fast progress of quantum computing is a serious threat to classical cryptographic schemes like RSA and elliptic curve cryptography, and it is time to come up with safe postquantum schemes.One of the new solutions is isogeny-based cryptography which has attracted attention because of its good-security basis and comparatively small key sizes.Nevertheless, currently used post-quantum cryptographic (PQC) designs, such as lattice-based and codebased ones, are typically characterized by the high key sizes, high computational costs, or scaling issues, with the necessity to have a well-balanced and efficient cryptographic design.This paper presents a powerful isogeny-based cryptosystem, which can allow safe communication in the post-quantum context.The mathematical complexity of isogenies over supersingular elliptic curves forms the foundation of the proposed framework and it has a structured architecture comprising of parameterization, key generation, encryption/decryption and communication layers.The design of the optimization of algorithms to generate keys, exchange keys securely and encrypt messages using shared secret derivation mechanisms is part of the methodology.Security analysis is also carried out to assess the resistance to quantum attacks and against known cryptanalytic vulnerabilities.The metrics used to conduct performance evaluation are computed cost, key size, and latency, and the results are compared to typical PQC schemes, like lattice-based (Kyber) and code-based (McEliece) systems.The results show that the model proposed has much smaller key sizes (330 bytes public key) with moderate computational efficiency although a little bit more latency than lattice-based methods.
The impending arrival of large-scale quantum computers poses a significant threat to modern public-key cryptography, which is largely based on the hardness of integer factorization and the discrete logarithm problem. Elliptic Curve Cryptography (ECC), a cornerstone of current digital security, is particularly vulnerable to attacks by quantum algorithms, notably Shor's algorithm. This has catalyzed the development of Post-Quantum Cryptography (PQC), a new generation of cryptographic systems designed to be secure against both classical and quantum adversaries. Among the various PQC families, isogeny-based cryptography has emerged as a compelling, albeit complex, candidate. This paper explores the reimagination of elliptic curve principles for a post-quantum world through the lens of isogeny graphs. We provide a comprehensive overview of the transition from classical ECC to isogeny-based schemes, detailing the mathematical foundations of elliptic curve isogenies and the construction of supersingular isogeny graphs. The core of our analysis focuses on how the problem of finding a secret isogeny path between two curves in this graph forms the basis for quantum-resistant cryptographic protocols. We review the evolution of seminal protocols such as Supersingular Isogeny Diffie-Hellman (SIDH) and its variants, discussing their initial promise. Crucially, the paper also addresses the recent groundbreaking cryptanalytic attacks on SIDH, which have reshaped the landscape of isogeny-based cryptography. We analyze the implications of these attacks and the ongoing research to develop new, more secure isogeny-based schemes like SQISign. By comparing the performance metrics (key size, performance, security) of isogeny-based systems with other leading PQC candidates, such as those based on lattices and codes, this paper offers a balanced perspective on their potential role in future cryptographic standards.
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 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.