Keywords

1 Introduction

Nowadays, information security is at the greatest importance in which communication over open networks and storage of data in digital form plays a key role in daily life. The science of cryptography provides efficient tools to secure information. Cryptography is defined as the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity identification, and data origin authentication. Due to their tampered resistance, cryptosystems are often implemented on constraint memory devices such as smart cards. For such cases elliptic curve cryptosystems (ECC) [1, 2] is considered to be the most appropriate. The ECC exploited the discrete logarithm problem on a general elliptic curve that has no subexponential time solution. The major advantage of ECC is that a small key of size 160-bits can provide comparable security level with other cryptographic standards such as RSA of 1024-bits but with much faster and and more efficient execution.

The basic operation of ECC involves scalar and multi-scalar multiplication. Addition chain method has been widely used to improved efficiency of large number operation such that found in ECC. An addition chain (AC) for a number n is a sequence, such that each new member is the sum of two earlier (not necessarily distinct) ones. The length of an AC for an integer n is calculated as the number of terms other than the first one. The number of operations is directly proportional to the number of terms. This way, efficiency can be achieved if we can have shorter chain that is, the number of operations can be reduced by shortening the sequence.

Many AC method have been introduced. This is due to finding the optimal chain for a set of numbers was proven to be NP-complete [3]. These methods aimed at generating chain closest to optimal value. AC methods can be grouped into two major family, heuristics and metaheuristics. One method is known to be no better than the other except on certain occasions for certain groups of integers. However, there is lack of performance evaluation in term of length generated to compare the efficiency of different methods. Therefore, some performance analysis focusing on finding the shorter length need to be done. In this study, we conduct performance evaluation by comparing the length of selected AC for heuristic methods to find the best methods (with shortest length) by focusing on comparing seven methods, evaluating integer from 2 to 180,000.

The remainder of this paper is structured as follows; Sect. 2 summaries the review of literature. Section 3 states the materials and methods used in this project. These will be followed by the results and discussion in Sect. 4 and conclusion in Sect. 5.

2 Related Works

There are many AC methods that have been introduced in order to find sub-optimal solution. The literatures divide them into two categories that are meta-heuristics and heuristics [4]. A meta-heuristics is an iterative master process that guides and modifies the operations of subordinates heuristics to efficiently produce high-quality solutions. Meta-heuristics support decision making with robust tools that provide high quality solution to important application in business, engineering, economics and science. Common target of meta-heuristics are to solve optimization problem usually known by their complexities and it is inspired by analogies related to other factor such as natural, chemical, biological, electrical and thermal.

In solving AC problem, many meta-heuristics methods have been proposed. Genetic algorithms was first used by [5], allowing one-point crossover and uniform mutation, followed by [6] with the use of two-point crossover together with a local search mutation operator and a repair mechanism built within the initialization of the population. The most notable one, which employ a representation based on factorial number system together with neighborhood functions and distribution functions is credited to [7]. Various other methods such as ant colony optimization [8], artificial immune system [9], population-based optimization [10], and simulated annealing [11]. However, the most notable one is that of an evolutionary programming (EP) [12]. EP simulates evolution at species level. Therefore, no crossover operator is employed. In this proposed approach, an individual is represented at genotype level, that is an individual is a feasible AC. The fitness value of each individual is the length of the AC. Therefore, shorter strings are preferred. An advantage of the EP algorithm comprises the solution encoding with suitable fitness function and initial population, a mutation operator, and the survivor selection mechanism. These elements are easy to implement comparing to operators such as crossover and parent selection found in genetic algorithm. However, there are a few issues with meta-heuristics techniques such as consume a lot time to get optimal results, dependencies of specific cases for good result and complexities in implementation.

Heuristic is a much simpler techniques which seeks good solutions at a reasonable computational cost. Heuristic is designed and tuned for some specific problem. Heuristics are criteria, methods, or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal. In broad, we can categorized these methods into a few different ways. By looking into the way of input representation we have binary or m-ary methods by using different radix, and unsigned and signed methods by allowing both positive and negative integer values. Either way, the idea is to reduce the number of operations that are addition and doubling, as much as possible. This can be done via manipulating the representation such that the digit representing the operation is reduced to the digit unpresented such that found in Binary Method (BM) [13]. Moreover, the location and adjacency of the digit can also be impactful for some methods such as Non-Adjacent Form (NAF) [14], and Complementary Recoding (CR) [15], Decomposition Method (DM) [16], Composition Method (CM) [17], Signed Decomposition Method (SDM) [18], and Signed Composition Method (SCM) [19].

