CryptoDB
Double-Base Chains for Scalar Multiplications on Elliptic Curves
| Authors: |
- Wei Yu , Institute of Information Engineering, Chinese Academy of Sciences, China
- Saud Al Musa , College of Computer Science and Engineering, Taibah University, Medina, Saudi Arabia
- Bao Li , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China, and School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
|
| Download: |
- DOI: 10.1007/978-3-030-45727-3_18
(login may be required)
- Search ePrint
- Search Google
|
| Presentation: |
Slides
|
|
Conference:
|
EUROCRYPT 2020
|
| Abstract: |
Double-base 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 state-of-the-art Bernstein, Chuengsatiansup, and Lange's work. The Hamming weights of optimal DBCs are over $60$\% smaller than those of NAFs. Experimental results show that scalar multiplication using our optimal DBC is about $13$\% faster than that using non-adjacent form on elliptic curves over large prime fields. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30177,
title={Double-Base Chains for Scalar Multiplications on Elliptic Curves},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={Elliptic curve cryptography;Scalar multiplication;Double-base chain;Hamming weight},
volume={12105},
doi={10.1007/978-3-030-45727-3_18},
author={Wei Yu and Saud Al Musa and Bao Li},
year=2020
}
