Paper 2006/330

Extended Double-Base Number System with applications to Elliptic Curve Cryptography

Christophe Doche and Laurent Imbert

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 {\em 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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of a paper to appear in the procedding of Indocrypt 2006
Keywords
Double-Base Number SystemElliptic Curve Cryptography
Contact author(s)
doche @ ics mq edu au
History
2006-10-05: received
Short URL
https://ia.cr/2006/330
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/330,
      author = {Christophe Doche and Laurent Imbert},
      title = {Extended Double-Base Number System with applications to Elliptic Curve Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2006/330},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/330}},
      url = {https://eprint.iacr.org/2006/330}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.