International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Efficient Scalar Multiplication by Isogeny Decompositions

Christophe Doche
Thomas Icart
David Kohel
Search ePrint
Search Google
Abstract: On an elliptic curve, the degree of an isogeny corresponds essentially to the degrees of the polynomial expressions involved in its application. The multiplication--by--$\ell$ map $[\ell]$ has degree~$\ell^2$, therefore the complexity to directly evaluate $[\ell](P)$ is $O(\ell^2)$. For a small prime $\ell\, (= 2, 3)$ such that the additive binary representation provides no better performance, this represents the true cost of application of scalar multiplication. If an elliptic curves admits an isogeny $\varphi$ of degree $\ell$ then the costs of computing $\varphi(P)$ should in contrast be $O(\ell)$ field operations. Since we then have a product expression $[\ell] = \hat{\varphi}\varphi$, the existence of an $\ell$-isogeny $\varphi$ on an elliptic curve yields a theoretical improvement from $O(\ell^2)$ to $O(\ell)$ field operations for the evaluation of $[\ell](P)$ by na\"ive application of the defining polynomials. In this work we investigate actual improvements for small $\ell$ of this asymptotic complexity. For this purpose, we describe the general construction of families of curves with a suitable decomposition $[\ell] = \hat{\varphi}\varphi$, and provide explicit examples of such a family of curves with simple decomposition for~$[3]$. Finally we derive a new tripling algorithm to find complexity improvements to triplication on a curve in certain projective coordinate systems, then combine this new operation to non-adjacent forms for $\ell$-adic expansions in order to obtain an improved strategy for scalar multiplication on elliptic curves.
  title={Efficient Scalar Multiplication by Isogeny Decompositions},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / elliptic curve cryptosystem},
  note={ 13110 received 21 Nov 2005, last revised 22 Nov 2005},
  author={Christophe Doche and Thomas Icart and David Kohel},