CryptoDB
Efficient Scalar Multiplication by Isogeny Decompositions
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2005-12753,
title={Efficient Scalar Multiplication by Isogeny Decompositions},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / elliptic curve cryptosystem},
url={http://eprint.iacr.org/2005/420},
note={ doche@ics.mq.edu.au 13110 received 21 Nov 2005, last revised 22 Nov 2005},
author={Christophe Doche and Thomas Icart and David Kohel},
year=2005
}