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=1 k2si3 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
Volume3715 LNCS
DOIs
Publication statusPublished - 2005
Externally publishedYes
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)03029743
ISSN (Electronic)16113349

Other

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

Fingerprint

Numbering systems
Scalar multiplication
Number system
Elliptic Curves
Curve
Efficient Algorithms
Decompose
Cryptographic Protocols
Identity-based
Decomposition

Keywords

  • Exponentiation algorithms
  • Integer decomposition

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

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) (Vol. 3715 LNCS, 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

An analysis of double base number systems and a sublinear scalar multiplication algorithm. / Ciet, Mathieu; Sica, Francesco.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 3715 LNCS 2005. p. 171-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3715 LNCS).

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

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). vol. 3715 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3715 LNCS, pp. 171-182, 1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005, Kuala Lumpur, Malaysia, 9/28/05. https://doi.org/10.1007/11554868_12
Ciet M, Sica F. 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). Vol. 3715 LNCS. 2005. p. 171-182. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11554868_12
Ciet, Mathieu ; Sica, Francesco. / An analysis of double base number systems and a sublinear scalar multiplication algorithm. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 3715 LNCS 2005. pp. 171-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{201e77eec1b041c9835ce0ace538f589,
title = "An analysis of double base number systems and a sublinear scalar multiplication algorithm",
abstract = "In this paper we produce a practical and efficient algorithm to find a decomposition of type n = ∑i=1 k2si3 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.",
keywords = "Exponentiation algorithms, Integer decomposition",
author = "Mathieu Ciet and Francesco Sica",
year = "2005",
doi = "10.1007/11554868_12",
language = "English",
isbn = "3540289380",
volume = "3715 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "171--182",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - GEN

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

AU - Ciet, Mathieu

AU - Sica, Francesco

PY - 2005

Y1 - 2005

N2 - In this paper we produce a practical and efficient algorithm to find a decomposition of type n = ∑i=1 k2si3 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.

AB - In this paper we produce a practical and efficient algorithm to find a decomposition of type n = ∑i=1 k2si3 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.

KW - Exponentiation algorithms

KW - Integer decomposition

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

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

U2 - 10.1007/11554868_12

DO - 10.1007/11554868_12

M3 - Conference contribution

SN - 3540289380

SN - 9783540289388

VL - 3715 LNCS

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

SP - 171

EP - 182

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

ER -