1. A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes
 
2. Claude Carlet, Department of Mathematics, Université Paris 8, 2 Rue de la Liberté, 93526 Saint-Denis Cedex, France & University of Bergen, Bergen, Norway,    
   claude.carlet@gmail.com
   Marko Ðurasevic, Faculty of Electrical Engineering and Computing, University of Zagreb, Unska 3, Zagreb, Croatia, marko.durasevic@fer.hr
   Domagoj Jakobovic, Faculty of Electrical Engineering and Computing, University of Zagreb, Unska 3, Zagreb, Croatia, domagoj.jakobovic@fer.hr
   Stjepan Picek, Digital Security Group, Radboud University, PO Box 9010, Nijmegen, The Netherlands, stjepan.picek@ru.nl, 0038598226407
   Luca Mariot, Semantics, Cybersecurity and Services Group, University of Twente, Drienerlolaan 5, 7522 NB Enschede, The Netherlands, l.mariot@utwente.nl
 
3. Stjepan Picek, stjepan.picek@ru.nl
 
4. Boolean functions are mathematical objects used in diverse applications. Different applications also have different requirements, making the research on Boolean functions very active. In the last 30 years, evolutionary algorithms have been shown to be a strong option for evolving Boolean functions in different sizes and with different properties. Still, most of those works consider similar settings and provide results that are mostly interesting from the evolutionary algorithm’s perspective. This work considers the problem of evolving highly nonlinear Boolean functions in odd sizes. While the formulation sounds simple, the problem is remarkably difficult, and the related work is extremely scarce. We consider three solutions encodings and four Boolean function sizes and run a detailed experimental analysis. Our results show that GP outperforms other EA in evolving highly nonlinear functions. Nevertheless, the problem is challenging, and finding optimal solutions is impossible except for the smallest tested size. However, once we added local search to the evolutionary algorithm, we managed to find a Boolean function in nine inputs with nonlinearity 241, which, to our knowledge, had never been accomplished before with evolutionary algorithms.
 
5. B, D, E, F
 
6. (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.
 
The question of whether a Boolean function in 9 variables can reach nonlinearity higher than 240 was open for more than 30 years. It was solved in 2007 when researchers used custom heuristics to design a function with nonlinearity 241. This represented a milestone since it resolved an important problem but also showed the potential of AI in the domain of Boolean function design and analysis. The result from 2007 was published in a prestigious journal, IEEE Transactions on Information Theory.
Despite numerous efforts in later years, other techniques on how to design such functions were not devised. In our work, we used general metaheuristics (genetic programming), and we reached the same nonlinearity level of 241. We emphasize that other results showed in the meantime that nonlinearity of 241 is also the optimal one for Boolean functions in 9 variables that are rotation symmetric (as the ones we looked at), making our result also the best possible one.
 
 
(D) The result is publishable in its own right as a new scientific result  independent of the fact that the result was mechanically created.
The importance of finding maximal reachable nonlinearity for Boolean functions is present in diverse domains like cryptography, coding theory, sequences, telecommunications, etc. New results on constructions, bounds, or best obtainable properties are regularly published in prestigious conferences and journals. 
As such, our result is clearly relevant and publishable. We note that our work also received the best paper award at EuroGP 2025.
 
(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.
 
The problem of constructing highly nonlinear Boolean functions in odd dimensions is long-standing. Dimension 9 represents a particular case where researchers could not find examples of nonlinearity higher than 240 for more than 30 years when the nonlinearity of 241 was achieved.
To our knowledge, there are no other techniques (including algebraic constructions) that could reach this value before our work.
As such, we showed that general metaheuristics could reach the best-obtained value, and since it is also proven in the meantime that this is the best possible value, we managed to reach the optimal value.
 
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
Since the result from 2007 represented a significant milestone, it sparked new interest in research on the best possible nonlinearity values for Boolean functions in an odd number of variables. Our approach resulted in the same nonlinearity, matching the optimal value. At the same time, for this result, we used genetic programming, while previous work required custom heuristics.
 
7. Carlet, C., Ðurasevic, M., Jakobovic, D., Picek, S., Mariot, L. (2025). A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes. In: Xue, B., Manzoni, L., Bakurov, I. (eds) Genetic Programming. EuroGP 2025. Lecture Notes in Computer Science, vol 15609. Springer, Cham. https://doi.org/10.1007/978-3-031-89991-1_2
 
8. Any prize money, if any, is to be divided equally among the co-authors.
 
9. Our entry showcases how metaheuristics (genetic programming) can achieve a nonlinearity of 241 for Boolean functions in dimension 9. This problem of whether such functions even exist was open for a long time and was solved only in 2007 with the usage of the specific heuristic technique developed explicitly for this problem. To our knowledge, there are no algebraic constructions capable of achieving this result (clearly showcasing the difficulty of the problem). Moreover, this result was also shown to be optimal for the class of rotation symmetric Boolean functions (that we explore in this paper). Our result is the first time that evolutionary algorithms managed to achieve this result, again demonstrating the importance of evolutionary computation for Boolean functions design.
 
10. Genetic programming (GP)
 
11. 18 April 2025