Abstract
A new version of the ISD method for computing a scalar multiplication on elliptic curve defined over prime field has been proposed. This version is called the soft graphic ISD (SG-ISD) method. The SG-ISD method employed the connected sub-graphs of undirected simple graph, which formed a soft graph (F, A) generated by a set valued function F, to represent the sub-scalars of ISD method. Thus, undirected simple graph can be proved as the SG-ISD version. On the SG-ISD method, the binary representations, which are all edges of the ISD sub-scalars that forms a nonempty set A, has been done directly from the connected sub-graphs. So, every ISD version of a scalar k is proven mathematically as the SG-ISD version of k in an elliptic scalar multiplication kP. New experimental results on the proposed SG-ISD method are presented. The computational complexities of the original ISD and proposed SG-ISD methods are determined mathematically on the basis of the counting operations. These operations are elliptic curve and finite field operations. The comparison results on these computational complexities of the ISD and SG-ISD methods have been discussed. The experiments on the computational complexities reveal that the SG-ISD method is faster than the ISD method. Thus, the SG-ISD method is considered as an efficient algorithm in comparison with the original ISD for cryptographic applications.