Fastest multi-scalar multiplication based on optimal double-base chains

We propose an algorithm to produce the optimal double-base chains (DBC) that minimize the time used for computing a multi-scalar multiplication, one of bottleneck operations of elliptic curve cryptosystem. The double-base chains are representations that combine binary and ternary representations. Since there are many possible sequences for a specific multi-scalar multiplication, we need to find an optimal sequence with smallest weighted sum of costs for elementary operations. Our algorithm is the first to attain the the fastest sequence with the same time complexity, O(lg ² r), as existing greedy-type algorithms, by means of dynamic programming. Also, experimental results show that our algorithm reduces the time for computing multi-scalar multiplications by 3.2-11.3% in less than a second for 192 to 448 bit inputs with Java implementation on a personal computer.