Paper 2007/268

Affine Precomputation with Sole Inversion in Elliptic Curve Cryptography

Erik Dahmen, Katsuyuki Okeya, and Daniel Schepers

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.