Cryptology ePrint Archive: Report 2017/037

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:

[ Cryptology ePrint archive ]