Optimizing double-base elliptic-curve single-scalar multiplication

D.J. Bernstein, P. Birkner, T. Lange, C.P. Peters

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

22 Citaties (Scopus)

Uittreksel

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.
TaalEngels
TitelProceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India
RedacteurenK. Srinathan, C. Pandu Rangan, M. Yung
Plaats van productieBerlin, Germany
UitgeverijSpringer
Pagina's167-182
ISBN van geprinte versie978-3-540-77025-1
DOI's
StatusGepubliceerd - 2007
Evenementconference; INDOCRYPT 2007, Chennai, India; 2007-12-09; 2007-12-13 -
Duur: 9 dec 200713 dec 2007

Publicatie series

NaamLecture Notes in Computer Science
Volume4859
ISSN van geprinte versie0302-9743

Congres

Congresconference; INDOCRYPT 2007, Chennai, India; 2007-12-09; 2007-12-13
Periode9/12/0713/12/07
AnderINDOCRYPT 2007, Chennai, India

Vingerafdruk

Scalar multiplication
Elliptic Curves
Curve
Doubling
Jacobi
Standard Basis
Quartic
Extremes
Intersection
Trade-offs
Range of data

Citeer dit

Bernstein, D. J., Birkner, P., Lange, T., & Peters, C. P. (2007). Optimizing double-base elliptic-curve single-scalar multiplication. In K. Srinathan, C. Pandu Rangan, & M. Yung (editors), Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India (blz. 167-182). (Lecture Notes in Computer Science; Vol. 4859). Berlin, Germany: Springer. DOI: 10.1007/978-3-540-77026-8_13
Bernstein, D.J. ; Birkner, P. ; Lange, T. ; Peters, C.P./ Optimizing double-base elliptic-curve single-scalar multiplication. Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India. redacteur / K. Srinathan ; C. Pandu Rangan ; M. Yung. Berlin, Germany : Springer, 2007. blz. 167-182 (Lecture Notes in Computer Science).
@inproceedings{6b88e140eed7442f8151accae93e37e4,
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.",
author = "D.J. Bernstein and P. Birkner and T. Lange and C.P. Peters",
year = "2007",
doi = "10.1007/978-3-540-77026-8_13",
language = "English",
isbn = "978-3-540-77025-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "167--182",
editor = "K. Srinathan and {Pandu Rangan}, C. and M. Yung",
booktitle = "Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India",
address = "Germany",

}

Bernstein, DJ, Birkner, P, Lange, T & Peters, CP 2007, Optimizing double-base elliptic-curve single-scalar multiplication. in K Srinathan, C Pandu Rangan & M Yung (redactie), Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India. Lecture Notes in Computer Science, vol. 4859, Springer, Berlin, Germany, blz. 167-182, 9/12/07. DOI: 10.1007/978-3-540-77026-8_13

Optimizing double-base elliptic-curve single-scalar multiplication. / Bernstein, D.J.; Birkner, P.; Lange, T.; Peters, C.P.

Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India. redactie / K. Srinathan; C. Pandu Rangan; M. Yung. Berlin, Germany : Springer, 2007. blz. 167-182 (Lecture Notes in Computer Science; Vol. 4859).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

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

PB - Springer

CY - Berlin, Germany

ER -

Bernstein DJ, Birkner P, Lange T, Peters CP. Optimizing double-base elliptic-curve single-scalar multiplication. In Srinathan K, Pandu Rangan C, Yung M, redacteurs, Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (INDOCRYPT 2007) 9-13 December 2007, Chennai, India. Berlin, Germany: Springer. 2007. blz. 167-182. (Lecture Notes in Computer Science). Beschikbaar vanaf, DOI: 10.1007/978-3-540-77026-8_13