Welcome to the resource topic for 2021/1488
Title:
Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
Authors: Maria Corte-Real Santos, Craig Costello, and Jia Shi
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.
ePrint: https://eprint.iacr.org/2021/1488
Talk: https://www.youtube.com/watch?v=ZRnRF_odIf0
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/137/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .