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.

Publication
Cryptography and Communications
Sadmir Kudin
Sadmir Kudin
Young Researcher
dr. Enes Pasalic
dr. Enes Pasalic
Full Professor, Head of the center
dr. Nastja Cepak
dr. Nastja Cepak
Assistant Professor

Related