Exploring Semi-bent Boolean Functions Arising from Cellular Automata
This work addresses cryptographic security by generating functions resistant to linear cryptanalysis, but it is incremental as it builds on existing cellular automata methods.
The authors tackled the problem of finding semi-bent Boolean functions for cryptographic applications by constructing them using cellular automata, resulting in an exhaustive enumeration of quadratic rules up to 6 variables that always yield semi-bent functions of up to 20 variables.
Semi-bent Boolean functions are interesting from a cryptographic standpoint, since they possess several desirable properties such as having a low and flat Walsh spectrum, which is useful to resist linear cryptanalysis. In this paper, we consider the search of semi-bent functions through a construction based on cellular automata (CA). In particular, the construction defines a Boolean function by computing the XOR of all output cells in the CA. Since the resulting Boolean functions have the same algebraic degree of the CA local rule, we devise a combinatorial algorithm to enumerate all quadratic Boolean functions. We then apply this algorithm to exhaustively explore the space of quadratic rules of up to 6 variables, selecting only those for which our CA-based construction always yields semi-bent functions of up to 20 variables. Finally, we filter the obtained rules with respect to their balancedness, and remark that the semi-bent functions generated through our construction by the remaining rules have a constant number of linear structures.