Optimizing double-base elliptic-curve single-scalar multiplication

Daniel J. Bernstein; Peter Birkner; Tanja Lange; Christiane Peters

doi:10.1007/978-3-540-77026-8_13

Optimizing double-base elliptic-curve single-scalar multiplication

Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S -M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader.
Keyword: edwards curves,scalar multiplication,Algorithms,double-base chains,addition chains,Computation theory,Double-base number systems,quintupling,T,tripling,COMPUTER,double-base number systems,Problem solving,Optimization

Original language	English
Title of host publication	PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007
Volume	Volume 4859
Publisher	Springer Verlag, Berlin
Publication date	2007
Pages	167-182
ISBN (Print)	978-35-40-77025-1
DOIs	https://doi.org/10.1007/978-3-540-77026-8_13
Publication status	Published - 2007
Externally published	Yes
Event	8th International Conference on Cryptology in India: Progress in Cryptology - Chennai, India Duration: 9 Dec 2007 → 13 Dec 2007 Conference number: 8 http://www.informatik.uni-trier.de/~ley/db/conf/indocrypt/indocrypt2007.html

Conference

Conference	8th International Conference on Cryptology in India
Number	8
Country	India
City	Chennai
Period	09/12/2007 → 13/12/2007
Internet address	http://www.informatik.uni-trier.de/~ley/db/conf/indocrypt/indocrypt2007.html

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	Volume 4859

Access to Document

10.1007/978-3-540-77026-8_13

Cite this

Bernstein, D. J., Birkner, P., Lange, T., & Peters, C. (2007). Optimizing double-base elliptic-curve single-scalar multiplication. In PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007 (Vol. Volume 4859, pp. 167-182). Springer Verlag, Berlin. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), No. Volume 4859 https://doi.org/10.1007/978-3-540-77026-8_13

Bernstein, Daniel J. ; Birkner, Peter ; Lange, Tanja ; Peters, Christiane. / Optimizing double-base elliptic-curve single-scalar multiplication. PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007. Vol. Volume 4859 Springer Verlag, Berlin, 2007. pp. 167-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); No. Volume 4859).

@inproceedings{8c9386fae2e742f4931db6816b2b1232,

title = "Optimizing double-base elliptic-curve single-scalar multiplication",

abstract = "This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S -M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader. Keyword: edwards curves,scalar multiplication,Algorithms,double-base chains,addition chains,Computation theory,Double-base number systems,quintupling,T,tripling,COMPUTER,double-base number systems,Problem solving,Optimization",

author = "Bernstein, {Daniel J.} and Peter Birkner and Tanja Lange and Christiane Peters",

year = "2007",

doi = "10.1007/978-3-540-77026-8_13",

language = "English",

isbn = "978-35-40-77025-1",

volume = "Volume 4859",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag, Berlin",

number = "Volume 4859",

pages = "167--182",

booktitle = "PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007",

note = "8th International Conference on Cryptology in India : Progress in Cryptology , INDOCRYPT 2007 ; Conference date: 09-12-2007 Through 13-12-2007",

url = "http://www.informatik.uni-trier.de/~ley/db/conf/indocrypt/indocrypt2007.html",

}

Bernstein, DJ, Birkner, P, Lange, T & Peters, C 2007, Optimizing double-base elliptic-curve single-scalar multiplication. in PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007. vol. Volume 4859, Springer Verlag, Berlin, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. Volume 4859, pp. 167-182, 8th International Conference on Cryptology in India, Chennai, India, 09/12/2007. https://doi.org/10.1007/978-3-540-77026-8_13

Optimizing double-base elliptic-curve single-scalar multiplication. / Bernstein, Daniel J.; Birkner, Peter; Lange, Tanja; Peters, Christiane.

PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007. Vol. Volume 4859 Springer Verlag, Berlin, 2007. p. 167-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); No. Volume 4859).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Optimizing double-base elliptic-curve single-scalar multiplication

AU - Bernstein, Daniel J.

AU - Birkner, Peter

AU - Lange, Tanja

AU - Peters, Christiane

N1 - Conference code: 8

PY - 2007

Y1 - 2007

N2 - This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S -M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader. Keyword: edwards curves,scalar multiplication,Algorithms,double-base chains,addition chains,Computation theory,Double-base number systems,quintupling,T,tripling,COMPUTER,double-base number systems,Problem solving,Optimization

AB - This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S -M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader. Keyword: edwards curves,scalar multiplication,Algorithms,double-base chains,addition chains,Computation theory,Double-base number systems,quintupling,T,tripling,COMPUTER,double-base number systems,Problem solving,Optimization

U2 - 10.1007/978-3-540-77026-8_13

DO - 10.1007/978-3-540-77026-8_13

M3 - Article in proceedings

SN - 978-35-40-77025-1

VL - Volume 4859

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 167

EP - 182

BT - PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007

PB - Springer Verlag, Berlin

T2 - 8th International Conference on Cryptology in India

Y2 - 9 December 2007 through 13 December 2007

ER -

Bernstein DJ, Birkner P, Lange T, Peters C. Optimizing double-base elliptic-curve single-scalar multiplication. In PROGRESS IN CRYPTOLOGY - INDOCRYPT 2007. Vol. Volume 4859. Springer Verlag, Berlin. 2007. p. 167-182. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); No. Volume 4859). https://doi.org/10.1007/978-3-540-77026-8_13