Talk
eSeminar: Faster Evaluation of Isogenies of Large Prime Degree
Talk by Dr. Luca De Feo
Date: 29.04.20 Time: 16.00 - 17.00 Room:
(**This eSeminar will take place on Zoom, using same meeting details as previous seminars. If you do not have meeting details, please contact karan.khathuria@math.uzh.ch. This talk will also be live streamed at https://defeo.lu/tube/**)
An isogeny is a non-zero morphism of elliptic curves. The isogeny evaluation problem asks, given a description of an isogeny φ:E→E' and of a point P∈E, to compute φ(P). It is a fundamental algorithmic problem in computational number theory, and has gained a fair amount interest thanks to the recent developments in isogeny-based cryptography.
The "atomic" case for isogeny evaluation is that of isogenies of prime degree, on top of which algorithms for isogenies of any degree are easily constructed. For the prime degree case, the classic solution is based on Vélu's formulas, or any of their optimized variants. Vélu's formulas take as input the kernel of the isogeny, e.g., as a list of points, and output the isogeny as a pair of rational functions, which are then used to evaluate the isogeny at the point. This algorithm can be implemented in time linear in the isogeny degree, which is asymptotically optimal in general; however in the fundamental case where the kernel can be described by a single generator over the base field, one could hope to find a more efficient algorithm which sidesteps the computation of the rational functions.
This is exactly what I will present in this talk: starting from a very simple idea, already used by Pollard, Strassen and Chudnovsky², among others, I will present a baby-step/giant-step algorithm that solves the isogeny evaluation problem in time and space proportional to the square root of the degree. I will explain why this is important for isogeny-based cryptography, and highlight several applications where the new algorithm produces practical speedups ranging from the unimpressive to the spectacular.
This is joint work with D.J. Bernstein, A. Leroux and B. Smith, the preprint can be found at https://ia.cr/2020/341. The talk will be live streamed at https://defeo.lu/tube/