Behind the scenes of a new construction for bent functions: a tour among cellular automata, Latin squares and linear recurring sequences


Bent functions are a particular class of Boolean functions reaching the highest possible nonlinearity; as such, they have many interesting applications for the design of symmetric ciphers, as well as for error-correcting codes and sequences. Despite their simple definition, a complete characterization of bent functions is still far out of reach, even after more than four decades of research on the topic. In particular, the related literature sports a multitude of different constructions, and nowadays introducing a new one requires careful examination of the functions it generates, to assess whether they are equivalent to previously known classes. This talk is about one such new construction of bent functions, recently published in the journal Designs, Codes and Cryptography. The paper describes the construction in terms of subspaces generated by linear recurring sequences, which form a partial spread. The aim of this talk is, instead, to give a ``behind the scenes” story that shows how we arrived to this simple description. We illustrate the original idea of using a construction of Mutually Orthogonal Latin Squares (MOLS) based on Cellular Automata (CA) to define a Hadamard matrix with the structure associated to a bent function. Next, we explain the connection with linear recurring sequences and partial spreads. We conclude with some encouraging results on the ranks distribution of the bent functions produced by our construction, which indicate that many of them are neither in the Maiorana-McFarland class nor in the Desarguesian partial spread.

Seminar Room -1, Povo 0, University of Trento, Italy