2025/04/24 by Carlet, Claude, Đurasevic, Marko, Jakobovic, Domagoj +2
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE)
paper · doi:10.48550/arxiv.2504.17666
This paper focuses on the problem of evolving Boolean functions of odd sizes with high nonlinearity, a property of cryptographic relevance. Despite its simple formulation, this problem turns out to be remarkably difficult. We perform a systematic evaluation by considering three solution encodings and four problem instances, analyzing how well different types of evolutionary algorithms behave in finding a maximally nonlinear Boolean function. Our results show that genetic programming generally outperforms other evolutionary algorithms, although it falls short of the best-known results achieved by ad-hoc heuristics. Interestingly, by adding local search and restricting the space to rotation symmetric Boolean functions, we show that a genetic algorithm with the bitstring encoding manages to evolve a 9-variable Boolean function with nonlinearity 241.