# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 2 Related Works
[29] applied GA with the integration of a process based on hybrid local search for determining Boolean functions composed of good characteristics of auto-correlation and also non-linearity. [PERSON] et al. [30] proposed a hill-climbing method that incorporates a GA to search for highly non-linear Boolean functions. [PERSON] et al. [4] presented an empirical study on how to adopt Cartesian Genetic Programming (CGP), i.e., a variant of Genetic Programming (GP) [31], to spot general-purpose Boolean functions. [PERSON] et al. [5] resumed the work of [PERSON] et al. [4] and investigated how much more effective CGP is than GP when it comes to learning highly non-linear Boolean functions. They further investigated GA and GP with different mutation operators and initialization procedures [32]. CGP was also investigated by [PERSON] et al. [33] to routinely build Bent functions with up to 16 variables. [PERSON] et al. [34] implemented a parallelized version of Linear GP to discover Bent functions instead of using CGP, and they focused their research work on learning functions that are as large as possible. Moreover, they proposed a comparative study wherein GP, Linear GP, and CGP are compared with respect to the task of building Boolean functions with an even number of inputs and that can exhibit high-quality non-linearity, algebraic degree, balancedness, and correlation immunity [35]. [PERSON] et al. [6] highlighted that among evolutionary algorithms, GP exhibits high qualitative performance when it comes to discovering both Boolean functions that provide non-linearity in filter and combiner generators and Boolean functions with sound correlation immunity and a Hamming weight that is as small as possible. Moreover, [PERSON] et al. [36] analyzed the landscape of results obtained by integrating algebraic and EC-based approaches for searching for secure Boolean functions. [PERSON] et al. [37] also explored a method that tries to combine evolutionary algorithms with known algebraic constructions. Specifically, they analyzed a recent generalization of the Hidden Weight Boolean Function construction, and they showed that evolutionary algorithms can meaningfully improve the cryptography properties of functions based on this construction. [PERSON] et al. [8] proposed several evolutionary algorithms to evolve Hyper-Bent functions, which provide better security towards approximation attacks. They showed that these specific types of functions are extremely difficult to evolve because of their rarity and complexity. Moreover, they [7] applied GA and GP to evolve Boolean functions that satisfy the perfect balancedness property. Specifically, they used these evolutionary techniques to evolve two different types of solution encodings: the truth table and weight-wise balanced representations. [PERSON] et al. [9] tried to evolve Boolean constructions by leveraging GP to build balanced functions with high non-linearity. Finally, [PERSON] et al. [38] proposed a work in which they represented Boolean functions by using Walsh-transform-based representations, and they evolved these representations with GP to discover non-linear functions with good balancedness properties. We introduce an algorithm based on GP with which we evolve Boolean functions represented by their corresponding Walsh transforms in order to maximize non-linearity and preserve balancedness as best as possible. Specifically, we resume the work in [38] and provide an in-depth experimental analysis of various types of symbolic Walsh-transform-based representations.