Perfect nonlinear functions and cryptography (Q2512886): Difference between revisions

Perfect nonlinear functions \(F:G\to H\) between groups \(G\) and \(H\) are those for which \(F(x+a)-F(x)=b\) has the same number \(\lambda\) of solutions for all \(b\) and all \(a\neq 0\). They have numerous applications in finite geometry, coding theory and cryptography. There are several survey type articles dealing with such functions, see [\textit{A. Pott}, Des. Codes Cryptography 78, No. 1, 141--195 (2016; Zbl 1351.51004)] and [\textit{C. Carlet} and \textit{C. Ding}, J. Complexity 20, No. 2--3, 205--244 (2004; Zbl 1053.94011)], for instance. The survey under review focuses on the cryptographic applications. In that case, also some extensions of perfect nonlinear functions have to be considered, notably the case of almost perfect nonlinear functions: these are functions where \(G=H={\mathbb Z}_2^n\) and \(F(x+a)-F(x)=b\) has \(0\) or \(2\) solutions for all \(b\) and all \(a\neq 0\) (it is known that the number of solutions must be always an even number if \(G=H={\mathbb Z}_2^n\), hence perfect nonlinear functions cannot exist in this case). Another goal is that \(F\) is bijective, which seems to be difficult to reach if \(n\) is even and \(G=H={\mathbb Z}_2^n\) (only one example for \(n=6\) is known [\textit{K. A. Browning} et al., Contemp. Math. 518, 33--42 (2010; Zbl 1206.94026)] ). Therefore, some further extensions of perfect nonlinearity have been studied, like the discrete exponential and logarithmic functions. The authors describe very concrete applications of perfect nonlinear functions and their variations in different cryptographic schemes (IDEA, AES, CRADIC, Keccak or FIDES, to name just a few). The strength of this article is the description of the links between perfect nonlinearity real world cryptography.