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 publicationProgress in Cryptology, VIETCRYPT 2006 - 1st International Conference on Cryptology in Vietnam, Revised Selected Papers
Pages131-146
Number of pages16
DOIs
Publication statusPublished - Dec 1 2006
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)0302-9743
ISSN (Electronic)1611-3349

Other

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

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Scalar multiplication on Koblitz curves using double bases'. Together they form a unique fingerprint.

  • Cite this

    Avanzi, R., & Sica, F. (2006). Scalar multiplication on Koblitz curves using double bases. In Progress in Cryptology, VIETCRYPT 2006 - 1st International Conference on Cryptology in Vietnam, Revised Selected Papers (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