# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 1 Introduction  
The importance of cryptography methods is critical in several applications that involve performing communication and exchanging messages and data. Thanks to these techniques, data exchanges are executed in a safe way even within unsafe communication channels on which, in general, malicious actors are potentially listening. Symmetric cryptography is a particular type of cryptography in which the communication is protected with encryption and decryption by means of a shared secret key that should be known only by the participants involved in the communication [1]. A typical problem in the cryptography field consists of guaranteeing the confidentiality of communication in the presence of passive attackers that can eavesdrop on the exchanged messages. To this end, symmetric ciphers can be employed to encrypt the exchanged messages so that an attacker is not able to gain information about the original messages on the basis of the encrypted ones. In this context, stream ciphers represent a particular class of symmetric ciphers for which each message is elaborated as a whole and combined with other messages by means of bit-wise operations. In many stream-cipher-based architectures, an important building block is represented by Boolean functions with a specific number \(n\) of variables. A Boolean function that exhibits high-quality cryptography properties (e.g., non-linearity and balancedness) is essential for guaranteeing high security standard for a given stream cipher. However, discovering Boolean functions with good security properties is, in practice, a complex optimization problem that has been largely studied in the literature. In particular, Evolutionary Computation (EC) methods have been shown to be promising techniques [2; 3; 4; 5; 6; 7; 8; 9]. Among the safety properties that can be used to characterize a Boolean function, non-linearity is certainly one of the most important ones. Despite the large number of research works that have investigated how to devise Boolean functions that are characterized by large non-linearity [3; 5; 7; 9; 10; 11], the optimal non-linearity, in the cases for which this value is theoretically known, has still not been reached yet (especially for real-world Boolean functions where \(n\) is large) [12]. For this reason, novel approaches to this problem are important for finding and addressing the best exploration strategy. In this setting, the evolutionary-based optimization method and the Boolean function representation are both important factors. Especially, a Boolean function can be mainly represented in three ways: with a truth table, with the algebraic normal form (ANF), or with the Walsh transform [13]. By performing different combinations of algorithms and representations, it is possible to discover new and hopefully better ways of exploring the search space. In this article, we delve into the usage of Genetic Programming (GP) in a way that we can design an algorithm that evolves Boolean functions represented by their corresponding Walsh transforms. This approach appears to be particularly promising since the Walsh transform can be easily and indirectly represented by a GP-based tree while encoding regularities among the different Walsh coefficients. Moreover, the optimization of Walsh transforms enables us to explore a different fitness landscape that may be hopefully more promising with respect to the desired objectives. We evolve symbolic trees representing Walsh transforms to maximize their non-linearity. Specifically, for each evolved Walsh transform, we retrieve the corresponding Walsh spectrum from which, through spectral inversion, we generate a pseudo-Boolean function. Given a pseudo-Boolean function, we compute the nearest Boolean one while trying to improve the balancedness of the final solution as best as possible. To this end, we exploit the \"uncertain\" inputs of the pseudo-Boolean function in which we have to non-deterministically choose the binary values that should be mapped to the target truth table.