Estimation of the Bounds for the Leading Term of a Double-Base Chain

Double-base chain (DBC) has been extensively studied for speeding up scalar multiplication, which significantly impacts the execution efficiency of ECC. In this paper, we estimate the theoretically optimal upper bound and lower bound for the leading term of a canonic DBC. Firstly, we develop a new method to estimate the bounds and prove its correctness, based on Yu et al.’s work in EUROCRYPT 2020. Secondly, we obtain the new bounds by applying this new method. Thirdly, we compare the efficiency improvements of canonic DBC generation algorithms and scalar multiplication algorithms using the new theoretically optimal upper bound. Compared to NAF algorithm, our new scalar multiplication algorithm achieves about \(13\%\) efficiency gains. Finally, we analyze the bounds for the leading term proposed by Eom et al., identify their limitations and provide counterexamples to demonstrate the issues.