**Double-base scalar multiplication revisited**

*Daniel J. Bernstein and 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.

**Category / Keywords: **scalar multiplication, Edwards curves, triplings, double-base chains, directed acyclic graphs, double-scalar multiplication, signatures

**Date: **received 15 Jan 2017, last revised 15 Jan 2017

**Contact author: **authorcontact-dagger at box cr yp to

**Available format(s): **PDF | BibTeX Citation

**Version: **20170115:213144 (All versions of this report)

**Short URL: **ia.cr/2017/037

[ Cryptology ePrint archive ]