*12:17*[Pub][ePrint] On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography, by Christophe Doche

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 \\lt{} 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$, called 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 length $\\ell$ and \\lt{} $2^a3^b$.

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 certain length $\\ell$ and a given

\\lt{} $2^a3^b$.

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. Our experiments indicate that the controlled DBC provides a speedup of at

least $6.98\\%$ and up to $8\\%$ for sizes from $192$ to $512$ bits. Experiments involve elliptic

curves defined over $\\F_p$, using the Inverted Edwards coordinate system and state of the art

scalar multiplication techniques.