Faster computation of isogenies of large prime degree

Let $E / F_{q}$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi mathvariant="bold-script">ℰ</mi><mo class="MathClass-bin">∕</mo><msub><mrow><mi mathvariant="double-struck">𝔽</mi></mrow><mrow><mi>q</mi></mrow></msub></mrow></math>$ be an elliptic curve, and $P$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>P</mi></mrow></math>$ a point in $E (F_{q})$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi mathvariant="bold-script">ℰ</mi><mrow><mo class="MathClass-open">(</mo><mrow><msub><mrow><mi mathvariant="double-struck">𝔽</mi></mrow><mrow><mi>q</mi></mrow></msub></mrow><mo class="MathClass-close">)</mo></mrow></mrow></math>$ of prime order $ℓ$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>ℓ</mi></mrow></math>$ . Vélu’s formulæ let us compute a quotient curve $E^{'} = E / ⟨ P ⟩$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><msup><mrow><mi mathvariant="bold-script">ℰ</mi></mrow><mrow><mi>′</mi></mrow></msup> <mo class="MathClass-rel">=</mo> <mi mathvariant="bold-script">ℰ</mi><mo class="MathClass-bin">∕</mo><mrow><mo class="MathClass-open">⟨</mo><mrow><mi>P</mi></mrow><mo class="MathClass-close">⟩</mo></mrow></mrow></math>$ and rational maps defining a quotient isogeny $ϕ : E \to E^{'}$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>ϕ</mi> <mo class="MathClass-punc">:</mo> <mi mathvariant="bold-script">ℰ</mi><mo class="MathClass-rel">→</mo><msup><mrow><mi mathvariant="bold-script">ℰ</mi></mrow><mrow><mi>′</mi></mrow></msup></mrow></math>$ in $˜ O (ℓ)$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mover accent="false"><mrow><mi>O</mi></mrow><mo class="MathClass-op">˜</mo></mover><mrow><mo class="MathClass-open">(</mo><mrow><mi>ℓ</mi></mrow><mo class="MathClass-close">)</mo></mrow></mrow></math>$ $F_{q}$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><msub><mrow><mi mathvariant="double-struck">𝔽</mi></mrow><mrow><mi>q</mi></mrow></msub></mrow></math>$ -operations, where the $˜ O$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mover accent="false"><mrow><mi>O</mi></mrow><mo class="MathClass-op">˜</mo></mover></mrow></math>$ is uniform in $q$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>q</mi></mrow></math>$ . This article shows how to compute $E^{'}$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><msup><mrow><mi mathvariant="bold-script">ℰ</mi></mrow><mrow><mi>′</mi></mrow></msup></mrow></math>$ , and $ϕ (Q)$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>ϕ</mi><mrow><mo class="MathClass-open">(</mo><mrow><mi>Q</mi></mrow><mo class="MathClass-close">)</mo></mrow></mrow></math>$ for $Q$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>Q</mi></mrow></math>$ in $E (F_{q})$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi mathvariant="bold-script">ℰ</mi><mrow><mo class="MathClass-open">(</mo><mrow><msub><mrow><mi mathvariant="double-struck">𝔽</mi></mrow><mrow><mi>q</mi></mrow></msub></mrow><mo class="MathClass-close">)</mo></mrow></mrow></math>$ , using only $˜ O (\sqrt{ℓ})$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mover accent="false"><mrow><mi>O</mi></mrow><mo class="MathClass-op">˜</mo></mover><mrow><mo class="MathClass-open">(</mo><mrow><msqrt><mrow><mi>ℓ</mi></mrow></msqrt></mrow><mo class="MathClass-close">)</mo></mrow></mrow></math>$ $F_{q}$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><msub><mrow><mi mathvariant="double-struck">𝔽</mi></mrow><mrow><mi>q</mi></mrow></msub></mrow></math>$ -operations, where the $˜ O$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mover accent="false"><mrow><mi>O</mi></mrow><mo class="MathClass-op">˜</mo></mover></mrow></math>$ is again uniform in $q$ $<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>q</mi></mrow></math>$ . As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.

Dedicated to the memory of Peter Lawrence Montgomery

Keywords

isogenies, resultants

Mathematical Subject Classification

Primary: 11Y16

Milestones

Received: 28 February 2020

Revised: 28 February 2020

Accepted: 29 April 2020

Published: 29 December 2020

Authors

Daniel J. Bernstein
Department of Computer Science University of Illinois at Chicago USA	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 Institut Polytechnique de Paris Palaiseau France

Benjamin Smith
Inria and École Polytechnique Institut Polytechnique de Paris Palaiseau France

Vol. 4, 2020

Daniel J. Bernstein, Luca De Feo, Antonin Leroux and Benjamin Smith

Abstract

Keywords

Mathematical Subject Classification

Milestones

Authors