1. Paper title: Evolutionary Algorithms for Finding Short Addition Chains: Going the Distance ------------------------- 2. Author contact details: Stjepan Picek, Afdeling ESAT - COSIC, Kasteelpark Arenberg 10 - bus 2452, 3001 Heverlee, Belgium, stjepan@computer.org, 0038598226407 Carlos A. Coello Coello, CINVESTAV-IPN Depto. de Computación Av. Instituto Politécnico Nacional No. 2508 Col. San Pedro Zacatenco México, D.F. 07300, ccoello@cs.cinvestav.mx, +52 55 5747 3800 ext. 6564 Domagoj Jakobovic, Dept. of Electronics, Microelectronics, Computer and Intelligent Systems Faculty of Electrical Engineering and Computing Unska 3, 10000 Zagreb, Croatia, domagoj.jakobovic@fer.hr, 0038516129967 Nele Mentens, Afdeling ESAT - COSIC, Kasteelpark Arenberg 10 - bus 2452, 3001 Heverlee, Belgium, Nele.Mentens@kuleuven.be, 003211180920 ------------------------- 3. Corresponding author: Stjepan Picek ------------------------- 4. Paper abstract: The problem of finding the shortest addition chain for a given exponent is of great relevance in cryptography, but is also very difficult to solve since it is an NP-hard problem. In this paper, we propose a genetic algorithm with a novel representation of solutions and new crossover and mutation operators to minimize the length of the addition chains corresponding to a given exponent. We also develop a repair strategy that significantly enhances the performance of our approach. The results are compared with respect to those generated by other metaheuristics for instances of moderate size, but we also investigate values up to 2^{127} - 3. For those instances, we were unable to find any results produced by other metaheuristics for comparison, and three additional strategies were adopted in this case to serve as benchmarks. Our results indicate that the proposed approach is a very promising alternative to deal with this problem. ------------------------- 5. Relevant criteria: D, E, G ------------------------- 6. Statement: In this paper, we present an application of GA in order to find shortest addition chains (believed to be NP-hard problem). Such addition chains have practical applications in the field of cryptography where they are used in fast calculation of modular exponentiation. Up to now, evolutionary computation was used to tackle this problem, but only with small exponent sizes (e.g., 14143037) that do not have any practical relevance. In our paper we designed GA that uses custom variation operators as well as a novel repair strategy in order to find short chains for values up to 2^(127) - 3. This number has practical relevance and the shortest chain we found (size 136) is also the shortest currently known chain where our method offers greater speed as well as diversity in the obtained solutions, i.e., we did not find only one chain of length 136 but several ones. These experiments are able to run on a standard desktop PC and the optimal results are obtained already in ~10 mins. To reach such a solution, related work used a combination of deterministic algorithms and expert human input. ------------------------- 7. Citation: Picek, S., Coello, C.A.C., Jakobovic, D., Mentens, N.: Evolutionary Algorithms for Finding Short Addition Chains: Going the Distance. Editors: Chicano, F., Hu, B., and Garcia-Sanchez, P. In: Evolutionary Computation in Combinatorial Optimization - 16th European Conference, EvoCOP 2016, Porto, Portugal, March 30 - April 1, 2016, Proceedings. (2016) 121-137. Please use the link: http://link.springer.com/chapter/10.1007%2F978-3-319-30698-8_9 ------------------------- 8. Any prize money, if any, is to be divided equally among the co-authors. ------------------------- 9. "Best" statement: We demonstrated a notable contribution with a significant impact to cryptography. Short addition chains enable faster calculation and are therefore of practical relevance for huge number of deployed devices that use cryptographic algorithms. Our approach can be easily extended to even larger addition chain values where the results again show that the optimal results can be obtained. Our results are human competitive and outperform several widely used deterministic algorithms. Furthermore, our results are competitive with results obtained via combination of deterministic methods and expert human input. Our contribution was accepted by an prominent conference in the field of natural computing - Evostar 2015. ------------------------- 10. Method used: Genetic Algorithm