Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms
(2003) International Conference on Theory and Applications of Cryptographic Techniques (EUROCRYPT 2003) — Location: WARSAW(Poland) (4.May.2003)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 209.04 KB
Details
- Authors
- Abstract
- In most algorithms involving elliptic curves, the most expensive part consists in computing multiples of points. This paper investigates how to extend the tau-adic expansion from Koblitz curves to a larger class of curves defined over a prime field having an efficiently-computable endomorphism phi in order to perform an efficient point multiplication with efficiency similar to Solinas' approach presented at CRYPTO 197. Furthermore, many elliptic curve cryptosystems require the computation of k(0)P + k(1)Q. Following the work of Solinas on the Joint Sparse Form, we introduce the notion of phi-Joint Sparse Form which combines the advantages of a phi-expansion with the additional speedup of the Joint Sparse Form. We also present an efficient algorithm to obtain the phi-Joint Sparse Form. Then, the double exponentiation can be done using the phi endomorphism instead of doubling, resulting in an average of l applications of phi and l/2 additions, where l is the size of the k(i)'s. This results in an important speed-up when the computation of phi is particularly effective, as in the case of Koblitz curves.
- Affiliations
Citations
Ciet, M., Quisquater, J.-J., Lange, T., & Sica, F. (2003). Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms. Lecture Notes in Computer Science, 2656, 388-400. https://doi.org/10.1007/3-540-39200-9_24 (Original work published 2003)