Paper Info
Title
Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick
Abstract
Our development of efficient methods for the precomputation of multi-scalar multiplication for elliptic curve cryptosystems (ECCs) is presented. Multi-scalar multiplication is required in many forms of ECC, including schemes for the verification of ECDSA signatures. The simultaneous method is one known method for fast multi-scalar multiplication. The method has two stages: a precomputation stage and an evaluation stage. Points for use in the evaluation stage are computed in the precomputation stage. The actual multiscalar multiplication is carried out on the basis of the precomputed points in the evaluation stage. In the evaluation stage of the simultaneous method, we are able to quickly compute the points of the multiscalar multiple because few additions are required. On the other hand, if we use a large window width, we have to compute an enormous number of points in the precomputation stage. Hence, we have to compute an abundance of inversions, which carries a high computational cost. The result is that a large amount of time is required by the precomputation stage. This is the well-known draw-back of the simultaneous method. In our proposed method, we apply the Montgomery trick to reduce the number of inversions required with a width window w from O(22w) to O(w). In addition, our proposed method computes uP and vQ for any u, v, then compute uP + vQ, where P,Q are elliptic points. This procedure enables us to remove points that will not be used later from the process of precomputation. Without our proposed method, an algorithm to compute precomputation table would have to be changed dependently on unused points. Compared with the method without Montgomery trick, our proposed method is 3.6 times faster than the conventional simultaneous method, i.e., than in the absence of the Montgomery trick. Moreover, the optimal window width for our proposed method is 3, whereas the corresponding width for conventional simultaneous methods is 2.
Year
Venue
Keywords
2002
Lecture Notes in Computer Science
montgomery trick,proposed method compute,precomputation stage,fast multi-scalar multiplication methods,conventional simultaneous method,evaluation stage,efficient method,precomputation strategy,multi-scalar multiplication,elliptic curves,precomputation table,simultaneous method,elliptic curve,cryptography,theoretical computer science,digital signature,scalar multiplication,elliptic curve cryptography
Field
DocType
Volume
Elliptic Curve Digital Signature Algorithm,Scalar multiplication,Precomputation,Computer science,Cryptography,Algorithm,Arithmetic,Digital signature,Theoretical computer science,Multiplication,Elliptic curve cryptography,Elliptic curve
Conference
2523
ISSN
ISBN
Citations 
0302-9743
3-540-00409-2
7
PageRank 
References 
Authors
0.58
13
2
Name
Order
Citations
PageRank
Katsuyuki Okeya144738.47
Kouichi Sakurai21514213.71