Bent Functions from CA

Abstract

Bent functions represent an important class of Boolean functions, due to their applications in symmetric cryptography, error-correcting codes and combinatorial designs. In the last decades, several constructions have been proposed in the literature, either with the approach where one defines a bent function by leveraging other combinatorial structures (primary constructions), or and by starting from other existing bent functions (secondary constructions). This talk focuses on a new primary construction where Cellular Automata (CA) are used to define bent functions, by exploiting their characterization in terms of Hadamard matrices and some recent results on mutually orthogonal Latin squares generated by linear CA. In particular, we show that the existence of such functions depends on the existence of a sufficiently large number of coprime polynomials of degree 1 or 2 over a finite field.