Double-Base number system for multi-scalar multiplications

Christophe Doche, David R. Kohel, Francesco Sica

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Citations (Scopus)

Abstract

The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form [n]P + m[Q]. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously n and m. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can find a chain of reasonable length that uses exactly the same terms to compute both n and m. Furthermore, we discuss an algorithm to produce such a Joint Double- Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than 0.3945 log2 n. With respect to the Joint Sparse Form, this induces a reduction by more than 20% of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, P + Q and P - Q. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications. Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves. Our second contribution is a new way to evaluate f, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute ± f(P) with at most 2 multiplications and 2 squarings in the base field F 2. This represents a speed-up of about 50% with respect to the fastest known techniques. This has very concrete consequences on scalar and multi-scalar multiplications on Koblitz curves.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages502-517
Number of pages16
Volume5479 LNCS
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2009 - Cologne, Germany
Duration: Apr 26 2009Apr 30 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5479 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2009
CountryGermany
CityCologne
Period4/26/094/30/09

Fingerprint

Numbering systems
Scalar multiplication
Number system
Redundancy
Multiplication
Curve
Endomorphism
Term
Doubling
Frobenius
Simplicity
Speedup
Scalar
Evaluate
Form
Concepts
Generalization

Keywords

  • Double- Base Number System
  • Elliptic curve cryptography
  • Koblitz curves.
  • scalar multiplication

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Doche, C., Kohel, D. R., & Sica, F. (2009). Double-Base number system for multi-scalar multiplications. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 5479 LNCS, pp. 502-517). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5479 LNCS). https://doi.org/10.1007/978-3-642-01001-9_29

Double-Base number system for multi-scalar multiplications. / Doche, Christophe; Kohel, David R.; Sica, Francesco.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 5479 LNCS 2009. p. 502-517 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5479 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Doche, C, Kohel, DR & Sica, F 2009, Double-Base number system for multi-scalar multiplications. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 5479 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5479 LNCS, pp. 502-517, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2009, Cologne, Germany, 4/26/09. https://doi.org/10.1007/978-3-642-01001-9_29
Doche C, Kohel DR, Sica F. Double-Base number system for multi-scalar multiplications. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 5479 LNCS. 2009. p. 502-517. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-01001-9_29
Doche, Christophe ; Kohel, David R. ; Sica, Francesco. / Double-Base number system for multi-scalar multiplications. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 5479 LNCS 2009. pp. 502-517 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{aae630f612ed40a99f7671c304d85274,
title = "Double-Base number system for multi-scalar multiplications",
abstract = "The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form [n]P + m[Q]. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously n and m. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can find a chain of reasonable length that uses exactly the same terms to compute both n and m. Furthermore, we discuss an algorithm to produce such a Joint Double- Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than 0.3945 log2 n. With respect to the Joint Sparse Form, this induces a reduction by more than 20{\%} of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, P + Q and P - Q. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications. Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves. Our second contribution is a new way to evaluate f, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute ± f(P) with at most 2 multiplications and 2 squarings in the base field F 2. This represents a speed-up of about 50{\%} with respect to the fastest known techniques. This has very concrete consequences on scalar and multi-scalar multiplications on Koblitz curves.",
keywords = "Double- Base Number System, Elliptic curve cryptography, Koblitz curves., scalar multiplication",
author = "Christophe Doche and Kohel, {David R.} and Francesco Sica",
year = "2009",
doi = "10.1007/978-3-642-01001-9_29",
language = "English",
isbn = "3642010008",
volume = "5479 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "502--517",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - GEN

T1 - Double-Base number system for multi-scalar multiplications

AU - Doche, Christophe

AU - Kohel, David R.

AU - Sica, Francesco

PY - 2009

Y1 - 2009

N2 - The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form [n]P + m[Q]. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously n and m. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can find a chain of reasonable length that uses exactly the same terms to compute both n and m. Furthermore, we discuss an algorithm to produce such a Joint Double- Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than 0.3945 log2 n. With respect to the Joint Sparse Form, this induces a reduction by more than 20% of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, P + Q and P - Q. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications. Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves. Our second contribution is a new way to evaluate f, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute ± f(P) with at most 2 multiplications and 2 squarings in the base field F 2. This represents a speed-up of about 50% with respect to the fastest known techniques. This has very concrete consequences on scalar and multi-scalar multiplications on Koblitz curves.

AB - The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form [n]P + m[Q]. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously n and m. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can find a chain of reasonable length that uses exactly the same terms to compute both n and m. Furthermore, we discuss an algorithm to produce such a Joint Double- Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than 0.3945 log2 n. With respect to the Joint Sparse Form, this induces a reduction by more than 20% of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, P + Q and P - Q. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications. Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves. Our second contribution is a new way to evaluate f, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute ± f(P) with at most 2 multiplications and 2 squarings in the base field F 2. This represents a speed-up of about 50% with respect to the fastest known techniques. This has very concrete consequences on scalar and multi-scalar multiplications on Koblitz curves.

KW - Double- Base Number System

KW - Elliptic curve cryptography

KW - Koblitz curves.

KW - scalar multiplication

UR - http://www.scopus.com/inward/record.url?scp=67650697249&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67650697249&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-01001-9_29

DO - 10.1007/978-3-642-01001-9_29

M3 - Conference contribution

AN - SCOPUS:67650697249

SN - 3642010008

SN - 9783642010002

VL - 5479 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 502

EP - 517

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -