Bounds and trade-offs for Double-Base Number Systems

During the past twenty years, elliptic curves have attracted more and more attention from the cryptography community. One of the core operations of elliptic curve cryptography protocols is the scalar multiplication. Any algorithm reducing the complexity of such multiplications will speed up cryptographic primitives based on these algebraic structures. In this paper, we study two recently introduced techniques for scalar multiplication: Double-Base Number System (DBNS) and Double-Base Chain (DBC). Our results are twofold. First, we demonstrate a theoretical bound Ω(logn) on the length of any DBC used to decompose some (logn)-bit integers. Second, we present a new algorithm to obtain a {2,3}{2,3}-integer expansion of n. The bound previously computed will imply the optimality of this algorithm. Our scheme represents a trade-off method between the DBNS approach and the DBC technique. Experimentally, our algorithm constructs shorter chains on average than both the binary/ternary method and the greedy algorithm approach.

Research highlights
► Integer decomposition for scalar multiplication over elliptic curves.
► The length of double-base chains is Ω(logn) for some (logn)-bit integers.
► This bound leads to an optimal algorithm for {2,3}{2,3}-integer expansion.
► Our implementations return short expansion chains.