Published in

Springer Verlag, Lecture Notes in Computer Science, p. 327-343

DOI: 10.1007/978-3-642-25516-8_20

Links

Tools

Export citation

Search in Google Scholar

Improved Precomputation Scheme for Scalar Multiplication on Elliptic Curves

Proceedings article published in 2011 by Duc-Phong Le, Chik How Tan
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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 , …, [2 k −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.