Optimal 2-3 Chains for Scalar Multiplication

Using double-base chains to represent integers, in particular chains with bases 2 and 3, can be beneficial to the efficiency of scalar multiplication. However, finding an optimal 2-3 chain as long been thought to be more expensive than the scalar multiplication itself, complicating the use of 2-3 chains in practical applications where the scalar is used only a few time (as in the Diffie-Hellman key exchange). In the last few years, important progress has been made in obtaining the shortest possible double-base chain for a varying integer n. In 2008, Doche and Habsieger used a binary-tree based approach to get a (relatively close) approximation of the minimal chain. In 2015, Capuñay and Thériault presented the first deterministic polynomial-time algorithm to compute the minimal chain for a scalar, but the complexity of O((log n)3+ε) is too high for use with a varying scalars. More recently, Bernstein, Chuengsatiansup, and Lange used a graph-based approach to obtain an algorithm with running time O((log n)2.5+ε). In this work, we adapt the algorithm of Capuñay and Thériault to obtain minimal chains in O((log n)2 log log n) bit operations and O((log n)2) bits of memory. This allows us to obtain minimal chains for 256-bits integers in the 0.280 ms range, making it useful to reduce scalar multiplication costs randomly-selected scalars. We also show how to extend the result to other types of double-base and triple-base chains (although the complexity for triple-base chains is cubic instead of quadratic). In the case of environments with restricted memory, our algorithm can be adapted to compute the minimal chain in O((log n)2 (log log n)2) bit operations with only O(log n(log log n)2) bits of memory. © Springer Nature Switzerland AG 2019.