Article ID Journal Published Year Pages File Type
427811 Information Processing Letters 2011 6 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,