International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Affine Precomputation with Sole Inversion in Elliptic Curve Cryptography

Authors:
Erik Dahmen
Katsuyuki Okeya
Daniel Schepers
Download:
URL: http://eprint.iacr.org/2007/268
Search ePrint
Search Google
Abstract: This paper presents a new approach to precompute all odd points $[3]P, [5]P,\ldots, [2k-1]P$, $k \geq 2$ on an elliptic curve over $\mathbb{F}_p$. Those points are required for the efficient evaluation of a scalar multiplication, the most important operation in elliptic curve cryptography. The proposed method precomputes the points in affine coordinates and needs only one single field inversion for the computation. The new method is superior to all known methods that also use one field inversion. Compared to methods that require several field inversions for the precomputation, the proposed method is faster for a broad range of ratios of field inversions and field multiplications. The proposed method benefits especially from ratios as they occur on smart cards. %Scalar multiplications are the basic operations in elliptic curve cryptosystems. The evaluation of a scalar multiplication can be sped up by using signed representations of the scalar. In exchange for the speed up, the precomputation of a series of points is required. While a lot of research has been done in the direction of signed representations, little attention has been paid to efficient methods to precompute the required points. Such methods are important since costly field inversions are involved in the precomputation. This paper presents a new method for the precomputation that requires only one single field inversion, independent of the number of points to precompute. The points to precompute are all odd points $[3]P, [5]P,\ldots, [2k-1]P$, $k \geq 2$ on an elliptic curve over $\mathbb{F}_p$. The proposed method benefits especially from a large ratios between inversions and multiplications as they occur on smart cards.
BibTeX
@misc{eprint-2007-13549,
  title={Affine Precomputation with Sole Inversion in Elliptic Curve Cryptography},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / affine coordinates, elliptic curve cryptosystem, precomputation, scalar multiplication},
  url={http://eprint.iacr.org/2007/268},
  note={ACISP'07, LNCS 4586, Springer, 2007, pp. 245-258. dahmen@cdc.informatik.tu-darmstadt.de 13704 received 10 Jul 2007},
  author={Erik Dahmen and Katsuyuki Okeya and Daniel Schepers},
  year=2007
}