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

arXiv:2602.02263

On the Spectral theory of Isogeny Graphs and Quantum Sampling of Secure Supersingular Elliptic curves

Maher Mamah, Jake Doliskani, David Jao

quant-phmath.NTSubmitted Feb 2, 2026• Announced Feb 3, 2026• 0 citations• Revised Mar 22, 2026 (v2)
v1 · Feb 2, 2026v2 · Mar 22, 2026v3 · Sep 21, 2026
arXivHTMLPDF

Abstract

In this paper, we study the problem of sampling random supersingular elliptic curves with unknown endomorphism rings. This problem has recently gained considerable attention as many isogeny-based cryptographic protocols require such ``secure'' curves for instantation, while existing methods achieve this only in a trusted-setup setting. We present the first provable quantum polynomial-time algorithms for sampling such curves with high probability, one of which is based on an algorithm of Booher et. al. One variant runs heuristically in $\tilde{O}(\log^{4} p)$ quantum gate complexity, and in $\tilde{O}(\log^{13} p)$ under the Generalized Riemann Hypothesis, and outputs a curve that is provably secure assuming average-case hardness of the endomorphism ring problem. Another variant samples uniform $\mathcal{O}$-oriented curves with unknown endomorphism rings, for any imaginary quadratic order $\mathcal O$, with security based on the hardness of Vectorization problem. When accompanied by an interactive quantum computation verification protocol our algorithms provide a secure instantiation of the CGL hash function and related primitives. Our analysis relies on a new spectral delocalization result for supersingular $\ell$-isogeny graphs: we prove the Quantum Unique Ergodicity conjecture and provide numerical evidence for complete eigenvector delocalization. We also prove a stronger $\varepsilon$-separation property for eigenvalues of isogeny graphs than that predicted in the quantum money protocol of Kane, Sharif, and Silverberg, thereby removing a key heuristic assumption in their construction.

Comments
29 pages with two figures

Related papers

Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.

David Jao, Luca De Feo

We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [19]. We add a new zero-knowledge identification scheme, and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.

•Jan 1, 2011•6 citations

Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies

Luca De Feo, David Jao, Jérôme Plût

Abstract We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the non-commutativity of the endomorphism ring. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [Lecture Notes in Comput. Sci. 7071, Springer (2011), 19–34]. We add a new zero-knowledge identification scheme and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.

Journal of Mathematical Cryptology•Jun 11, 2014•435 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

Constructing elliptic curve isogenies in quantum subexponential time

Andrew M. Childs, David Jao, Vladimir Soukharev

Abstract. Given two ordinary elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit a nonzero isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a new subexponential-time quantum algorithm for constructing nonzero isogenies between two such elliptic curves, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, and represents the first nontrivial application of Kuperberg's quantum algorithm for finding hidden shifts. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems. As part of this work, we also present the first classical algorithm for evaluating isogenies having provably subexponential running time in the cardinality of the base field under GRH.

arXiv:1012.4019•Journal of Mathematical Cryptology•Oct 23, 2013•245 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

Post-Quantum Elliptic Curve Cryptography

Vladimir Soukharev

We propose and develop new schemes for post-quantum cryptography based on isogenies over elliptic curves. First we show that ordinary elliptic curves are have less than exponential security against quantum computers. These results were used as the motivation for De Feo, Jao and Pl\\^ut's construction of public key cryptosystems using supersingular elliptic curve isogenies. We extend their construction and show that isogenies between supersingular elliptic curves can be used as the underlying hard mathematical problem for other quantum-resistant schemes. For our second contribution, we propose is an undeniable signature scheme based on elliptic curve isogenies. We prove its security under certain reasonable number-theoretic computational assumptions for which no efficient quantum algorithms are known. This proposal represents only the second known quantum-resistant undeniable signature scheme, and the first such scheme secure under a number-theoretic complexity assumption. Finally, we also propose a security model for evaluating the security of authenticated encryption schemes in the post-quantum setting. Our model is based on a combination of the classical Bellare-Namprempre security model for authenticated encryption together with modifications from Boneh and Zhandry to handle message authentication against quantum adversaries. We give a generic construction based on Bellare-Namprempre for producing an authenticated encryption protocol from any quantum-resistant symmetric-key encryption scheme together with any digital signature scheme or MAC admitting any classical security reduction to a quantum-computationally hard problem. We apply the results and show how we can explicitly construct authenticated encryption schemes based on isogenies.

