# On Pseudorandomness and Deep Learning: A Case Study
## 2 Pseudorandomness  
In this section we introduce the fundamental notion of pseudorandomness. For further details and a more formal treatment, the reader can consult [10]. Pseudorandom generatorA pseudorandom generator is an efficient (deterministic) algorithm that, given short seeds, stretches them into longer output sequences, which are computationally indistinguishable from uniform ones. The term \"computationally indistinguishable\" means that no efficient algorithm, the distinguisher, can tell them apart [11; 12; 13]. Pseudorandom functionA pseudorandom function \(F:\{0,1\}^{n}\times\{0,1\}^{\ell}\to\{0,1\}^{n}\) is an efficiently computable two-input function such that, for uniform choices of \(k\in\{0,1\}^{\ell}\), the univariate function \(F_{k}:\{0,1\}^{n}\to\{0,1\}^{n}\) is computationally indistinguishable from a univariate function \(f:\{0,1\}^{n}\to\{0,1\}^{n}\), chosen uniformly at random from the set of all univariate functions of \(n\)-bit inputs to \(n\)-bit outputs. A pseudorandom _permutation_ can be defined similarly. Pseudorandom permutationA pseudorandom permutation \(P:\{0,1\}^{n}\times\{0,1\}^{\ell}\to\{0,1\}^{n}\) is a two-input permutation such that, for uniform choices of \(k\in\{0,1\}^{\ell}\), the univariate permutation \(P_{k}:\{0,1\}^{n}\to\{0,1\}^{n}\) and its inverse \(P_{k}^{-1}:\{0,1\}^{n}\to\{0,1\}^{n}\) are efficiently computable, and \(P_{k}\) is computationally indistinguishable from a univariate permutation \(p:\{0,1\}^{n}\to\{0,1\}^{n}\), chosen uniformly at random from the set of permutations on \(n\)-bit strings. Often, in practice, block ciphers are evaluated depending on how well they approximate the behavior of a pseudorandom function or permutation. Distinguishing experimentLet \(E:\{0,1\}^{n}\times\{0,1\}^{2n}\to\{0,1\}^{n}\) be a block cipher (in our case, it is Speck32 or Simon32 with block length \(n=32\) and key-size \(\ell=64\)). Let \(c=E(p,k)\) be a \(n\)-bit ciphertext. The description of the experiment in [9], Pseudo-R, defined for any distinguisher \(D\) for the block cipher \(E\), can be re-phrased as follows: \begin{tabular}{|l|} \hline Pseudo-\(R_{D,E}\) \\
1. & A bit \(b\) is chosen uniformly at random. \\  & If \(b=1\), then a key \(k\in\{0,1\}^{64}\) is chosen uniformly at random, and an oracle \(\mathcal{O}(\cdot)\) is set to reply to queries using \(E(\cdot,k)\). Otherwise, a function \(e:\{0,1\}^{32}\to\{0,1\}^{32}\) is chosen uniformly at random, from the set of all the functions of 32 bits to 32 bits, and \(\mathcal{O}(\cdot)\) is set to reply to queries using \(e(\cdot)\). \\
2. & \(D\) receives access to oracle \(\mathcal{O}(\cdot)\), and obtains replies to at most \(t\) queries. \\
3. & \(D\) outputs a bit \(b^{\prime}\). \\
4. & The output of the experiment is 1 if \(b^{\prime}=b\); otherwise, it is 0. \\ \hline \end{tabular}   
The block cipher \(E\) is said to be \((t,\epsilon)\)-pseudorandom if, for _any_ distinguisher \(D\), which runs for at most \(t\) steps, there exists a small \(\epsilon\), such that  
\[Pr[\mathsf{Pseudo}\text{-}\mathsf{R}_{D,E}=1]\leq 1/2+\epsilon. \tag{1}\]  
Roughly speaking, the block cipher is pseudorandom if any efficient distinguisher \(D\) has no better distinguishing strategy than guessing (uniformly at random). Several methods can be employed in order to set up an efficient distinguisher. For example, the distinguisher may employ differential cryptanalysis: given a plaintext pair \((P_{0},P_{1})\), with difference \(\Delta P=P_{0}\oplus P_{1}\), if the ciphertext difference \(\Delta C=C_{0}\oplus C_{1}\) is such that \(Pr(\Delta P\xrightarrow{E}\Delta C)>2^{-n}\), then \(E\) is not a pseudorandom generator. Or, it may use other algorithmic techniques to find patterns, similarities or whatever can be useful for distinguishing. We are interested in this work in ML methods. Actually, ML methods are quite general and provide flexibility in implementing cryptanalytic strategies.