Paper 2020/1272

Bent Functions from Cellular Automata

Maximilien Gadouleau, Luca Mariot, and Stjepan Picek


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.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
bent functionscellular automataHadamard matricesLatin squaresorthogonal arrayspolynomialspartial spreads
Contact author(s)
l mariot @ tudelft nl
2020-10-14: received
Short URL
Creative Commons Attribution


      author = {Maximilien Gadouleau and Luca Mariot and Stjepan Picek},
      title = {Bent Functions from Cellular Automata},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1272},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.