Paper 2020/1272

Bent Functions from Cellular Automata

Maximilien Gadouleau, Luca Mariot, and Stjepan Picek

Abstract

In this work, we present a primary construction of bent functions based on cellular automata (CA). We consider the well-known characterization of bent functions in terms of Hadamard matrices and employ some recent results about mutually orthogonal Latin squares (MOLS) based on linear bipermutive CA (LBCA) to design families of Hadamard matrices of the form required for bent functions. In particular, the main question to address in this construction can be reduced to finding a large enough set of coprime polynomials over $\mathbb{F}_q$, which are used to define a set of MOLS via LBCA. This set of MOLS is, in turn, used to define a Hadamard matrix of the specific structure characterizing a bent function. We settle the existence question of such bent functions by proving that the required coprime sets exist if and only if the degree of the involved polynomials is either $1$ or $2$, and we count the resulting sets. Next, we check if the functions of $8$ variables arising from our construction are EA-equivalent to Maiorana-McFarland functions, observing that most of them are not. Finally, we show how to represent the support of these bent functions as a union of the kernels of the underlying linear CA. This allows us, in turn, to prove that the functions generated by our construction belong to the partial spread class $\mathcal{PS}^-$. In particular, we remark that for degree $1$ our construction is a particular case of the Desarguesian spread construction.