An analysis of double base number systems and a sublinear scalar multiplication algorithm

Mathieu Ciet, Francesco Sica

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

16 Citations (Scopus)

Abstract

In this paper we produce a practical and efficient algorithm to find a decomposition of type n = ∑i=1k2si3 ti, si ti ∈ ℕ ∪ {0} with k ≤ (c +o(1)) log n/log log n . It is conjectured that one can take c = 2 above. Then this decomposition is refined into an effective scalar multiplication algorithm to compute nP on some supersingular elliptic curves of characteristic 3 with running time bounded by O (log n/log log n) and essentially no storage. To our knowledge, this is the first instance of a scalar multiplication algorithm that requires o(log n) curve operations on an elliptic curve over double struck F signq, with log q ≈ log n and uses comparable storage as in the standard double-and-add algorithm. This leads to an efficient algorithm very useful for cryptographic protocols based on supersingular curves. This is for example the case of the well-studied (in the past four years) identity based schemes. The method carries over to any supersingular curve of fixed characteristic.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages171-182
Number of pages12
DOIs
Publication statusPublished - Dec 1 2005
Event1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005 - Kuala Lumpur, Malaysia
Duration: Sep 28 2005Sep 30 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3715 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005
CountryMalaysia
CityKuala Lumpur
Period9/28/059/30/05

Keywords

  • Exponentiation algorithms
  • Integer decomposition

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An analysis of double base number systems and a sublinear scalar multiplication algorithm'. Together they form a unique fingerprint.

  • Cite this

    Ciet, M., & Sica, F. (2005). An analysis of double base number systems and a sublinear scalar multiplication algorithm. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 171-182). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3715 LNCS). https://doi.org/10.1007/11554868_12