Optimizing double-base elliptic-curve single-scalar multiplication

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

Paper 2007/414

Optimizing double-base elliptic-curve single-scalar multiplication

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

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Edwards curves double-base number systems double-base chains addition chains scalar multiplication tripling quintupling
Contact author(s): tanja @ hyperelliptic org
History: 2007-11-06: received
Short URL: https://ia.cr/2007/414
License: CC BY

BibTeX

@misc{cryptoeprint:2007/414,
      author = {Daniel J.  Bernstein and Peter Birkner and Tanja Lange and Christiane Peters},
      title = {Optimizing double-base elliptic-curve single-scalar multiplication},
      howpublished = {Cryptology ePrint Archive, Paper 2007/414},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/414}},
      url = {https://eprint.iacr.org/2007/414}
}