Let E/𝔽q be an elliptic curve, and P a point in E(𝔽q) of prime order ℓ. Vélu's formulae let us compute a quotient curve E' = E/〈P〉 and rational maps defining a quotient isogeny φ:E→E' in Õ(ℓ) 𝔽q-operations, where the Õ is uniform in q. This work shows how to compute E', and φ(Q) for Q in E(𝔽q), using only Õ(√ℓ) 𝔽q-operations, where the Õ is again uniform in q. As an application, this work speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.
Contributors (alphabetical order)
- Daniel J. Bernstein (Department of Computer Science, University of Illinois at Chicago, USA, and Horst Görtz Institute for IT Security, Ruhr University Bochum, Germany)
- Luca De Feo (IBM Research, Zürich, Switzerland)
- Antonin Leroux (DGA, Inria and École Polytechnique, France)
- Benjamin Smith (Inria and École Polytechnique, France)
[velusqrt] (PDF) Daniel J. Bernstein, Luca De Feo, Antonin Leroux, Benjamin Smith. "Faster computation of isogenies of large prime degree." Document ID: 44d5ade1c1778d86a5b035ad20f880c08031a1dc. Date: 2020.03.23. Supersedes: (PDF) 2020.03.20.
Part of this work was carried out while Bernstein was visiting the Simons Institute for the Theory of Computing. This work was supported by the Cisco University Research Program, by DFG Cluster of Excellence 2092 "CASA: Cyber Security in the Age of Large-Scale Adversaries", and by the U.S. National Science Foundation under grant 1913167. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation" (or other funding agencies).
Version: This is version 2020.03.23 of the "Intro" web page.