CryptoDB
Optimizing double-base elliptic-curve single-scalar multiplication
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2007-13694, title={Optimizing double-base elliptic-curve single-scalar multiplication}, booktitle={IACR Eprint archive}, keywords={public-key cryptography / Edwards curves, double-base number systems, double-base chains, addition chains, scalar multiplication, tripling, quintupling}, url={http://eprint.iacr.org/2007/414}, note={ tanja@hyperelliptic.org 13814 received 28 Oct 2007, last revised 28 Oct 2007}, author={Daniel J. Bernstein and Peter Birkner and Tanja Lange and Christiane Peters}, year=2007 }