Paper Info
Title
Improved precomputation scheme for scalar multiplication on elliptic curves
Abstract
Precomputation is essential for window-based scalar multiplications which are the most important operation of elliptic curve cryptography. This precomputation stage may require a significant amount of time due to the expensive inversions over finite fields of large characteristic. Hence, the existing state-of-the-art precomputation schemes try to reduce the number of inversions as much as possible. However, our analysis show that the performance of precomputation schemes not only depends on the cost of field inversions, but also on the cost ratio of inversion to multiplication (i.e. I/M). In this paper, we present a new scheme to precompute all odd multiples [3]P , …, [2k −1]P , k ≥2 on standard elliptic curves in affine coordinates. Our precomputation scheme strikes a balance between the number of inversions and multiplications. We show that our scheme requiring only 2(k −1) registers, offers the best performance in the case of k ≥8 if the I/M-ratio is around 10.
Year
DOI
Venue
2011
10.1007/978-3-642-25516-8_20
IMA Int. Conf.
Keywords
Field
DocType
expensive inversion,precomputation stage,existing state-of-the-art precomputation scheme,scalar multiplication,precomputation scheme,standard elliptic curve,improved precomputation scheme,cost ratio,new scheme,best performance,elliptic curve cryptography,analysis show
Affine transformation,Finite field,Scalar multiplication,Precomputation,Algorithm,Arithmetic,Multiplication,Elliptic curve point multiplication,Elliptic curve cryptography,Mathematics,Elliptic curve
Conference
Citations 
PageRank 
References 
0
0.34
14
Authors
2
Name
Order
Citations
PageRank
Duc-Phong Le1297.06
Chik How Tan249954.60