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:{\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}}^{\mathrm{\#}}$) 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

Assistant with PhD

dr. Enes Pasalic

Full Professor, Head of the center

dr. Nastja Cepak

Assistant Professor