Paper 2023/1618
Improved algorithms for finding fixeddegree isogenies between supersingular elliptic curves
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 in isogenybased cryptography. Let $E_1,E_2$ be supersingular elliptic curves over $\mathbb{F}_{p^2}$. We present improved classical and quantum algorithms that compute an isogeny of degree~$d$ between~$E_1$ and~$E_2$ if it exists. Let $d \approx p^{1/2+ \epsilon}$ for some $\epsilon>0$. Our essentially memoryfree algorithms have better time complexity than meetinthemiddle algorithms, which require exponential memory storage, in the range $1/2\leq\epsilon\leq 3/4$ on a classical computer. For quantum computers, we improve the time complexity in the range $0<\epsilon<5/2$. Our strategy is to compute the endomorphism rings of both curves, compute the reduced norm form associated to $\operatorname{Hom}(E_1,E_2)$ 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. For the different approaches, we provide implementations and experimental results. A solution to the norm form can be then be efficiently translated to recover the soughtafter isogeny using wellknown techniques. As a consequence of our results we show that a recently introduced signature scheme published at ACNS 2024 does not reach NIST level I security.
Note: Attack on ACNS paper added and some more graphics
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Keywords
 Isogenybased cryptographyPostquantum cryptographyPure isogeny problems
 Contact author(s)

benjamin bencina @ gmail com
kutasp @ gmail com
research @ simonphilipp com
christophe petit @ ulb be
stopar miha @ gmail com
C Weitkaemper @ pgr bham ac uk  History
 20240301: last of 2 revisions
 20231018: received
 See all versions
 Short URL
 https://ia.cr/2023/1618
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1618, author = {Benjamin Benčina and Péter Kutas and SimonPhilipp Merz and Christophe Petit and Miha Stopar and Charlotte Weitkämper}, title = {Improved algorithms for finding fixeddegree isogenies between supersingular elliptic curves}, howpublished = {Cryptology ePrint Archive, Paper 2023/1618}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1618}}, url = {https://eprint.iacr.org/2023/1618} }