Paper 2017/037

Double-base scalar multiplication revisited

Daniel J. Bernstein, Chitchanok Chuengsatiansup, and Tanja Lange

Abstract

This paper reduces the number of field multiplications required for scalar multiplication on conservative elliptic curves. For an average 256-bit integer n, this paper's multiply-by-n algorithm takes just 7.47M per bit on twisted Edwards curves -x^2+y^2=1+dx^2y^2 with small d. The previous record, 7.62M per bit, was unbeaten for seven years. Unlike previous record-setting algorithms, this paper's multiply-by-n algorithm uses double-base chains. The new speeds rely on advances in tripling speeds and on advances in constructing double-base chains. This paper's new tripling formula for twisted Edwards curves takes just 11.4M, and its new algorithm for constructing an optimal double-base chain for n takes just (log n)^{2.5+o(1)} bit operations. Extending this double-base algorithm to double-scalar multiplications, as in signature verification, takes 8.80M per bit to compute n_1P+n_2Q. Previous techniques used 9.34M per bit.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
scalar multiplicationEdwards curvestriplingsdouble-base chainsdirected acyclic graphsdouble-scalar multiplicationsignatures
Contact author(s)
authorcontact-dagger @ box cr yp to
History
2017-01-15: received
Short URL
https://ia.cr/2017/037
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/037,
      author = {Daniel J.  Bernstein and Chitchanok Chuengsatiansup and Tanja Lange},
      title = {Double-base scalar multiplication revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2017/037},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/037}},
      url = {https://eprint.iacr.org/2017/037}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.