JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]


Journal of Information Science and Engineering, Vol. 34 No. 3, pp. 721-732


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

YUN-QI DOU1,2, JIANG WENG3, CHUAN-GUI MA4 AND FU-SHAN WEI1,2
1State Key Laboratory of Mathematical Engineering and Advanced Computing
Zhengzhou, 450001 P.R. China
2State Key Laboratory of Cryptology
Beijing, 100878 P.R. China
3Information and Navigation College
Air Force Engineering University
Xi'an, 710077 P.R. China
4Department of Basic
Army Aviation Institution
Beijing, 101123 P.R. China
E-mail: douyunqi@126.com

  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 Méloni et al. about double-base number system.

Keywords: elliptic curve cryptography, scalar multiplication, constrained triple-base number system, greedy algorithm, sub-linear

  Retrieve PDF document (JISE_201803_09.pdf)