**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 \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.

**Category / Keywords: **public-key cryptography / Double-base number system, elliptic curve cryptography.

**Date: **received 26 May 2014

**Contact author: **christophe doche at mq edu au

**Available format(s): **PDF | BibTeX Citation

**Version: **20140527:102112 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]