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 }