Cellular automata, boolean functions and combinatorial designs


The goal of this thesis is to investigate Cellular Automata (CA) from the perspective of Boolean functions and combinatorial designs. Besides the inherent theoretical interest, this research also bases its motivation in cryptography, since Boolean functions and combinatorial designs have several applications in the design of Pseudorandom Number Generators (PRNG) and Secret Sharing Schemes (SSS). The contributions presented in this thesis are developed along three main research lines, organized as follows. The first research line concerns the use of heuristic optimization algorithms for designing Boolean functions with good cryptographic properties, to be used as local rules in CA-based PRNG. The main motivation is to improve Wolfram’s pseudorandom generator, which has been shown to be vulnerable to two cryptanalytic attacks due to the poor cryptographic properties of rule $30$. In this research line, we first develop a discrete Particle Swarm Optimizer (PSO) which explores the space of truth tables of balanced Boolean functions having good nonlinearity, resiliency and propagation criteria. Next, we design a Genetic Algorithm (GA) which works on a different representation of Boolean functions, namely their Walsh spectrum. The second research line deals with vectorial Boolean functions generated by CA global rules. The first contribution investigates the period of preimages of spatially periodic configurations under the action of surjective CA, a problem which is related to the maximum number of players in a CA-based SSS already published in the literature. The second contribution analyzes the cryptographic properties of CA global rules, focusing on their algebraic degree, nonlinearity and differential uniformity. We then adopt a heuristic approach based on Genetic Programming (GP) to evolve S-boxes defined by CA with nonlinearity and differential uniformity. As a last contribution in this research line, we focus on the resiliency criterion and introduce a new cryptographic property for CA-based S-boxes, namely asynchrony immunity. The third research line deals with combinatorial designs generated by CA. We specifically focus on the case of Orthogonal Latin Squares (OLS), since they are equivalent to perfect authentication codes and threshold secret sharing schemes. To this end, our first contribution in this research line concerns the construction and the enumeration of OLS generated through linear CA, leveraging on results from the theory of finite fields. The second contribution, on the other hand, extends the investigation to OLS generated by nonlinear CA, using both a combinatorial approach for exhaustive enumeration and a heuristic approach based on GA and GP.

PhD Thesis. University of Côte d’Azur, France