OPTIMAL ELLIPTIC CURVE SCALAR MULTIPLICATION USING DOUBLE-BASE CHAINS

In this work, we propose an algorithm to produce the double-base chain that optimizes the time used for computing an elliptic curve scalar multiplication, i.e. the bottleneck operation of the elliptic curve cryptosystem. The double-base number system and its subclass, double-base chain, are the representation that combines the binary and ternary representations. The time is measured as the weighted sum in terms of the point double, triple, and addition, as used in evaluating the performance of existing greedy-type algorithms, and our algorithm is the first to attain the minimum time by means of dynamic programming. Compared with greedy-type algorithm, the experiments show that our algorithm reduces the time for computing the scalar multiplication by 3.88-3.95% with almost the same average running time for the method itself. We also extend our idea, and propose an algorithm to optimize multi-scalar multiplication. By that extension, we can improve a computation time of the operation by 3.2-11.3%.