Double-base scalar multiplication revisited

Daniel J.  Bernstein; Chitchanok Chuengsatiansup; Tanja Lange

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 multiplication Edwards curves triplings double-base chains directed acyclic graphs double-scalar multiplication signatures
Contact author(s): authorcontact-dagger @ box cr yp to
History: 2017-01-15: received
Short URL: https://ia.cr/2017/037
License: 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},
      url = {https://eprint.iacr.org/2017/037}
}