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

Christophe Doche*, Laurent Imbert

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

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

Original languageEnglish
Title of host publicationProgress in cryptology
Subtitle of host publicationINDOCRYPT 2006
EditorsRana Barua, Tanja Lange
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages336-348
Number of pages14
ISBN (Print)9783540497677
Publication statusPublished - 2006
Event7th International Conference on Cryptology in India - Calcutta, India
Duration: 11 Dec 200613 Dec 2006

Publication series

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

Conference

Conference7th International Conference on Cryptology in India
CountryIndia
CityCalcutta
Period11/12/0613/12/06

Keywords

  • double-base number system
  • elliptic curve cryptography

Cite this