Enumerating Double-Base Chains with Applications to Elliptic Curve Cryptography


Christophe Doche


Macquarie University


Wed, 13/05/2015 - 1:30pm


OMB 145 (Old Main Building)


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.

School Seminar Series: