Semantic Mutation Operator for Fast and Efficient Design of Bent Boolean Functions

Boolean functions are important cryptographic primitives with extensive use in cryptography, coding theory, and communications. Still, only few of the myriad possible Boolean functions possess the necessary cryptographic properties that make them fit for the purpose. The main limiting factor on the cryptographic quality of a function is the number of its input variables. Unfortunately, functions with a higher number of variables are not only more secure, but also significantly harder to find, which necessitates the development of new and more efficient ways to design them. In this paper, we focus on one specific type of cryptographic Boolean functions, known as bent functions, and propose a new semantic mutation operator for faster and more efficient heuristic search via genetic programming. The principle of the proposed operator lies in setting the mutation rates of each of the Boolean functions components dynamically, based on their current cryptographic properties, and in mutating all of the Boolean functions input variables simultaneously, to decrease the likelihood that the original and mutated Boolean function will belong to the same affine-equivalent class. To assess the efficiency of this new operator, we experiment with three distinct genetic programming variants, and compare it against the standard uniform mutation. Our results show that semantic mutation makes the evolutionary process more efficient. It scales better with the increasing number of variables, and provides up to a sevenfold decrease in both the number of fitness function evaluations and computation time.