Conference paper
Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication
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.
Language: | English |
---|---|
Publisher: | Springer Berlin Heidelberg |
Year: | 2007 |
Pages: | 167-182 |
Proceedings: | International Conference on Cryptology in India |
ISBN: | 3540770259 , 3540770267 , 9783540770251 and 9783540770268 |
Types: | Conference paper |
DOI: | 10.1007/978-3-540-77026-8_13 |