Revisiting the Expansion Length of Triple-base Number System for Elliptic Curve Scalar Multiplication

摘要

Because of its sparsity, triple-base number system is used to accelerate the scalar multiplication in elliptic curve cryptography. Yu et al. presented an estimate for the length of triple-base number system at Africacrypt 2013. However, the efficiency of scalar multiplication is not only associated with the length of representation but also the numbers and costs of doubling, tripling, quintupling and addition. It is necessary to set a restriction for exponents of base 2, 3 and 5, which will lead to longer expansion length. In this situation, we prove a stronger result: the upper bound on expansion length of constrained triple-base number system is still sub-linear. This result provides more practical boundary of the triple-base number system to speed up the scalar multiplication. At the same time, it also generalizes the result of Meloni et al. about double-base number system.