# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 3 Cryptography Overview
### Boolean Function and Walsh Transforms  
Let \(\mathbb{B}=\{0,\ 1\}\) be a set of binary values for which zero stands for _False_ and one stands for _True_. Let \(\oplus\) be the sum operator defined over \(\mathbb{B}\), and \(\wedge\) is the product operator. Specifically, \(\oplus\) is the logical _XOR_ operator (the output bit is one if and only if the input bits are not equal), and \(\wedge\) is the logical _AND_ operator (the output bit is one if and only  
Figure 3: Architecture of the Combiner model. Figure 2: Architecture of the Vernam cipher (K = Key, EK = Expanded Key, PT = Plain-Text, and CT = Cipher-Text). if both the input bits are one). A Boolean function can be formalized as \(f:\mathbb{B}^{n}\rightarrow\mathbb{B}\). Given \(n\), \(2^{n}\) is the total number of \(n\)-bit long binary strings, and thus the set of all possible values of \(f\) has a size of \(2^{2^{n}}\). Provided that, searching for an \(f\) with a defined set of desired properties is already infeasible when \(n\) is greater than five [14]. Secure cryptography systems usually employ Boolean functions with at least 13 variables. From now on, we are going to use \(n\) to denote the number of variables of a Boolean function and \(f\) to denote a generic Boolean function. Moreover, we are going to use the terms \"binary string\" and \"binary vector\" interchangeably. We can formulate an \(f\) of \(n\) variables with: an \(\mathbf{\Omega}_{f}\in\mathbb{B}^{2^{n}}\) point holding the truth table of \(f\), a multivariate polynomial called the Algebraic Normal Form (ANF) of \(f\) (defined as the sum of products over \(\mathbb{B}\)), or a Walsh transform [13]. Particularly, let \(\mathbf{w}\cdot\mathbf{x}=\bigoplus_{i=1}^{n}\mathbf{w}_{i}\wedge\mathbf{x}_{i}\) be the dot product defined over \(\mathbb{B}^{n}\): a Walsh Transform is formulated as \(\hat{F}:\mathbb{B}^{n}\rightarrow\mathbb{R}\). More precisely:  
\[\hat{F}(\mathbf{w})=\sum_{\mathbf{x}\in\mathbb{B}^{n}}f(\mathbf{x})(-1)^{ \mathbf{w}\cdot\mathbf{x}} \tag{1}\]  
From the application of \(\hat{F}\) to all the \(\mathbf{w}\in\mathbb{B}^{n}\), we obtain the Walsh spectrum of \(f\), i.e., the vector of Walsh coefficients \(\mathbf{S}_{f}\in\mathbb{R}^{2^{n}}\). Given a generic \(\mathbf{S}_{f}\), it is possible to build \(\mathbf{\hat{\Omega}}_{f}\in\mathbb{Z}^{2^{n}}\), which is the polar-form version of the truth table of \(f\). We retrieve that from the application of the Inverse Walsh Transform \(\hat{F}^{-1}:\mathbb{B}^{n}\rightarrow\mathbb{R}\):  
\[\hat{F}^{-1}(\mathbf{x})=2^{-n}\sum_{\mathbf{w}\in\mathbb{B}^{n}}\hat{F}( \mathbf{w})(-1)^{\mathbf{w}\cdot\mathbf{x}} \tag{2}\]  
There is no guarantee that calling Equation (2) by providing a generic spectrum \(\mathbf{S}_{f}\) as input leads to a Boolean function, specifically, a truth table in polar form. Generally, Equation (2) outputs a polar-form-based pseudo-Boolean function \(\tilde{f}:\mathbb{B}^{n}\rightarrow\mathbb{R}\). Basically, the polar form is a truth table consisting only of \(-1\) (_True_) and \(1\) (_False_). For a given pseudo-Boolean function \(\tilde{f}\), there are potentially many nearest Boolean functions that can be computed starting from the pseudo-Boolean one. We are mainly interested in computing only one (\(f\)) of all the possible nearest Boolean functions in polar form of a given pseudo-Boolean function. The classical approach consists of defining \(f\) as follows:  
\[f(\mathbf{x})= \begin{cases}1&\text{if }\tilde{f}(\mathbf{x})>0\\ -1&\text{if }\tilde{f}(\mathbf{x})<0\\ -1\text{ or }1\text{ at random}&\text{if }\tilde{f}(\mathbf{x})=0\end{cases}  \tag{3}\]  
When \(\tilde{f}(\mathbf{x})=0\), we say that there is uncertainty with \(\tilde{f}\) as regards the computation of the truth value of \(\mathbf{x}\). In Equation (3), the uncertain positions are filled by adopting a random criterion (i.e., unbiased uncertainty filling). Mind that uncertain positions could also be filled by leveraging other types of strategies.