Finding short and implementation-friendly addition chains with evolutionary algorithms

Stjepan Picek (), Carlos A. Coello Coello (), Domagoj Jakobovic () and Nele Mentens ()
Additional contact information
Stjepan Picek: KU Leuven, ESAT/COSIC and Imec
Carlos A. Coello Coello: CINVESTAV-IPN
Domagoj Jakobovic: University of Zagreb
Nele Mentens: KU Leuven, ESAT/COSIC and Imec

Journal of Heuristics, 2018, vol. 24, issue 3, No 10, 457-481

Abstract: Abstract Finding the shortest addition chain for a given exponent is a significant problem in cryptography. In this work, we present a genetic algorithm with a novel encoding 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 exponents of moderate size, but we also investigate values up to $$2^{255} - 21$$ 2 255 - 21 . For numbers of such size, we were unable to find any results produced by other metaheuristics which could be used for comparison purposes. Therefore, we decided to add three additional strategies to serve as benchmarks. Our results indicate that the proposed approach is a very promising alternative to deal with this problem. We also consider a more practical perspective by taking into account the implementation cost of the chains: we optimize the addition chains with regards to the type of operations as well as the number of instructions required for the implementation.

Keywords: Addition chains; Genetic algorithms; Cryptography; Optimization; Implementation (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-017-9340-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:24:y:2018:i:3:d:10.1007_s10732-017-9340-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-017-9340-2

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().