Nonlinearity of bent functions over finite fields

V. G. Ryabov

Matematičeskie voprosy kriptografii, Tome 12 (2021), pp. 87-98

Résumé

A function of $n$ variables over a field of $q$ elements is called maximally nonlinear if it has the greatest nonlinearity among all $q$-valued functions of $n$ variables. It is proved that for $q>2$ and even values of $n$, a necessary condition for the maximum nonlinearity of a function is the absence of a linear manifold of dimension not smaller than $n/2$, on which its restriction coincides with the restriction of some affine function. It follows from this that the bent functions from Maiorana–McFarland and Dillon families are not maximally nonlinear. A new family of maximally nonlinear bent functions of degrees from $2$ to $\max \{2, (q-1)(n/2-1)\}$ with nonlinearity equal to $(q-1)q^{n-1} - q^{n/2-1}$ is constructed.