Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms

In most algorithms involving elliptic curves, the most expensive part consists in computing multiples of points. This paper investigates how to extend the t-adic expansion from Koblitz curves to a larger class of curves defined over a prime field having an efficiently-computable endomorphism f 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 k 0 P + k 1 Q. Following the work of Solinas on the Joint Sparse Form, we introduce the notion of f-Joint Sparse Form which combines the advantages of a f-expansion with the additional speedup of the Joint Sparse Form. We also present an efficient algorithm to obtain the f-Joint Sparse Form. Then, the double exponentiation can be done using the f endomorphism instead of doubling, resulting in an average of l applications of f and l/2 additions, where l is the size of the ki’s. This results in an important speed-up when the computation of f is particularly effective, as in the case of Koblitz curves. The work described in this paper has been supported [in part] by the Commission of the European Communities through the IST Programme under Contract IST-1999-12324, http://www.cryptonessie.org/. The information in this document is provided as is, and no guarantee or warranty is given or implied that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability. The views expressed are those of the authors and do not represent an official view/position of the NESSIE project (as a whole).