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 language | English |
|---|---|
| Pages (from-to) | 388-400 |
| Number of pages | 13 |
| Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Volume | 2656 |
| Publication status | Published - 2003 |
| Externally published | Yes |
Fingerprint
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
Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms. / Ciet, Mathieu; Lange, Tanja; Sica, Francesco; Quisquater, Jean Jacques.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 2656, 2003, p. 388-400.Research output: Contribution to journal › Article
}
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 -