Permutations without linear structures inducing bent functions outside the completed Maiorana-McFarland class
Abstract
Recently, the construction of bent functions that belong to the so-called $\mathcal{C}$ class and are provably outside the completed Maiorana-McFarland ($\mathcal{M}$) class, introduced by Carlet almost three decades ago, has been addressed in several works. The main method for proving the class membership is based on a sufficient (but not necessary) condition that component functions of the permutation $\pi$ that defines a bent function of the form $f(x,y)=\pi(y)\cdot x+\mathbf{1}_{L^{\perp}}(x)$, where $x,y\in \mathbb{F}_2^n$, (for a suitably chosen subspace $L$), do not admit non-trivial linear structures. The problem of finding such permutations and corresponding subspaces such that the pair additionally satisfies the so-called (C) property ($\pi^{-1}(a + L)$ is a flat for any $a\in \mathbb{F}_2^n$) appears to be a difficult task. In this article, we provide a generic method for specifying such permutations which is based on a suitable space decomposition introduced by Baum and Neuwirth in the 1970’s. In contrast to this result, which gives many families of bent functions outside the completed $\mathcal{M}$ class, we also show that one cannot have the (C) property satisfied for permutations whose component functions are without linear structures, when the dimension of corresponding subspace $L$ is relatively large. Furthermore, a class of vectorial bent functions $F\colon \mathbb{F}_2^{2n}\to \mathbb{F}_2^m$ such that every component function of $F$ is outside the completed $\mathcal{M}$ class (i.e. $F$ is strongly outside $\mathcal{M}^{\#}$) is specified. The problem of increasing the output dimension $m$ and especially specifying such functions with $m = n$ seems to be difficult.
dr. Sadmir Kudin
Teaching Assistant
dr. Enes Pasalic
Full Professor, Head of the center
