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 $2^a3^b$ 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 $2^{60}$ 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 $2^a3^b$ and length $\ell$. To inform the selection of those parameters, in particular $\ell$, 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 $2^a3^b$ and a certain length $\ell$. 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 $\F_p$, using the Inverted Edwards coordinate system and state of the art scalar multiplication techniques.