Paper 2014/371

On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography

Christophe Doche

Abstract

The Double-Base Number System (DBNS) uses two bases, 2 and 3, in order to represent any integer n. A Double-Base Chain (DBC) is a special case of a DBNS expansion. DBCs have been introduced to speed up the scalar multiplication [n]P on certain families of elliptic curves used in cryptography. In this context, our contributions are twofold. First, given integers n, a, and b, we outline a recursive algorithm to compute the number of different DBCs with a leading factor dividing 2a3b and representing n. A simple modification of the algorithm allows to determine the number of DBCs with a specified length as well as the actual expansions. In turn, this gives rise to a method to compute an optimal DBC representing n, i.e. an expansion with minimal length. Our implementation is able to return an optimal expansion for most integers up to bits in a few minutes. Second, we introduce an original and potentially more efficient approach to compute a random scalar multiplication , based on the concept of controlled DBC. Instead of generating a random integer and then trying to find an optimal, or at least a short DBC to represent it, we propose to directly generate as a random DBC with a chosen leading factor and length . To inform the selection of those parameters, in particular , which drives the trade-off between the efficiency and the security of the underlying cryptosystem, we enumerate the total number of DBCs having a given leading factor and a certain length . The comparison between this total number of DBCs and the total number of integers that we wish to represent a priori provides some guidance regarding the selection of suitable parameters. Experiments indicate that our new Near Optimal Controlled DBC approach provides a speedup of at least with respect to the NAF for sizes from to bits. Computations involve elliptic curves defined over , using the Inverted Edwards coordinate system and state of the art scalar multiplication techniques.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2014
Keywords
Double-base number systemelliptic curve cryptography.
Contact author(s)
christophe doche @ mq edu au
History
2014-09-16: last of 2 revisions
2014-05-27: received
See all versions
Short URL
https://ia.cr/2014/371
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/371,
      author = {Christophe Doche},
      title = {On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/371},
      year = {2014},
      url = {https://eprint.iacr.org/2014/371}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.