A novel bio-inspired encoding for evolving cryptographic Boolean functions

Discovering Boolean functions that satisfy properties such as balancedness and nonlinearity is a complex optimization problem, which is crucial to important cryptographic constructions like block and stream ciphers. The difficulty of this problem lies in the search space growing super-exponentially in the number of variables. Evolutionary approaches, including Genetic Algorithms (GAs) and Genetic Programming (GP), have been successfully applied to overcome this difficulty. The major drawback of these methods is that they evolve functions through encodings that are either exponential in the input size or hard to interpret. We address this problem as follows. (i) We propose a new encoding for Boolean functions as reaction systems, a bio-inspired computational model which can be directly translated into the compact and easily interpretable Disjunctive Normal Form (DNF). (ii) We design EvoBRS, an evolutionary optimization framework that exploits this new representation to discover Boolean functions with maximum nonlinearity (bent functions), possibly under the balancedness constraint. (iii) We back up our novel paradigm with a refined theoretical analysis of independent interest. (iv) We conduct a rigorous experimental study, demonstrating that EvoBRS consistently discovers diverse, highly nonlinear Boolean functions with and without the balancedness constraint. EvoBRS proves particularly effective on balanced functions, successfully identifying balanced maximally nonlinear instances and outperforming both GP and state-of-the-art GAs. All the discovered functions are returned in a compact and easily interpretable DNF. A preliminary version of this work appeared in Ascone et al., GECCO 2025.

• View at Publisher