Efficient scalar multiplication by isogeny decompositions

Christophe Doche*, Thomas Icart, David R. Kohel

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

39 Citations (Scopus)

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-ℓ map [ℓ] has degree, therefore the complexity to directly evaluate [ℓ](P) is O(ℓ2). For a small prime ℓ (= 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 curve admits an isogeny φ of degree ℓ then the costs of computing φ(P) should in contrast be O(ℓ) field operations. Since we then have a product expression [ℓ] = φ̂φ, the existence of an ℓ-isogeny φ on an elliptic curve yields a theoretical improvement from O(ℓ2) to O(ℓ) field operations for the evaluation of [ℓ](P) by naïve application of the defining polynomials. In this work we investigate actual improvements for small ℓ of this asymptotic complexity. For this purpose, we describe the general construction of families of curves with a suitable decomposition [ℓ] = φ̂φ, 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 ℓ-adic expansions in order to obtain an improved strategy for scalar multiplication on elliptic curves.

Original languageEnglish
Title of host publicationPublic Key Cryptography - PKC 2006 - 9th International Conference on Theory and Practice in Public-Key Cryptography, Proceedings
EditorsMoti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages191-206
Number of pages16
Volume3958 LNCS
ISBN (Print)3540338519, 9783540338512
DOIs
Publication statusPublished - 2006
Event9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006 - New York, NY, United States
Duration: 24 Apr 200626 Apr 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3958 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other9th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2006
CountryUnited States
CityNew York, NY
Period24/04/0626/04/06

Fingerprint Dive into the research topics of 'Efficient scalar multiplication by isogeny decompositions'. Together they form a unique fingerprint.

Cite this