On functions with the maximal number of bent components

Abstract

A function $F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$, $n=2m$, can have at most $2^n-2^m$ bent component functions. Trivial examples are obtained as $F(x)=(f_1(x),\dots ,f_m(x),a_1(x),\dots ,a_m(x))$, where $\tilde{F}(x)=(f_1(x),\dots ,f_m(x))$ is a vectorial bent function from ${\mathbb{F}}_2^n$ to ${\mathbb{F}}_2^m$, and $a_i$, $1\le i\le m$, are affine Boolean functions. A class of nontrivial examples is given in univariate form with the functions $F(x)=x^{2^r}\mathrm{T}{\mathrm{r}}_{\mathrm{m}}^{\mathrm{n}}(\Lambda (x))$, where $\Lambda$ is a linearized permutation of ${\mathbb{F}}_{2^m}$. In the first part of this article it is shown that plateaued functions with $2^n-2^m$ bent components can have nonlinearity at most $2^{n-1}-2^{\lfloor \frac{n+m}{2}\rfloor }$, a bound which is attained by the example $x^{2^r}\mathrm{T}{\mathrm{r}}_{\mathrm{m}}^{\mathrm{n}}(x)$, $1\le r<m$ (Pott et al. 2018). This partially solves Question 5 in Pott et al. 2018. We then analyse the functions of the form $x^{2^r}\mathrm{T}{\mathrm{r}}_{\mathrm{m}}^{\mathrm{n}}(\Lambda (x))$. We show that for odd $m$, only $x^{2^r}\mathrm{T}{\mathrm{r}}_{\mathrm{m}}^{\mathrm{n}}(x)$, $1\le r<m$, has maximal nonlinearity, whereas there are more of them for even $m$, of which we present one more infinite class explicitly. In detail, we investigate Walsh spectrum, differential spectrum and their relations for the functions $x^{2^r}\mathrm{T}{\mathrm{r}}_{\mathrm{m}}^{\mathrm{n}}(\Lambda (x))$. Our results indicate that this class contains many nontrivial EA-equivalence classes of functions with the maximal number of bent components, if $m$ is even, several with maximal possible nonlinearity.