Projects per year
Abstract
Finding isogenies between supersingular elliptic curves is a natural algorithmic problem which is known to be equivalent to computing the curves’ endomorphism rings.
When the isogeny is additionally required to have a specific known degree d, the problem appears to be somewhat different in nature, yet its hardness is also required for isogeny-based cryptography.
Let E1,E2 be supersingular elliptic curves over Fp2. We present improved classical and quantum algorithms that compute an isogeny of degree d between E1 and E2 if it exists. Let d ≈ p1/2+ε for some ε >0. Our essentially memory-free algorithms have better time complexity than meet-in-the-middle algorithms, which require exponential memory storage, in the range 1/2 ≤ ε ≤ 3/4 on a classical computer. For quantum computers, we improve the time complexity in the range 0 < ε <5/2.
Our strategy is to compute the endomorphism rings of both curves, compute the reduced norm form associated to Hom(E1,E2) and try to represent the integer d as a solution of this form. We present multiple approaches to solving this problem which combine guessing certain variables exhaustively (or use Grover’s search in the quantum case) with methods for solving quadratic Diophantine equations such as Cornacchia’s algorithm and multivariate variants of Coppersmith’s method. We provide implementations and experimental results for the different approaches. A solution to the norm form can then be efficiently translated to recover the sought-after isogeny using well-known techniques. As a consequence of our results we show that a recently introduced signature scheme from [3] does not reach NIST level I security.
When the isogeny is additionally required to have a specific known degree d, the problem appears to be somewhat different in nature, yet its hardness is also required for isogeny-based cryptography.
Let E1,E2 be supersingular elliptic curves over Fp2. We present improved classical and quantum algorithms that compute an isogeny of degree d between E1 and E2 if it exists. Let d ≈ p1/2+ε for some ε >0. Our essentially memory-free algorithms have better time complexity than meet-in-the-middle algorithms, which require exponential memory storage, in the range 1/2 ≤ ε ≤ 3/4 on a classical computer. For quantum computers, we improve the time complexity in the range 0 < ε <5/2.
Our strategy is to compute the endomorphism rings of both curves, compute the reduced norm form associated to Hom(E1,E2) and try to represent the integer d as a solution of this form. We present multiple approaches to solving this problem which combine guessing certain variables exhaustively (or use Grover’s search in the quantum case) with methods for solving quadratic Diophantine equations such as Cornacchia’s algorithm and multivariate variants of Coppersmith’s method. We provide implementations and experimental results for the different approaches. A solution to the norm form can then be efficiently translated to recover the sought-after isogeny using well-known techniques. As a consequence of our results we show that a recently introduced signature scheme from [3] does not reach NIST level I security.
Original language | English |
---|---|
Title of host publication | Advances in Cryptology – CRYPTO 2024 |
Subtitle of host publication | 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part V |
Editors | Leonid Reyzin, Douglas Stebila |
Publisher | Springer |
Pages | 183-217 |
Number of pages | 35 |
Volume | 5 |
ISBN (Electronic) | 9783031683886 |
ISBN (Print) | 9783031683879 |
DOIs | |
Publication status | Published - 17 Aug 2024 |
Event | CRYPTO 2024 - Duration: 18 Aug 2024 → 22 Aug 2024 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 14924 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | CRYPTO 2024 |
---|---|
Period | 18/08/24 → 22/08/24 |
Bibliographical note
Publisher Copyright:© International Association for Cryptologic Research 2024.
Keywords
- cryptanalysis
- isogeny computation
- Post-quantum cryptography
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
Fingerprint
Dive into the research topics of 'Improved algorithms for finding fixed-degree isogenies between supersingular elliptic curves'. Together they form a unique fingerprint.Projects
- 1 Active
-
Post-Quantum Cryptography: a Cryptanalysis Approach
Petit, C. (Principal Investigator)
Engineering & Physical Science Research Council
1/10/21 → 30/09/26
Project: Research Councils