# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 6 Discussion  
Following, we recap the research questions presented in Section 1 and try to provide an answer to them based on the observed results:  
Figure 18: Trend of the mean uncertainty position percentage across the generations of several GP evolutions. * _Can we easily obtain balanced solutions?_ We demonstrate that by using the proposed biased uncertainty filling method, we are able through a GP evolution to discover solutions that are balanced. This is of paramount importance since unbalanced functions have a statistical bias that can be exploited by attackers. Therefore, it is essential to guarantee a high chance of building balanced solutions when using the proposed spectral inversion technique. * _Can we leverage a GP-based evolution to discover solutions with higher non-linearity than random search?_ We show that by using GP, we are able to discover better solutions than RS even if we set a small population size and a low number of generations, provided that we use a specific type of symbolic tree structure. In this case, it seems that the (scaled) non-linearity is usually larger than 0.90. This means that by employing \(\mathcal{S}_{\text{F1}}^{\text{N,ERC}}\) and \(\mathcal{S}_{\text{F1}}^{\text{N}}\) as tree structures along with GP and biased uncertainty filling, the proposed technique has the potential to identify Boolean functions characterized by a large non-linearity. Therefore, performing an exploration of the search space composed by Walsh transforms is potentially an interesting approach. As a further remark, we stress that for the numbers of bits that have been extensively studied in a way for which the optimal non-linearity has been derived [12], given the complexity of the problem, GP is still unable to reach the optimal non-linearity. * _What are the implications of changing the tree syntactical structure as regards our fitness function?_ We provide an analysis of why with certain types of symbolic representations the GP-based method is not able to perform better than random search. We find the justification of this phenomenon in the percentage of uncertain positions in the pseudo-truth tables obtained through spectral inversion. To this end, by analyzing the mean uncertainty position percentage across the executed generations, we show that when the tree structure is different from \(\mathcal{S}_{\text{F1}}^{\text{N,ERC}}\) and \(\mathcal{S}_{\text{F1}}^{\text{N}}\), the percentage of uncertain positions in the pseudo-truth tables constructed during the evolution is so high that the corresponding nearest functions are basically built at random, making the evolution ineffective and no different from a simple random search. On the other hand, when the percentage of uncertain positions is lower, then there is a portion of these pseudo-truth tables that actually take advantage of the GP evolution, leading to better solutions than random search. This article provides a comprehensive analysis of how to design and implement Boolean functions that can serve as components for safe stream ciphers. In particular, as we have already seen in Section 3.1, we only need a safe Boolean function to build a confidentiality-safe stream cipher that can be adopted in real-world applications. As a matter of fact, we can adopt a Vernam cipher with PRG so that we do not need a key that is as long as the exchanged message. This is an almost mandatory requirement as regards cipher applicability in real-world tasks. Moreover, we can employ the Combiner model as PRG to guarantee confidentiality of the communication. However, this holds true if and only if we provide to the Combiner model a Boolean function characterized by good safety features. With our proposed approach, it is indeed possible to build Boolean functions that should respect those types of features. We can run our evolutionary process, retrieve the best solution, and plug that solution into a Combiner model that is employed as PRG in a Vernam cipher.