Optimizing double-base elliptic-curve single-scalar multiplication

Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S -M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader.
Keyword: edwards curves,scalar multiplication,Algorithms,double-base chains,addition chains,Computation theory,Double-base number systems,quintupling,T,tripling,COMPUTER,double-base number systems,Problem solving,Optimization
Original languageEnglish
Title of host publicationPROGRESS IN CRYPTOLOGY - INDOCRYPT 2007
VolumeVolume 4859
PublisherSpringer Verlag, Berlin
Publication date2007
Pages167-182
ISBN (Print)978-35-40-77025-1
DOIs
Publication statusPublished - 2007
Externally publishedYes
Event8th International Conference on Cryptology in India: Progress in Cryptology - Chennai, India
Duration: 9 Dec 200713 Dec 2007
Conference number: 8
http://www.informatik.uni-trier.de/~ley/db/conf/indocrypt/indocrypt2007.html

Conference

Conference8th International Conference on Cryptology in India
Number8
CountryIndia
CityChennai
Period09/12/200713/12/2007
Internet address
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberVolume 4859

Cite this

Bernstein, D. J., Birkner, P., Lange, T., & Peters, C. (2007). Optimizing double-base elliptic-curve single-scalar multiplication. In PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007 (Vol. Volume 4859, pp. 167-182). Springer Verlag, Berlin. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), No. Volume 4859 https://doi.org/10.1007/978-3-540-77026-8_13