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)

Papers

[velusqrt] (PDF) Daniel J. Bernstein, Luca De Feo, Antonin Leroux, Benjamin Smith. "Faster computation of isogenies of large prime degree." Algorithmic Number Theory Symposium 2020. Document ID: 44d5ade1c1778d86a5b035ad20f880c08031a1dc. Date: 2020.06.16. Supersedes: (PDF) 2020.03.23. (PDF) 2020.03.20.

Funding

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).