2007 | OriginalPaper | Chapter
Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication
Authors : Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters
Published in: Progress in Cryptology – INDOCRYPT 2007
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.