Paper 2021/1488

Accelerating the Delfs-Galbraith algorithm with fast subfield root detection

Maria Corte-Real Santos, University College London
Craig Costello, Microsoft Research (United States)
Jia Shi, University of Waterloo
Abstract

We give a new algorithm for finding an isogeny from a given supersingular elliptic curve $E/\mathbb{F}_{p^2}$ to a subfield elliptic curve $E'/\mathbb{F}_p$, which is the bottleneck step of the Delfs-Galbraith algorithm for the general supersingular isogeny problem. Our core ingredient is a novel method of rapidly determining whether a polynomial $f \in L[X]$ has any roots in a subfield $K \subset L$, while crucially avoiding expensive root-finding algorithms. In the special case when $f=\Phi_{\ell,p}(X,j) \in \mathbb{F}_{p^2}[X]$, i.e. when $f$ is the $\ell$-th modular polynomial evaluated at a supersingular $j$-invariant, this provides a means of efficiently determining whether there is an $\ell$-isogeny connecting the corresponding elliptic curve to a subfield curve. Together with the traditional Delfs-Galbraith walk, inspecting many $\ell$-isogenous neighbours in this way allows us to search through a larger proportion of the supersingular set per unit of time. Though the asymptotic $\tilde{O}(p^{1/2})$ complexity of our improved algorithm remains unchanged from that of the original Delfs-Galbraith algorithm, our theoretical analysis and practical implementation both show a significant reduction in the runtime of the subfield search. This sheds new light on the concrete hardness of the general supersingular isogeny problem, the foundational problem underlying isogeny-based cryptography.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in CRYPTO 2022
Keywords
Isogeny-based cryptography supersingular isogeny problem Delfs-Galbraith algorithm.
Contact author(s)
maria santos 20 @ ucl ac uk
craigco @ microsoft com
j96shi @ uwaterloo ca
History
2022-06-21: last of 2 revisions
2021-11-15: received
See all versions
Short URL
https://ia.cr/2021/1488
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1488,
      author = {Maria Corte-Real Santos and Craig Costello and Jia Shi},
      title = {Accelerating the Delfs-Galbraith algorithm with fast subfield root detection},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1488},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1488}},
      url = {https://eprint.iacr.org/2021/1488}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.