Abstract
Boolean functions are essential building blocks in the design of secure stream ciphers. Finding cryptographically strong Boolean functions is, however, a notoriously difficult optimization problem, owing to the size of the search space and the combinatorial nature of the task. Evolutionary Algorithms (EAs) have proven effective at constructing Boolean functions that are simultaneously balanced and highly nonlinear, two properties that are crucial for resisting correlation and statistical attacks. Nevertheless, these and other heuristic approaches often converge prematurely to local optima because of the complexity of the fitness landscape. Cellular Automata (CA) have been used extensively to represent and analyze Boolean functions, and spatially structured populations arranged on cellular toroidal grids have been shown, in other evolutionary paradigms, to slow the propagation of dominant individuals and to encourage broader exploration. The two ideas have not been brought together: cellular population structures have not previously been used to guide the search for balanced, nonlinear Boolean functions. We therefore investigate the integration of cellular population structures into Genetic Algorithms (GAs) for evolving balanced truth tables with high nonlinearity. We evolve Boolean functions of 8 to 16 variables and compare different neighborhood radii of the cellular grid. Our results show that, for larger numbers of variables, small neighborhoods improve the nonlinearity of the evolved functions relative to a non-spatial GA, and that this improvement is statistically significant. We emphasize that the contribution of this work is an analysis of the search and diversity dynamics induced by the cellular structure: the nonlinearity values obtained remain below the best-known values for balanced Boolean functions, and the study is not intended as a step forward in the construction of cryptographically deployable functions.