# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 2 Related Works  
Applying a brute-force-based optimization method in order to identify, with respect to a certain quality criterion, the best Boolean function is inconceivable when the number of variables (\(n\)) is larger than five. On the other hand, stream ciphers usually leverage Boolean functions with \(n\) greater than 13 [14]. Therefore, designing and constructing Boolean functions that are characterized by sound security features requires more intelligent approaches than a purely random one. In the literature, this problem has been addressed by leveraging different types of strategies. Algebraic constructions, such as the Rothaus construction [15] and the McFarland construction [16], are adopted to build classes of Bent functions [17]. [PERSON] et al. [18] introduced a method to generate \(n\)-variable Boolean functions with optimal algebraic immunity and computed a lower bound of the number of Boolean functions with optimal algebraic immunity. [PERSON] et al. [19] proposed two classes of symmetric Boolean functions with optimum algebraic immunity for which both the algebraic degree and the non-linearity are also determined. [PERSON] et al. [20] presented a combinatorial conjecture about binary strings that, if correct, enables the discovers of two classes of Boolean functions with optimal algebraic immunity: Bent functions and balanced functions, with the latter having an optimal algebraic degree and the best non-linearity. Heuristic-based optimization approaches have been applied to seek good-quality Boolean functions with respect to given security objectives. [PERSON] et al. [21] optimized the non-linearity of a starting Boolean function with incremental changes. Moreover, they provided a method that discovers resilient Boolean functions by progressively concatenating valid Walsh spectra. [PERSON] et al. [13] optimized functions that intrinsically exhibit good cryptography properties and tried to transform the most-promising ones to Boolean functions that preserve the original properties. In [22], [PERSON] et al. optimized good-quality Boolean functions by using a Simulated Annealing algorithm [23]. [PERSON] et al. [24] presented a novel diversity-aware meta-heuristic for non-linearity maximization of Boolean functions that exploits a cost function that adopts the Walsh-Hadamard Transform (WHT) to gather useful information for the task at hand. Evolutionary Computation (EC) techniques serve as auspicious substitutes to more traditional optimization methods when it comes to searching for Boolean functions that possess certain security features. [PERSON] et al. [11] investigated a multi-objective evolutionary approach to discover balanced functions with similar characteristic that satisfy multiple criteria such as non-linearity. [PERSON] et al. [25] provided a survey describing the usage of evolutionary algorithms in both the symmetric and asymmetric cryptography fields. [PERSON] et al. used Genetic Algorithms (GAs) to discover balanced Boolean functions that satisfy both correlation immunity and the strict avalanche criterion [26], and they em ployed the same type of algorithm to identify Boolean functions with large non-linearity [3]. [PERSON] et al. [10] presented a GA-based scheme to build Boolean functions that satisfy balancedness, correlation immunity, algebraic degree, and non-linearity properties. [PERSON] et al. [2] adopted GA to evolve plateaued Boolean functions [27] by using the spectral inversion technique introduced in [13] and thus by representing the chromosome of an individual as a permutation of a three-valued Walsh spectrum. Morevoer, [PERSON] et al. [28] implemented a Particle Swarm Optimizer for generating Boolean functions with good cryptography properties. Particularly, this Particle Swarm Optimizer updates the particle positions while preserving their Hamming weights in a way that the generated functions remain balanced. Additionally, it exploits hill-climbing to further improve non-linearity and correlation immunity. [PERSON] et al.