Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms

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

Research output: Contribution to journalArticle

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
Pages (from-to)388-400
Number of pages13
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2656
Publication statusPublished - 2003
Externally publishedYes

Fingerprint

Endomorphisms
Elliptic Curves
Joints
Endomorphism
Curve
Cryptography
Speedup
Elliptic Curve Cryptosystem
Efficient Points
Exponentiation
Doubling
Multiplication
Efficient Algorithms
Form
Computing

Keywords

  • Elliptic curves
  • Fast endomorphisms
  • Joint Sparse Form

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

Cite this

@article{1de7d781cd214ebd9e577ae30dab5a5d,
title = "Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms",
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.",
keywords = "Elliptic curves, Fast endomorphisms, Joint Sparse Form",
author = "Mathieu Ciet and Tanja Lange and Francesco Sica and Quisquater, {Jean Jacques}",
year = "2003",
language = "English",
volume = "2656",
pages = "388--400",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms

AU - Ciet, Mathieu

AU - Lange, Tanja

AU - Sica, Francesco

AU - Quisquater, Jean Jacques

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - Elliptic curves

KW - Fast endomorphisms

KW - Joint Sparse Form

UR - http://www.scopus.com/inward/record.url?scp=35248868300&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248868300&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:35248868300

VL - 2656

SP - 388

EP - 400

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -