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

Mathieu Ciet; Francesco Sica

doi:10.1007/11554868_12

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

Mathieu Ciet, Francesco Sica

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Citations (Scopus)

Abstract

In this paper we produce a practical and efficient algorithm to find a decomposition of type n = ∑_i=1^k2^si3 ^ti, sⁱ tⁱ ∈ ℕ ∪ {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 sign_q, 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 language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	171-182
Number of pages	12
DOIs	https://doi.org/10.1007/11554868_12
Publication status	Published - Dec 1 2005
Event	1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005 - Kuala Lumpur, Malaysia Duration: Sep 28 2005 → Sep 30 2005

Publication series

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

Other

Other	1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005
Country	Malaysia
City	Kuala Lumpur
Period	9/28/05 → 9/30/05

Keywords

Exponentiation algorithms
Integer decomposition

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11554868_12

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

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). 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 proceeding › Conference 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). 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). 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). 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=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.",

keywords = "Exponentiation algorithms, Integer decomposition",

author = "Mathieu Ciet and Francesco Sica",

year = "2005",

month = dec,

day = "1",

doi = "10.1007/11554868_12",

language = "English",

isbn = "3540289380",

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)",

note = "1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005 ; Conference date: 28-09-2005 Through 30-09-2005",

}

TY - GEN

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

AU - Ciet, Mathieu

AU - Sica, Francesco

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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.

AB - 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.

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

AN - SCOPUS:33646198552

SN - 3540289380

SN - 9783540289388

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)

T2 - 1st International Conference on Cryptology in Malaysia on Progress in Cryptology - Mycrypt 2005

Y2 - 28 September 2005 through 30 September 2005

ER -