Design and Analysis of Bent Functions Using M-Subspaces

In this article, we provide the first systematic analysis of bent functions <inline-formula> <tex-math notation="LaTeX">$f$ </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{2}^{n}$ </tex-math></inline-formula> in the Maiorana-McFarland class <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula> regarding the origin and cardinality of their <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula> -subspaces, i.e., vector subspaces such that for any two elements <inline-formula> <tex-math notation="LaTeX">$a,b$ </tex-math></inline-formula> from this subspace, the second-order derivative <inline-formula> <tex-math notation="LaTeX">$D_{a}D_{b}f$ </tex-math></inline-formula> is the zero function on <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{2}^{n}$ </tex-math></inline-formula>. By imposing restrictions on permutations <inline-formula> <tex-math notation="LaTeX">$\pi $ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{2}^{n/2}$ </tex-math></inline-formula>, we specify the conditions so that Maiorana-McFarland bent functions <inline-formula> <tex-math notation="LaTeX">$f(x,y)=x\cdot \pi (y) + h(y)$ </tex-math></inline-formula> admit a unique <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>-subspace of dimension <inline-formula> <tex-math notation="LaTeX">$n/2$ </tex-math></inline-formula>. On the other hand, we show that permutations <inline-formula> <tex-math notation="LaTeX">$\pi $ </tex-math></inline-formula> with linear structures give rise to Maiorana-McFarland bent functions that do not have this property. In this way, we contribute to the classification of Maiorana-McFarland bent functions, since the number of <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>-subspaces of a fixed dimension is invariant under equivalence. Additionally, we give several generic methods of specifying permutations <inline-formula> <tex-math notation="LaTeX">$\pi $ </tex-math></inline-formula> so that <inline-formula> <tex-math notation="LaTeX">$f\in \mathcal {M}$ </tex-math></inline-formula> admits a unique <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>-subspace. Most notably, using the knowledge about <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>-subspaces, we show that using the bent 4-concatenation of four suitably chosen Maiorana-McFarland bent functions on <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{2}^{n-2}$ </tex-math></inline-formula>, one can in a generic manner generate bent functions on <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{2}^{n}$ </tex-math></inline-formula> outside the completed Maiorana-McFarland class <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}^{\#}$ </tex-math></inline-formula> for any even <inline-formula> <tex-math notation="LaTeX">$n\geq 8$ </tex-math></inline-formula>. Remarkably, with our construction methods, it is possible to obtain inequivalent bent functions on <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{2}^{8}$ </tex-math></inline-formula> not stemming from the two primary classes, the partial spread class <inline-formula> <tex-math notation="LaTeX">$\mathcal {PS}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>. In this way, we contribute to a better understanding of the origin of bent functions in eight variables, since only a small fraction of about 276 bent functions stems from <inline-formula> <tex-math notation="LaTeX">$\mathcal {PS}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>, whereas their total number on <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{2}^{8}$ </tex-math></inline-formula> is approximately 2106.