New and Improved Methods to Analyze and Compute Double-Scalar Multiplications

摘要

We address several algorithms to perform a double-scalar multiplication on an elliptic curve. All the methods investigated are related to the double-base number system (DBNS) and extend previous work of Doche et al. . We refine and rigorously prove the complexity analysis of the joint binary-ternary (JBT) algorithm. Experiments are in line with the theory and show that the JBT requires approximately 6 percent less field multiplications than the standard joint sparse form (JSF) method to compute $([{schmi{n}}]{schmi{P}} + [{schmi{m}}]{schmi{Q}})$. We also introduce a randomized version of the JBT, called JBT-Rand, that gives total control of the number of triplings in the expansion that is produced. So it becomes possible with the JBT-Rand to adapt and tune the number of triplings to the coordinate system and bit length that are used, to further decrease the cost of a double-scalar multiplication. Then, we focus on Koblitz curves. For extension degrees enjoying an optimal normal basis of type II, we discuss a Joint $({schmi{tau}})$-DBNS approach that reduces the number of field multiplications by at least 35 percent over the traditional $({schmi{tau}})$-JSF. For other extension degrees represented in polynomial basis, the Joint $({schmi{tau}})$-DBNS is still relevant provided that appropriate bases conversion methods are used. In this situation, tests show that the speedup over the $({schmi{tau}})$-JSF is then larger than 20 percent. Finally, when the use of the $({schmi{tau}})$-DBNS becomes unrealistic, for instance because of the lack of an efficient normal basis or the lack of memory to allow an efficient conversion, we adapt the joint binary-ternary algorithm to Koblitz curves giving rise to the Joint $({schmi{tau}})$-$(bar{{schmi{tau}} })$ method whose complexity is analyzed and proved. The Joint $({schmi{tau}})$-$(bar{{schmi{tau}} })$ induces a speedup of about 10 percent over the $({schmi{tau}})$-JSF.