Extended double-base number system with applications to elliptic curve cryptography

Christophe Doche; Laurent Imbert

Extended double-base number system with applications to elliptic curve cryptography

Christophe Doche^*, Laurent Imbert

^*Corresponding author for this work

Department of Computing

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

35 Citations (Scopus)

Abstract

We investigate the impact of larger digit sets on the length of Double-Base Number system (DBNS) expansions. We present a new representation system called extended DBNS whose expansions can be extremely sparse. When compared with double-base chains, the average length of extended DBNS expansions of integers of size in the range 200– 500 bits is approximately reduced by 20% using one precomputed point, 30% using two, and 38% using four. We also discuss a new approach to approximate an integer n by d2^a3^b where d belongs to a given digit set. This method, which requires some precomputations as well, leads to realistic DBNS implementations. Finally, a left-to-right scalar multiplication relying on extended DBNS is given. On an elliptic curve where operations are performed in Jacobian coordinates, improvements of up to 13% overall can be expected with this approach when compared to window NAF methods using the same number of precomputed points. In this context, it is therefore the fastest method known to date to compute a scalar multiplication on a generic elliptic curve.

Original language	English
Title of host publication	Progress in cryptology
Subtitle of host publication	INDOCRYPT 2006
Editors	Rana Barua, Tanja Lange
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	336-348
Number of pages	14
ISBN (Print)	9783540497677
Publication status	Published - 2006
Event	7th International Conference on Cryptology in India - Calcutta, India Duration: 11 Dec 2006 → 13 Dec 2006

Publication series

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

Conference

Conference	7th International Conference on Cryptology in India
Country	India
City	Calcutta
Period	11/12/06 → 13/12/06

Keywords

double-base number system
elliptic curve cryptography

Access to Document

Link to publication in Scopus

Cite this

Doche, C., & Imbert, L. (2006). Extended double-base number system with applications to elliptic curve cryptography. In R. Barua, & T. Lange (Eds.), Progress in cryptology: INDOCRYPT 2006 (pp. 336-348). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4329). Berlin: Springer, Springer Nature.

Doche, Christophe ; Imbert, Laurent. / Extended double-base number system with applications to elliptic curve cryptography. Progress in cryptology: INDOCRYPT 2006. editor / Rana Barua ; Tanja Lange. Berlin : Springer, Springer Nature, 2006. pp. 336-348 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{344d36543c21493989b0099b6a5a6e23,

title = "Extended double-base number system with applications to elliptic curve cryptography",

abstract = "We investigate the impact of larger digit sets on the length of Double-Base Number system (DBNS) expansions. We present a new representation system called extended DBNS whose expansions can be extremely sparse. When compared with double-base chains, the average length of extended DBNS expansions of integers of size in the range 200– 500 bits is approximately reduced by 20{\%} using one precomputed point, 30{\%} using two, and 38{\%} using four. We also discuss a new approach to approximate an integer n by d2a3b where d belongs to a given digit set. This method, which requires some precomputations as well, leads to realistic DBNS implementations. Finally, a left-to-right scalar multiplication relying on extended DBNS is given. On an elliptic curve where operations are performed in Jacobian coordinates, improvements of up to 13{\%} overall can be expected with this approach when compared to window NAF methods using the same number of precomputed points. In this context, it is therefore the fastest method known to date to compute a scalar multiplication on a generic elliptic curve.",

keywords = "double-base number system, elliptic curve cryptography",

author = "Christophe Doche and Laurent Imbert",

year = "2006",

language = "English",

isbn = "9783540497677",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "336--348",

editor = "Rana Barua and Tanja Lange",

booktitle = "Progress in cryptology",

address = "United States",

}

Doche, C & Imbert, L 2006, Extended double-base number system with applications to elliptic curve cryptography. in R Barua & T Lange (eds), Progress in cryptology: INDOCRYPT 2006. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4329, Springer, Springer Nature, Berlin, pp. 336-348, 7th International Conference on Cryptology in India, Calcutta, India, 11/12/06.

Extended double-base number system with applications to elliptic curve cryptography. / Doche, Christophe; Imbert, Laurent.

Progress in cryptology: INDOCRYPT 2006. ed. / Rana Barua; Tanja Lange. Berlin : Springer, Springer Nature, 2006. p. 336-348 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4329).

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

TY - GEN

T1 - Extended double-base number system with applications to elliptic curve cryptography

AU - Doche, Christophe

AU - Imbert, Laurent

PY - 2006

Y1 - 2006

N2 - We investigate the impact of larger digit sets on the length of Double-Base Number system (DBNS) expansions. We present a new representation system called extended DBNS whose expansions can be extremely sparse. When compared with double-base chains, the average length of extended DBNS expansions of integers of size in the range 200– 500 bits is approximately reduced by 20% using one precomputed point, 30% using two, and 38% using four. We also discuss a new approach to approximate an integer n by d2a3b where d belongs to a given digit set. This method, which requires some precomputations as well, leads to realistic DBNS implementations. Finally, a left-to-right scalar multiplication relying on extended DBNS is given. On an elliptic curve where operations are performed in Jacobian coordinates, improvements of up to 13% overall can be expected with this approach when compared to window NAF methods using the same number of precomputed points. In this context, it is therefore the fastest method known to date to compute a scalar multiplication on a generic elliptic curve.

AB - We investigate the impact of larger digit sets on the length of Double-Base Number system (DBNS) expansions. We present a new representation system called extended DBNS whose expansions can be extremely sparse. When compared with double-base chains, the average length of extended DBNS expansions of integers of size in the range 200– 500 bits is approximately reduced by 20% using one precomputed point, 30% using two, and 38% using four. We also discuss a new approach to approximate an integer n by d2a3b where d belongs to a given digit set. This method, which requires some precomputations as well, leads to realistic DBNS implementations. Finally, a left-to-right scalar multiplication relying on extended DBNS is given. On an elliptic curve where operations are performed in Jacobian coordinates, improvements of up to 13% overall can be expected with this approach when compared to window NAF methods using the same number of precomputed points. In this context, it is therefore the fastest method known to date to compute a scalar multiplication on a generic elliptic curve.

KW - double-base number system

KW - elliptic curve cryptography

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

M3 - Conference proceeding contribution

SN - 9783540497677

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

SP - 336

EP - 348

BT - Progress in cryptology

A2 - Barua, Rana

A2 - Lange, Tanja

PB - Springer, Springer Nature

CY - Berlin

ER -