Addition chain heuristics in application to elliptic curve cryptosystems

Abstract

The idea of an addition chain can be applied to scalar multiplication involving huge number operations in elliptic curve cryptosystems. In this article, initially, we study the taxonomy of the addition chain problem to build up an understanding of the problem. We then examine the mathematics behind an optimal addition chain that includes the theoretical boundary for the upper limit and lower limit which laid the foundation for experimentation hereafter. In the following, we examine different addition chain solutions that were used to increase efficiency in scalar multiplication. To avoid any possible confusion, we intentionally separated the discussion into two modules called integer recoding method and chain generator based on the heuristics method. These methods were developed by considering various aspects such as the space within which the operation is executed, the curve that is selected, the formulation to express the original equation, and the choices of operation and arithmetic, all together to improve operational efficiency.