Scalar multiplication on Koblitz curves using double bases

Roberto Avanzi, Francesco Sica

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

11 Citations (Scopus)

Abstract

The paper is an examination of double-base decompositions of integers n, namely expansions loosely of the form n = Σi, j ± A iBj for some base {A, B}. This was examined in previous works [5,6], in the case when A, B lie in N. We show here how to extend the results of [5] to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer n and an elliptic curve point P, the point nP in time O (log n / log lgo n) elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. In view of combinatorial results, this is the best type of estimate with two bases, apart from the value of the constant in the O notation.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages131-146
Number of pages16
Volume4341 LNCS
DOIs
Publication statusPublished - 2006
Externally publishedYes
Event1st International Conference on Cryptology in Vietnam, VIETCRYPT 2006 - Hanoi, Viet Nam
Duration: Sep 25 2006Sep 28 2006

Publication series

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

Other

Other1st International Conference on Cryptology in Vietnam, VIETCRYPT 2006
CountryViet Nam
CityHanoi
Period9/25/069/28/06

Fingerprint

Scalar multiplication
Elliptic Curves
P-point
Curve
Integer
Notation
Scalar
Binary
Decomposition
Decompose
Estimate
Form

Keywords

  • Double base number systems
  • Elliptic curves
  • Koblitz curves
  • Scalar multiplication
  • Sublinear algorithms

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Avanzi, R., & Sica, F. (2006). Scalar multiplication on Koblitz curves using double bases. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 4341 LNCS, pp. 131-146). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4341 LNCS). https://doi.org/10.1007/11958239-9

Scalar multiplication on Koblitz curves using double bases. / Avanzi, Roberto; Sica, Francesco.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 4341 LNCS 2006. p. 131-146 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4341 LNCS).

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

Avanzi, R & Sica, F 2006, Scalar multiplication on Koblitz curves using double bases. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 4341 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4341 LNCS, pp. 131-146, 1st International Conference on Cryptology in Vietnam, VIETCRYPT 2006, Hanoi, Viet Nam, 9/25/06. https://doi.org/10.1007/11958239-9
Avanzi R, Sica F. Scalar multiplication on Koblitz curves using double bases. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 4341 LNCS. 2006. p. 131-146. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11958239-9
Avanzi, Roberto ; Sica, Francesco. / Scalar multiplication on Koblitz curves using double bases. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 4341 LNCS 2006. pp. 131-146 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{eee3f744b735460d888198a363127a87,
title = "Scalar multiplication on Koblitz curves using double bases",
abstract = "The paper is an examination of double-base decompositions of integers n, namely expansions loosely of the form n = Σi, j ± A iBj for some base {A, B}. This was examined in previous works [5,6], in the case when A, B lie in N. We show here how to extend the results of [5] to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer n and an elliptic curve point P, the point nP in time O (log n / log lgo n) elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. In view of combinatorial results, this is the best type of estimate with two bases, apart from the value of the constant in the O notation.",
keywords = "Double base number systems, Elliptic curves, Koblitz curves, Scalar multiplication, Sublinear algorithms",
author = "Roberto Avanzi and Francesco Sica",
year = "2006",
doi = "10.1007/11958239-9",
language = "English",
isbn = "3540687998",
volume = "4341 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "131--146",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - GEN

T1 - Scalar multiplication on Koblitz curves using double bases

AU - Avanzi, Roberto

AU - Sica, Francesco

PY - 2006

Y1 - 2006

N2 - The paper is an examination of double-base decompositions of integers n, namely expansions loosely of the form n = Σi, j ± A iBj for some base {A, B}. This was examined in previous works [5,6], in the case when A, B lie in N. We show here how to extend the results of [5] to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer n and an elliptic curve point P, the point nP in time O (log n / log lgo n) elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. In view of combinatorial results, this is the best type of estimate with two bases, apart from the value of the constant in the O notation.

AB - The paper is an examination of double-base decompositions of integers n, namely expansions loosely of the form n = Σi, j ± A iBj for some base {A, B}. This was examined in previous works [5,6], in the case when A, B lie in N. We show here how to extend the results of [5] to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer n and an elliptic curve point P, the point nP in time O (log n / log lgo n) elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. In view of combinatorial results, this is the best type of estimate with two bases, apart from the value of the constant in the O notation.

KW - Double base number systems

KW - Elliptic curves

KW - Koblitz curves

KW - Scalar multiplication

KW - Sublinear algorithms

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

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

U2 - 10.1007/11958239-9

DO - 10.1007/11958239-9

M3 - Conference contribution

SN - 3540687998

SN - 9783540687993

VL - 4341 LNCS

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

SP - 131

EP - 146

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

ER -