TY - GEN

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

AU - Bernstein, D.J.

AU - Birkner, P.

AU - Lange, T.

AU - Peters, C.P.

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.

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.

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

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

M3 - Conference contribution

SN - 978-3-540-77025-1

T3 - Lecture Notes in Computer Science

SP - 167

EP - 182

BT - Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India

A2 - Srinathan, K.

A2 - Pandu Rangan, C.

A2 - Yung, M.

PB - Springer

CY - Berlin, Germany

T2 - conference; INDOCRYPT 2007, Chennai, India; 2007-12-09; 2007-12-13

Y2 - 9 December 2007 through 13 December 2007

ER -