Boolean Functions, S-Boxes and Evolutionary Algorithms


Boolean functions and S-boxes are a fundamental building block in the design of symmetric ciphers. Indeed, the security of several approaches such as the combiner model for stream ciphers or the substitution-permutation network for block ciphers can often be reduced to the cryptographic properties of the underlying Boolean functions and S-boxes. However, finding a Boolean function or an S-box with an appropriate trade-off of properties represents a difficult combinatorial optimization problem which is not amenable to exhaustive search, as soon as the number of variables becomes too high. In this respect, Evolutionary Algorithms (EAs) represent an interesting heuristic method to address this optimization problem. In this talk, we give a general survey of the literature concerning the use of EAs for optimizing the cryptographic properties of Boolean functions and S-boxes. Starting from the seminal works in the late 90s based on Genetic Algorithms to evolve balanced nonlinear Boolean functions, we will then show the most recent and successful approaches based on Genetic Programming, that allowed to evolve optimal S-boxes defined by cellular automata.

Room A219, Polo Ferrari, University of Trento, Italy