Extending scalar multiplication using double bases

Roberto Avanzi, Vassil Dimitrov, Christophe Doche, Francesco Sica

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

30 Citations (Scopus)

Abstract

It has been recently acknowledged [4,6,9] that the use of double bases representations of scalars n, that is an expression of the form n = ∑e,s,t (-1)e As Bt can speed up significantly scalar multiplication on those elliptic curves where multiplication by one base (say B) is fast. This is the case in particular of Koblitz curves and supersingular curves, where scalar multiplication can now be achieved in o(logn) curve additions. Previous literature dealt basically with supersingular curves (in characteristic 3, although the methods can be easily extended to arbitrary characteristic), where A,B ∈ ℕ. Only [4] attempted to provide a similar method for Koblitz curves, where at least one base must be non-real, although their method does not seem practical for cryptographic sizes (it is only asymptotic), since the constants involved are too large. We provide here a unifying theory by proposing an alternate recoding algorithm which works in all cases with optimal constants. Furthermore, it can also solve the until now untreatable case where both A and B are non-real. The resulting scalar multiplication method is then compared to standard methods for Koblitz curves. It runs in less than logn/loglogn elliptic curve additions, and is faster than any given method with similar storage requirements already on the curve K-163, with larger improvements as the size of the curve increases, surpassing 50% with respect to the τ-NAF for the curves K-409 and K-571. With respect of windowed methods, that can approach our speed but require O(log(n)/loglog(n)) precomputations for optimal parameters, we offer the advantage of a fixed, small memory footprint, as we need storage for at most two additional points.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages130-144
Number of pages15
Volume4284 LNCS
DOIs
Publication statusPublished - 2006
Externally publishedYes
Event12th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2006 - Shanghai, China
Duration: Dec 3 2006Dec 7 2006

Publication series

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

Other

Other12th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2006
CountryChina
CityShanghai
Period12/3/0612/7/06

Fingerprint

Scalar multiplication
Curve
Data storage equipment
Elliptic Curves
Optimal Constants
Optimal Parameter
Alternate
Multiplication
Speedup
Scalar

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Avanzi, R., Dimitrov, V., Doche, C., & Sica, F. (2006). Extending scalar multiplication using double bases. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 4284 LNCS, pp. 130-144). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4284 LNCS). https://doi.org/10.1007/11935230_9

Extending scalar multiplication using double bases. / Avanzi, Roberto; Dimitrov, Vassil; Doche, Christophe; Sica, Francesco.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 4284 LNCS 2006. p. 130-144 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4284 LNCS).

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

