Highly nonlinear mappings (Q1827566)

The paper is a survey on non-Boolean functions with optimal nonlinearity. It contains generalizations of well-known classical results as well as several new results. In section 2, the authors present two important measures for the nonlinearity of a function \(f:A\to B\): (1) \(N_f=\min_{l\in L} d(f,l)\), where \(L\) denotes the set of all affine functions from \((A,+)\) to \((B,+)\) and \(d(f,g)=| \{x\in A| f(x)\neq g(x)\}| \); (2) \(P_f=\max_{0\neq a\in A}\max_{b\in B} \text{Pr}(D_af(x)=b)\), where \(D_af(x)=f(x+a)-f(x)\) and \(\text{Pr}(E)\) denotes the probability of the occurence of the event \(E\). Section 3 is devoted to functions with perfect nonlinearity. A function \(f:A\to B\) is said to have perfect nonlinearity if \(P_f=1/| B| \). A function \(g:A\to B\) is balanced if the size of \(g^{_1}(b)\) is the same for all \(b\in B\). A function has perfect nonlinearity iff \(D_af\) is balanced for every \(a\in A^*\) (Theorem 5). Further, perfect nonlinear functions are stable under actions of the general affine groups (Theorems 6, 7). In Sections 3.2 and 3.3, the authors study connections between perfect nonlinearity and difference partitions and generalized Hadamard matrices. Section 3.4 contains a characterization of perfect nonlinear functions via the Fourier transform. In Section 3.5, methods are described for obtaining functions with perfect nonlinearity from known ones. Section 3.6 is devoted to the connections of perfect nonlinear functions and bent functions. Sections 4 and 5 contain a detailed treatment of binary and nonbinary functions with optimal nonlinearity. Finally, various constructions of functions with optimum nonlinearity are described in Section 6.