3 Materials and Method

In general the studies of AC can be represented by a framework in Fig. 1. This section discusses how do we conduct the experiment and the tools required. The performance metric used is the length of the generated AC. The chosen methods are Binary Method, Non Adjacent Form, Complementary Recording, Decomposition Method, Composition Method, Signed Decomposition Method, and Signed Composition Method.

Fig. 1
figure 1

Investigative framework

Full size image

We implemented these algorithms based on that of suggested by the original articles and perform the performance measurement under Dev C++ environment. The GNU Multiple Precision Arithmetic Library (GMP) is a free library for arbitrary-precision arithmetic, operating on signed integers, rational numbers, and floating point numbers is used to support large integer operation. GMP has a rich set of functions, and the functions have a regular interface. Besides that main target applications of GMP are cryptography applications and research same as in our project. To install the GMP library a few tool should also be installed which are MinGW 3.4.2—used as interfaced, GCC and GCC++, and MySYS 1.0.10. Meanwhile, for graphing and analysis the GNUPlot 4.6 and Microsoft Excel 2010 are used respectively.

This whole experiment can be divided into 3 phases. First, we develop all the seven algorithms and measure their performance for integers from 1 to 180,000. An overall from this experiment, we can see the distribution of length for each integer. Second, we do the comparison using four group of test which are:

  • Test 1: We compare every two methods, totalling 21 combinations altogether, to find out how many wins (shorter), looses (longer) and draws (equal) in terms of the length of AC measured for every integer in each block.

  • Test 2: By splitting integers n into blocks such that \( 2^{N} \, + \, 1 \, \le \,n \, \le \,2^{N + 1} \) specified by N from 3 to 17, we compute an average length for each block.

  • Test 3: By separating odd (2k + 1) from even (2k) integers, we study the distribution of an AC generated by each method.

Finally, we plot the graph for every test done to observe the distribution and comparison then analyze the result.

4 Results and Discussion

In this section, we discuss the results that we have been obtained from our three experiment setup.

For Test 1, Fig. 2 shows the distribution of the length of AC produced by the seven different methods. Observably, the lengths for all methods are increasing when the integer are growing but the rates of growth are fairly small. Table 1 shows the list of comparisons between methods for 21 combinations. These comparisons calculate the wins, loose and draw in term of the length of AC. The method with more wins (shorter chain) is considered as winner. The more the method wins the shorter the method generated the length. The SCM has wins all the comparison against the other methods whereas, CM and BM produces chain of having the same lengths.

Fig. 2
figure 2

Distribution length of 7 methods

Full size image
Table 1 Length comparison
Full size table

For Test 2, the average length of AC for each block specified by the value of N are calculated by adding all the lengths for every integer and divide by N. Table 2 shows the result for \( 3 \, \le \,N\, \le \,17 \). We observed that for \( N \, \le \,8 \), SDM produces the shortest average among all methods, whereas for \( N\, > \,8 \), SCM seems to outclass all other methods.

Table 2 Average lengths
Full size table

From the Test 1 and Test 2, the methods can be ranked as SCM (shortest), SDM, NAF, DM, BM and CM, and CR. In both tests, we found out SDM and SCM methods are competing between each other in term of performance. The length of SCM becomes shortest when the integer number growth.

In Test 3, by separating even from odd integers, we plot graphs representing the length of AC produced by each method. For odd integer, Fig. 3 shows that SDM and SCM are competing to each other to become the method with the shortest AC. For even integers, Fig. 4 shows that NAF method has contributed to the production of the shortest AC alongside with SDM and SCM.

Fig. 3
figure 3

Distribution of length for odd integer

Full size image
Fig. 4
figure 4

Distribution of length for even integer

Full size image

5 Conclusion

Competitively, SDM and SCM generate the shortest length. Both methods use rules as their basis. However, SCM has outclassed SDM for large integers and therefore is more recommended for cryptographic implementation which utilizes large integers.