Enumerating Double-Base Chains with Applications to Elliptic Curve Cryptography

Abstract: 

A Double-Base Chain (DBC) uses two bases, 2 and 3, in order to represent an integer. This concept is useful in Cryptography in the context of a scalar multiplication performed on an elliptic curve. We will outline two contributions. First, generalising work of Erdős and Loxton, we outline a recursive algorithm to compute the number of different DBCs with a leading factor dividing 2^a*3^b and representing n. A simple modification of the algorithm allows to determine an optimal DBC, i.e. an expansion with minimal length representing n. Second, we propose to directly generate a scalar n as a random DBC with a chosen leading factor 2^a*3^b and given length, instead of generating a random integer n and then trying to find an optimal, or at least a short DBC to represent it. In order to inform the selection of those parameters, which drive 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^a*3^b and a certain length. The comparison between this total number of DBCs and the total number of integers that we need to represent provides some guidance regarding the selection of suitable parameters.