Double-base scalar multiplication revisited

Daniel J.  Bernstein; Chitchanok Chuengsatiansup; Tanja Lange

Paper 2017/037 Original: eprint.iacr.org/2017/037 ↗

Double-base scalar multiplication revisited

Daniel J. Bernstein

Chitchanok Chuengsatiansup

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.
History: 2017-01-15: last updated; 2017-01-15: published
Short URL: https://ia.cr/2017/037
License: https://creativecommons.org/licenses/by/4.0/

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}
}