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

Christophe Doche 1 Laurent Imbert 2
2 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Communication dans un congrès
INDOCRYPT'06: Progress in Cryptology, Dec 2006, Kolkata, India, Springer, pp.335-348, 2006, LNCS
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00125442
Contributeur : Laurent Imbert <>
Soumis le : vendredi 19 janvier 2007 - 15:09:10
Dernière modification le : mardi 11 décembre 2018 - 17:16:02
Document(s) archivé(s) le : mardi 6 avril 2010 - 21:05:45

Identifiants

  • HAL Id : lirmm-00125442, version 1

Collections

Citation

Christophe Doche, Laurent Imbert. Extended Double-Base Number System with Applications to Elliptic Curve Cryptography. INDOCRYPT'06: Progress in Cryptology, Dec 2006, Kolkata, India, Springer, pp.335-348, 2006, LNCS. 〈lirmm-00125442〉

Partager

Métriques

Consultations de la notice

219

Téléchargements de fichiers

345