Paper 2020/144
DoubleBase Chains for Scalar Multiplications on Elliptic Curves
Wei Yu, Saud Al Musa, and Bao Li
Abstract
Doublebase chains (DBCs) are widely used to speed up scalar multiplications on elliptic curves. We present three results of DBCs. First, we display a structure of the set containing all DBCs and propose an iterative algorithm to compute the number of DBCs for a positive integer. This is the first polynomial time algorithm to compute the number of DBCs for positive integers. Secondly, we present an asymptotic lower bound on average Hamming weights of DBCs $\frac{\log n}{8.25}$ for a positive integer $n$. This result answers an open question about the Hamming weights of DBCs. Thirdly, we propose a new algorithm to generate an optimal DBC for any positive integer. The time complexity of this algorithm is $\mathcal{O}\left(\left(\log n\right)^2 \log\log n\right)$ bit operations and the space complexity is $\mathcal{O}\left(\left(\log n\right)^{2}\right)$ bits of memory. This algorithm accelerates the recoding procedure by more than $6$ times compared to the stateoftheart Bernstein, Chuengsatiansup, and Lange's work. The Hamming weights of optimal DBCs are over $60$\% smaller than those of NAFs. Scalar multiplication using our optimal DBC is about $13$\% faster than that using nonadjacent form on elliptic curves over large prime fields.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2020
 Keywords
 Elliptic curve cryptographyScalar multiplicationDoublebase chainHamming weight
 Contact author(s)

yuwei_1_yw @ 163 com
yuwei @ iie ac cn  History
 20210219: last of 2 revisions
 20200210: received
 See all versions
 Short URL
 https://ia.cr/2020/144
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/144, author = {Wei Yu and Saud Al Musa and Bao Li}, title = {DoubleBase Chains for Scalar Multiplications on Elliptic Curves}, howpublished = {Cryptology ePrint Archive, Paper 2020/144}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/144}}, url = {https://eprint.iacr.org/2020/144} }