# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 3 Cryptography Overview
### PRG-Based Stream Cipher Design  
In the context of symmetric cryptography (Figure 1), we are interested in making the interaction safe despite the eventual presence of eavesdroppers--i.e., our security requirement matches the confidentiality of the communication. This means that without having the secret key, it is computationally infeasible to retrieve the original content of an encrypted message or a single component of it. In this scenario, we assume an unsafe communication channel in which there is a passive attacker, i.e., a malicious actor that can retrieve the encrypted message and process it but, at the same time, cannot alter the communication itself [1]. We focus our attention on stream ciphers, which are symmetric ciphers for which a message is treated as a single block. A One-Time Pad (OTP) is an example of a stream cipher that satisfies [PERSON]'s perfect secrecy definition, which states that an encrypted message must reveal no information about any bit of the corresponding plain-text message [39]. Given a plain-text message and a shared secret key, the encryption is performed by applying a bit-wise _XOR_ operator between the plain-text message and a shared secret key. Similarly, the decryption is performed by applying the same operation between the encrypted message and the secret key. This implies that the secret key length must be as long as the length of the exchanged messages. Furthermore, in order to keep the OTP safe, the same secret key must not be reused across different message exchanges. The aforementioned requirements pose practical limitations to the adoption of the OTP in real-world scenarios. To this end, a Pseudo Random Generator (PRG) can be employed to adapt the OTP construction when the length of the secret key is smaller than the length of the message. Specifically, a PRG is a public, deterministic, and efficient algorithm that, given a binary string called the \"seed\", is able to generate a much longer, seemingly random binary string [40; 41]. By adopting a PRG, it is possible to build the Vernam stream cipher [42] (Figure 2), which basically consists of an OTP for which the secret key is expanded by a PRG to match the length of the message. A Vernam stream cipher is considered to be confidentially safe if and only if the PRG is safe, i.e., unpredictable. To this end, several PRG architectures have been implemented. Figure 1: A typical scenario of symmetric cryptography. The Linear Feedback Shift Register (LSFR) [43] is an example of a construction that can be adopted within a PRG architecture. This registry essentially outputs a single bit at every clock cycle starting from a given seed (a binary string). For instance, given a state represented by the current seed stored in the registry, at every clock cycle, the most-significant bit is returned as output; then, the registry performs a left-shift operation, and the least-significant bit is populated with bit-wise _XOR_ operations performed on a subset of the seed. This way, if the registry works for \(t\) clock cycles, it will generate a \(t\)-bit long binary string. The Content Scramble System (CSS) [44] is an example of an unsafe stream cipher that leverages LSFR. This statement highlights the fact that LSFR alone does not suffice to build secure stream ciphers. A potentially unpredictable PRG can be constructed by using a combination of \(n\) LSFRs and an \(n\)-variable Boolean function. This architecture is called the Combiner model [14] (Figure 3). The seed is an \(s\)-bit long binary string. It is processed in parallel by \(n\) LSFRs, which consequentially output an \(n\)-bit long binary string at each clock cycle (one bit for each LSFR). An \(n\)-variable Boolean function \(f\) is thus applied to this binary string, and a single bit is generated. Hence, if the Combiner model works for \(d\) clock cycles, it will generate a \(d\)-bit long binary string.