International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Accelerating the Delfs-Galbraith algorithm with fast subfield root detection

Authors:
Maria Corte-Real Santos , University College London
Craig Costello , Microsoft Research
Jia Shi , University of Waterloo
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: We give a new algorithm for finding an isogeny from a given supersingular elliptic curve $E/\F_{p^2}$ to a subfield elliptic curve $E'/\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 avoiding expensive root-finding algorithms. In the special case when $f=\Upphi_{\ell,p}(X,j) \in \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 (i.e. the foundational problem underlying isogeny-based cryptography), and has immediate implications on the bit-security of schemes like B-SIDH and SQISign for which Delfs-Galbraith is the best known classical attack.
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32134,
  title={Accelerating the Delfs-Galbraith algorithm with fast subfield root detection},
  publisher={Springer-Verlag},
  author={Maria Corte-Real Santos and Craig Costello and Jia Shi},
  year=2022
}