In this work, we present the theory behind Elliptic Curve Cryptography (ECC) and Isogeny-based cryptography. We start with a quick introduction to Complexity Theory and Cryptography. We give a detailed description of elliptic curves and discuss how they are used to create secure protocols. We present the strength of this scheme and also its weaknesses regarding quantum computation. To show the necessity for other protocols, we review some basic concepts of Quantum Computing and present how Shor's Quantum Algorithm breaks ECC. Then, we survey the rich theory of isogenies between ordinary and supersingular elliptic curves to end with cryptographic protocols, that use these isogenies to create post-quantum cryptographic systems.
In this work, we present the theory behind Elliptic Curve Cryptography (ECC) and Isogeny-based cryptography. We start with a quick introduction to Complexity Theory and Cryptography. We give a detailed description of elliptic curves and discuss how they are used to create secure protocols. We present the strength of this scheme and also its weaknesses regarding quantum computation. To show the necessity for other protocols, we review some basic concepts of Quantum Computing and present how Shor's Quantum Algorithm breaks ECC. Then, we survey the rich theory of isogenies between ordinary and supersingular elliptic curves to end with cryptographic protocols, that use these isogenies to create post-quantum cryptographic systems.
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.
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.
In this article, we discuss how algebraic geometry, especially the isogenies and elliptic curves, have been used to construct secure post-quantum cryptographic systems. Since quantum computing is a very big threat to conventional cryptographic techniques, it is essential to develop new strategies that would enhance protection of data in quantum age. Algebraic geometry provides such solutions as the elliptic curve cryptography and the protocols based on isogenic, which is also resistant to the attacks of quantum algorithms. The article explores the mathematical basis of these cryptographic techniques, their effectiveness, scalability and security. It is noteworthy that isogeny-based cryptography schemes such as the Supersingular Isogeny Diffie-Hellman (SIDH) and Supersingular Isogeny Key Encapsulation (SIKE) prove that isogeny-based cryptography is capable of secure key exchange and encapsulation. The results indicate that algebraic geometry is not only enhancing the cryptography systems, but also opening up a reasonable channel in which strong post-quantum systems can be created. The future of secure communication in a quantum-driven world has profound implications to the methods.
Isogeny-based cryptography using supersingular elliptic curves --- most prominently, the constructions of De Feo-Jao-Plut --- is one of the few practical candidates for post-quantum public key cryptography. Its formidable security claim is earned through the continual exploration of quantum algorithms for `isogeny problems' and the assessment of the threat they pose to supersingular isogeny-based cryptography. We survey the rich history of classical and quantum algorithms for isogeny problems, and close with an original result --- a quantum algorithm for the general supersingular isogeny problem, based on the discovery of Delfs and Galbraith in 2013 --- that has exponential-complexity in general and subexponential complexity in an important sub-case. As yet, this algorithm poses a limited threat to the schemes of De Feo-Jao-Plut; however, it is an important algorithm to consider, for it provides insight into the structure of supersingular curves and the isogenies between them, and may lead to newer destructive quantum algorithms.
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.
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.