On the Improvement of Addition Chain in Applications to Elliptic Curve Cryptosystem Status: Submitted

A hard problem most of the time can be broken into a sequence of simple tasks from which a solution to the original problem is obtainable. Originally, elliptic curve cryptography is based on a non-singular algebraic curve of genus 1. The process of encrypting message involves modular operation of huge integer n acting on points on elliptic curve. This operation namely scalar multiplication is formularized as Q = nP. By restricting to only addition and doubling operations of two previous terms, it can be transformed into an equivalent iteration of Q = (2 . . . (2(2(P) + br−1P) + br−2P) + . . .) + b0P). The resulting ascending sequence is called an addition chain. Finding an optimal chain was proven to be an NP-complete problem. Notwithstanding, this gives way to the emergence of many heuristics methods offering near optimal solution. All in all, the study of efficient point arithmetic on elliptic curves can be reduced to the study of optimizing an addition chain. This thesis centers around an investigation into a new method to improve scalar multiplication operation. Ultimately, the objective is to minimize the execution time of EC point arithmetic. One of the ways to achieve this is through shorter addition chain. The proposed method will be developed from scratch, and are subjected to some theoretical analysis. For the purpose of empirical test, some parameters are defined in the course to validating the findings. Existing methods exploit the binary(m-ary) representation of an integer n, whilst the new method to be proposed opens up a new window of research into the problem. An integer n is decomposed into its prime factor pe1 1 pe2 2 . . . pes s . A classical one-layered approach is transformed into a two-layered approach. Efficiency can be improved at prime pi layer, prime power pei i layer and the combination of prime power layer that make up an n. Initially, a Decomposition Method (DM) is developed based on prime power factorization of an integer n. Each factor pi is assigned a unique rule from which an addition chain will be generated. An ei multiple of each rule pi generates an addition chain for pei of which be further combined altogether to build up n. Mathematical analysis shows that the chain generated by this method is confined to the similar boundary as that of an optimal chain studied by A. Brauer. Experiment shows a significant advantage over existing methods under appropriate working conditions. An improved version, Signed Decomposition Method (SDM) introduces a subtraction operation into the sequence to generate an addition subtraction chain. P. Erdos stated that addition subtraction chain is always at most as lengthy as an addition chain. It follows that SDM outperforms its predecessor by 8 percents. Moreover, the generated chains are shown to outclass existing methods with significant improvement. Additionally, we developed a Composition Method (CM) which bears the idea of computing addition chain directly from the respective rule for n. Unlike decomposition based methods, CM brings back the approach to one-layered with most of its properties are inherited from DM at prime layer. An improved version called Signed Composition Method (SCM) is also proposed as an implication of introducing a subtraction operation into CM. The generated chain by SCM has recorded an improvement of 10 percent over its predecessor. Furthermore, SCM has shown an advantage over existing methods for selected integers. Earlier comparison between DM and CM favours DM for most n. However, experimental result for SDM against SCM shows that for small integers SDM is in favour over SCM, but as n grows, SCM gradually start to outperform

Preview PDF IPM_2011_9_ir.pdf Download (425kB)

Actions (login required)

View Item