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, and , in order to represent any integer . A Double-Base Chain (DBC) is a special case of a DBNS expansion. DBCs have been introduced to speed up the scalar multiplication on certain families of elliptic curves used in cryptography. In this context, our contributions are twofold. First, given integers , , and , we outline a recursive algorithm to compute the number of different DBCs with a leading factor dividing and representing . 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 , 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.
@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.