1. Paper title: Evolutionary Algorithms-assisted Construction of Cryptographic Boolean Functions ------------------------- 2. Author contact details: Claude Carlet, University of Bergen, Bergen, Norway and Université Paris 8, Département de mathématiques 2 rue de la liberté, 93526 Saint-Denis, Cedex, France, claude.carlet@gmail.com, 0033630389528 Stjepan Picek, Cyber Security Research Group, Delft University of Technology, Mekelweg 2, Delft, The Netherlands, s.picek@tudelft.nl, 0038598226407 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 ------------------------- 3. Corresponding author: Stjepan Picek ------------------------- 4. Paper abstract: In the last few decades, evolutionary algorithms were successfully applied numerous times for creating Boolean functions with good cryptographic properties. Still, the applicability of such approaches was always limited as the cryptographic community knows how to construct suitable Boolean functions with deterministic algebraic constructions. Thus, evolutionary results so far helped to increase the confidence that evolutionary techniques have a role in cryptography, but at the same time, the results themselves were seldom used. This paper considers a novel problem using evolutionary algorithms to improve Boolean functions obtained through algebraic constructions. To this end, we consider a recent generalization of Hidden Weight Boolean Function construction, and we show that evolutionary algorithms can significantly improve the cryptographic properties of the functions. Our results show that the genetic algorithm performs by far the best of all the considered algorithms and improves the nonlinearity property in all Boolean function sizes. As there are no known algebraic techniques to reach the same goal, we consider this application a step forward in accepting evolutionary algorithms as a powerful tool in the cryptography domain. ------------------------- 5. Relevant criteria: B, D, E, F, G ------------------------- 6. Statement: Our paper has shown that evolutionary algorithms can construct Boolean functions of practical sizes (e.g., 16 to 18 inputs) that have better cryptographic properties than achievable with algebraic constructions or any other human-made technique. At the same time, exhaustive search is already impossible for much smaller sizes (e.g., 9 inputs). Since we also use GP, we manage to find small, cheap (in terms of area), and fast constructions to implement, which is relevant for hardware implementations. This covers criteria B, E, and F. Finding Boolean functions of sufficient size, cryptographic properties, and implementation properties is a difficult and long-standing problem. Since our results are accepted for GECCO 2021 and have practical implications, this covers criteria D and G. ------------------------- 7. Citation: Claude Carlet, Stjepan Picek, Domagoj Jakobovic. Evolutionary Algorithms-assisted Construction of Cryptographic Boolean Functions. GECCO ’21, July 10–14, 2021, Lille, France, DOI: https://doi.org/10.1145/3449639.3459362 Note: this paper is accepted as a full paper for GECCO 2021, so it is in press status. ------------------------- 8. Any prize money, if any, is to be divided equally among the co-authors. ------------------------- 9. "Best" statement: Boolean functions are an important primitive in cryptography, telecommunication, coding theory, sequences, etc. Still, not all Boolean functions can be used but only those that fulfill different properties. The most important property is nonlinearity, while other important ones include speed (how complex the function is) and algebraic immunity (to resist specific types of attacks). One simple yet powerful Boolean function construction is called the Hidden Weight Boolean Function (HWBF) construction. While being extremely simple to implement and fast to execute, the nonlinearity obtained from it is far from optimal (which actually prohibited the use of that construction more widely). Recently, there is a proposal on generalizing this construction while allowing it to maintain speed and good algebraic immunity. Unfortunately, this generalization did not sufficiently improve the nonlinearity property, and there are no human-made techniques (to the best of our knowledge) that can further improve that property. We use evolutionary algorithms to find the positions in the truth table representation of a Boolean function, whose values can then be altered, resulting in a significant increase in nonlinearity. As an example, for the Boolean function with 18 inputs, the original HWBF construction results in nonlinearity of 105332, and the generalized construction has a nonlinearity of 110194. Our approach found Boolean functions with nonlinearity 116840 (the higher nonlinearity, the better). Our results open a new chapter on the usability of fast Boolean functions with high nonlinearity. Our contribution is accepted as a full paper at GECCO 2021. ------------------------- 10. Method used: GA (genetic algorithms), GP (genetic programming), ES (evolution strategy) ------------------------- 11. The date of publication of each paper. The paper is in the press for GECCO 2021, where it is accepted as a full paper. We attach the copyright notice to show its status.