# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 7 Conclusions  
In this article, we introduce an evolutionary-based approach that discovers potentially balanced Boolean functions characterized by good non-linearity by performing an exploration of the search space composed by Walsh transforms, i.e., particular Boolean function representations. In our method, a Walsh transform is a symbolic formula with a given functions set and terminal set that can be evolved by leveraging GP. In addition, we present and analyze an effective balancedness-preserving strategy that enables us to obtain balanced Boolean functions when computing the nearest Boolean functions starting from the corresponding pseudo-Boolean ones.  
In our experimental phase, we study and implement different types of Walsh-transform-based representations by using different combinations of the function set and the terminal set. We test these representations by performing several GP runs and RS runs. We perform a rigorous comparison between GP and RS and try to figure out whether the space determined by evolving Walsh transforms with GP represents an encouraging strategy for the purpose of devising Boolean functions that can build confidentiality-safe stream ciphers. For this particular problem, the results show that the convergence is faster for GP than the baseline based on RS, and this is evident even with a small population size with a low number of generations, making the proposed approach a promising one that deserves further research effort. However, we demonstrate that this result is possible only if a specific type of combination of function set and terminal set is adopted.  
To this end, we provide a comprehensive analysis regarding the uncertain positions of the pseudo-Boolean functions that are built with spectral inversion. We show that for the majority of the tree syntactical structures, the percentage of uncertain positions is so high that the corresponding Boolean functions are basically constructed completely at random, making the whole evolution useless. On the other hand, we show that if the proper function set and terminal set are selected, then the percentage of uncertain positions is low enough to make the evolution be beneficial for the maximization of the non-linearity and the selection of better solutions as generations are executed.  
This leads to possible future work in which larger populations can be adopted to seek higher non-linearity values, and a comprehensive benchmark of these types of evolutionary methods for Boolean function optimization can be formalized to help point out the best exploration strategy. This way, it should be possible to check the effectiveness of these techniques when a larger search space is explored. The goal in this case would consist of figuring out whether a higher and unknown non-linearity can be discovered. Finally, a strict comparison among these methods may help to highlight the technique that has the fastest convergence and the exploration strategy that appears to be the most promising for the task of maximizing the non-linearity of Boolean functions.  
**Author Contributions:** Conceptualization, L.M.; methodology, L.M. and L.R.; software, L.R.; validation, A.D.L., L.M. and L.R.; formal analysis, A.D.L. and L.R.; investigation, L.R.; resources, A.D.L. and L.M.; data curation, L.R.; writing--original draft preparation, A.D.L., L.M. and L.R.; writing--review and editing, A.D.L., L.M. and L.R.; visualization, A.D.L. and L.R.; supervision, A.D.L. and L.M.; project administration, A.D.L. and L.M.; funding acquisition, A.D.L. All authors have read and agreed to the published version of the manuscript.  
**Funding:** This research received no external funding.  
**Data Availability Statement:** Code and data can be found in our repository, available through a hyperlink at the beginning of the experimental phase section.  
**Conflicts of Interest:** The authors declare no conflicts of interest.