Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms

Mathieu Ciet, Tanja Lange, Francesco Sica, Jean Jacques Quisquater

Research output: Chapter in Book/Report/Conference proceedingChapter

22 Citations (Scopus)

Abstract

In most algorithms involving elliptic curves, the most expensive part consists in computing multiples of points. This paper investigates how to extend the τ-adic expansion from Koblitz curves to a larger class of curves defined over a prime field having an efficiently-computable endomorphism φ in order to perform an efficient point multiplication with efficiency similar to Solinas' approach presented at CRYPTO '97. Furthermore, many elliptic curve cryptosystems require the computation of k0P + k1Q. Following the work of Solinas on the Joint Sparse Form, we introduce the notion of φ-Joint Sparse Form which combines the advantages of a φ-expansion with the additional speedup of the Joint Sparse Form. We also present an efficient algorithm to obtain the φ-Joint Sparse Form. Then, the double exponentiation can be done using the φ endomorphism instead of doubling, resulting in an average of l applications of φ and l/2 additions, where l is the size of the ki's. This results in an important speed-up when the computation of φ is particularly effective, as in the case of Koblitz curves.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsEli Biham
PublisherSpringer Verlag
Pages388-400
Number of pages13
ISBN (Print)3540140395, 9783540140399
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2656
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Elliptic curves
  • Fast endomorphisms
  • Joint Sparse Form

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms'. Together they form a unique fingerprint.

  • Cite this

    Ciet, M., Lange, T., Sica, F., & Quisquater, J. J. (2003). Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms. In E. Biham (Ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 388-400). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2656). Springer Verlag. https://doi.org/10.1007/3-540-39200-9_24