On the enumeration of double-base chains with applications to elliptic curve cryptography

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 260 bits in a few minutes. Second, we introduce an original and potentially more efficient approach to compute a random scalar multiplication [n]P, based on the concept of controlled DBC. Instead of generating a random integer n and then trying to find an optimal, or at least a short DBC to represent it, we propose to directly generate n as a random DBC with a chosen leading factor 2a3b 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 2a3b 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 10% with respect to the NAF for sizes from 192 to 512 bits. Computations involve elliptic curves defined over Fp, using the Inverted Edwards coordinate system and state of the art scalar multiplication techniques.