Avanzi, R, Dimitrov, V, Doche, C & Sica, F 2006, Extending scalar multiplication using double bases. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 4284 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4284 LNCS, pp. 130-144, 12th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2006, Shanghai, China, 12/3/06. https://doi.org/10.1007/11935230_9
Avanzi R, Dimitrov V, Doche C, Sica F. Extending scalar multiplication using double bases. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 4284 LNCS. 2006. p. 130-144. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11935230_9
Avanzi, Roberto ; Dimitrov, Vassil ; Doche, Christophe ; Sica, Francesco. / Extending scalar multiplication using double bases. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 4284 LNCS 2006. pp. 130-144 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{0a44369d13e64aeb92b424f2c56c499a,
title = "Extending scalar multiplication using double bases",
abstract = "It has been recently acknowledged [4,6,9] that the use of double bases representations of scalars n, that is an expression of the form n = ∑e,s,t (-1)e As Bt can speed up significantly scalar multiplication on those elliptic curves where multiplication by one base (say B) is fast. This is the case in particular of Koblitz curves and supersingular curves, where scalar multiplication can now be achieved in o(logn) curve additions. Previous literature dealt basically with supersingular curves (in characteristic 3, although the methods can be easily extended to arbitrary characteristic), where A,B ∈ ℕ. Only [4] attempted to provide a similar method for Koblitz curves, where at least one base must be non-real, although their method does not seem practical for cryptographic sizes (it is only asymptotic), since the constants involved are too large. We provide here a unifying theory by proposing an alternate recoding algorithm which works in all cases with optimal constants. Furthermore, it can also solve the until now untreatable case where both A and B are non-real. The resulting scalar multiplication method is then compared to standard methods for Koblitz curves. It runs in less than logn/loglogn elliptic curve additions, and is faster than any given method with similar storage requirements already on the curve K-163, with larger improvements as the size of the curve increases, surpassing 50{\%} with respect to the τ-NAF for the curves K-409 and K-571. With respect of windowed methods, that can approach our speed but require O(log(n)/loglog(n)) precomputations for optimal parameters, we offer the advantage of a fixed, small memory footprint, as we need storage for at most two additional points.",
author = "Roberto Avanzi and Vassil Dimitrov and Christophe Doche and Francesco Sica",
year = "2006",
doi = "10.1007/11935230_9",
language = "English",
isbn = "3540494758",
volume = "4284 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "130--144",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - GEN

T1 - Extending scalar multiplication using double bases

AU - Avanzi, Roberto

AU - Dimitrov, Vassil

AU - Doche, Christophe

AU - Sica, Francesco

PY - 2006

Y1 - 2006

N2 - It has been recently acknowledged [4,6,9] that the use of double bases representations of scalars n, that is an expression of the form n = ∑e,s,t (-1)e As Bt can speed up significantly scalar multiplication on those elliptic curves where multiplication by one base (say B) is fast. This is the case in particular of Koblitz curves and supersingular curves, where scalar multiplication can now be achieved in o(logn) curve additions. Previous literature dealt basically with supersingular curves (in characteristic 3, although the methods can be easily extended to arbitrary characteristic), where A,B ∈ ℕ. Only [4] attempted to provide a similar method for Koblitz curves, where at least one base must be non-real, although their method does not seem practical for cryptographic sizes (it is only asymptotic), since the constants involved are too large. We provide here a unifying theory by proposing an alternate recoding algorithm which works in all cases with optimal constants. Furthermore, it can also solve the until now untreatable case where both A and B are non-real. The resulting scalar multiplication method is then compared to standard methods for Koblitz curves. It runs in less than logn/loglogn elliptic curve additions, and is faster than any given method with similar storage requirements already on the curve K-163, with larger improvements as the size of the curve increases, surpassing 50% with respect to the τ-NAF for the curves K-409 and K-571. With respect of windowed methods, that can approach our speed but require O(log(n)/loglog(n)) precomputations for optimal parameters, we offer the advantage of a fixed, small memory footprint, as we need storage for at most two additional points.

AB - It has been recently acknowledged [4,6,9] that the use of double bases representations of scalars n, that is an expression of the form n = ∑e,s,t (-1)e As Bt can speed up significantly scalar multiplication on those elliptic curves where multiplication by one base (say B) is fast. This is the case in particular of Koblitz curves and supersingular curves, where scalar multiplication can now be achieved in o(logn) curve additions. Previous literature dealt basically with supersingular curves (in characteristic 3, although the methods can be easily extended to arbitrary characteristic), where A,B ∈ ℕ. Only [4] attempted to provide a similar method for Koblitz curves, where at least one base must be non-real, although their method does not seem practical for cryptographic sizes (it is only asymptotic), since the constants involved are too large. We provide here a unifying theory by proposing an alternate recoding algorithm which works in all cases with optimal constants. Furthermore, it can also solve the until now untreatable case where both A and B are non-real. The resulting scalar multiplication method is then compared to standard methods for Koblitz curves. It runs in less than logn/loglogn elliptic curve additions, and is faster than any given method with similar storage requirements already on the curve K-163, with larger improvements as the size of the curve increases, surpassing 50% with respect to the τ-NAF for the curves K-409 and K-571. With respect of windowed methods, that can approach our speed but require O(log(n)/loglog(n)) precomputations for optimal parameters, we offer the advantage of a fixed, small memory footprint, as we need storage for at most two additional points.

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

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

U2 - 10.1007/11935230_9

DO - 10.1007/11935230_9

M3 - Conference contribution

SN - 3540494758

SN - 9783540494751

VL - 4284 LNCS

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

SP - 130

EP - 144

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

ER -