A new construction for bent functions based on cellular automata, Latin squares and linear recurring sequences


Bent functions are a class of Boolean functions with many interesting applications for the design of symmetric ciphers, since they reach the highest possible nonlinearity. The literature features 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. In this talk, instead, we 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.

Lecture Room Mercator 1, Radboud University