•May 16, 2016•1 citation
In this paper, we study the problem of sampling random supersingular elliptic curves with unknown endomorphism rings. This problem has recently gained considerable attention as many isogeny-based cryptographic protocols require such ``secure'' curves for instantation, while existing methods achieve this only in a trusted-setup setting. We present the first provable quantum polynomial-time algorithms for sampling such curves with high probability, one of which is based on an algorithm of Booher et. al. One variant runs heuristically in O~(log⁡4p)\tilde{O}(\log^{4} p)O~(log4p) quantum gate complexity, and in O~(log⁡13p)\tilde{O}(\log^{13} p)O~(log13p) under the Generalized Riemann Hypothesis, and outputs a curve that is provably secure assuming average-case hardness of the endomorphism ring problem. Another variant samples uniform O\mathcal{O}O-oriented curves with unknown endomorphism rings, for any imaginary quadratic order O\mathcal OO, with security based on the hardness of Vectorization problem. When accompanied by an interactive quantum computation verification protocol our algorithms provide a secure instantiation of the CGL hash function and related primitives.
Our analysis relies on a new spectral delocalization result for supersingular ℓ\ellℓ-isogeny graphs: we prove the Quantum Unique Ergodicity conjecture and provide numerical evidence for complete eigenvector delocalization. We also prove a stronger ε\varepsilonε-separation property for eigenvalues of isogeny graphs than that predicted in the quantum money protocol of Kane, Sharif, and Silverberg, thereby removing a key heuristic assumption in their construction.
We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [19]. We add a new zero-knowledge identification scheme, and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.
Abstract We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the non-commutativity of the endomorphism ring. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [Lecture Notes in Comput. Sci. 7071, Springer (2011), 19–34]. We add a new zero-knowledge identification scheme and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.
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.
Abstract. Given two ordinary elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit a nonzero isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a new subexponential-time quantum algorithm for constructing nonzero isogenies between two such elliptic curves, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, and represents the first nontrivial application of Kuperberg's quantum algorithm for finding hidden shifts. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems. As part of this work, we also present the first classical algorithm for evaluating isogenies having provably subexponential running time in the cardinality of the base field under GRH.
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 and develop new schemes for post-quantum cryptography based on isogenies over elliptic curves. First we show that ordinary elliptic curves are have less than exponential security against quantum computers. These results were used as the motivation for De Feo, Jao and Pl\\^ut's construction of public key cryptosystems using supersingular elliptic curve isogenies. We extend their construction and show that isogenies between supersingular elliptic curves can be used as the underlying hard mathematical problem for other quantum-resistant schemes. For our second contribution, we propose is an undeniable signature scheme based on elliptic curve isogenies. We prove its security under certain reasonable number-theoretic computational assumptions for which no efficient quantum algorithms are known. This proposal represents only the second known quantum-resistant undeniable signature scheme, and the first such scheme secure under a number-theoretic complexity assumption. Finally, we also propose a security model for evaluating the security of authenticated encryption schemes in the post-quantum setting. Our model is based on a combination of the classical Bellare-Namprempre security model for authenticated encryption together with modifications from Boneh and Zhandry to handle message authentication against quantum adversaries. We give a generic construction based on Bellare-Namprempre for producing an authenticated encryption protocol from any quantum-resistant symmetric-key encryption scheme together with any digital signature scheme or MAC admitting any classical security reduction to a quantum-computationally hard problem. We apply the results and show how we can explicitly construct authenticated encryption schemes based on isogenies.