Optimizing double-base elliptic-curve single-scalar multiplication

D.J. Bernstein, P. Birkner, T. Lange, C.P. Peters

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

27 Citations (Scopus)
282 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationProceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India
EditorsK. Srinathan, C. Pandu Rangan, M. Yung
Place of PublicationBerlin, Germany
ISBN (Print)978-3-540-77025-1
Publication statusPublished - 2007
Eventconference; INDOCRYPT 2007, Chennai, India; 2007-12-09; 2007-12-13 -
Duration: 9 Dec 200713 Dec 2007

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conferenceconference; INDOCRYPT 2007, Chennai, India; 2007-12-09; 2007-12-13
OtherINDOCRYPT 2007, Chennai, India


Dive into the research topics of 'Optimizing double-base elliptic-curve single-scalar multiplication'. Together they form a unique fingerprint.

Cite this