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.

Lo scopo di questa tesi è studiaregli Automi Cellulari (AC) dalla prospettiva delle funzioni booleane e dei disegni combinatorici. Oltre all'intrinseco interesse teorico, questa ricerca è motivata da applicazioni alla crittografia, dato che sia le funzioni booleane che i disegni combinatorici sono utilizzati nella progettazione di generatori di numeri pseudocasuali (Pseudorandom Number Generators}, PRNG) e degli schemi di condivisione di segreti (Secret Sharing Schemes, SSS). I contributi della tesi sono stati sviluppati lungo tre linee di ricerca, di seguito descritte. La prima linea di ricerca riguarda l'utilizzo di algoritmi di ottimizzazione euristica per cercare funzioni booleane aventi buone proprietà crittografiche, da impiegare come regole locali nei PRNG basati su AC. La motivazione principale di questo studio è il miglioramento del generatore di Wolfram, che è stato dimostrato essere vulnerabile a due attacchi crittoanalitici, a causa delle cattive proprietà crittografiche della regola 30. In primo luogo, in questa linea di ricerca viene sviluppata una versione discreta di un Particle Swarm Optimizer (PSO), che esplora lo spazio delle tabelle di verità di funzioni booleane bilanciate aventi una buona combinazione di nonlinearità, ordine di resilienza e criterio di propagazione. In seguito, viene proposto un Algoritmo Genetico (Genetic Algorithm}, GA) basato su una rappresentazione differente delle funzioni booleane, in particolare il loro spettro di Walsh. La seconda linea di ricerca si occupa delle funzioni booleane vettoriali generate dalle regole globali degli AC. Il primo contributo in questa linea di ricerca considera il periodo delle preimmagini di configurazioni spazialmente periodiche sotto l'azione di un AC suriettivo, un problema che è collegato al numero di partecipanti di un SSS basato sugli AC pubblicato in letteratura. Il secondo contributo consiste nell'analisi delle proprietà crittografiche delle regole globali degli AC, con particolare riguardo al loro grado algebrico, nonlinearità e uniformità differenziale. Viene in seguito adottato un approccio euristico basato sulla Programmazione Genetica (Genetic Programming, GP) per ottimizzare le \emph{S-box} definite da AC con una buona nonlinearità e uniformità differenziale. Infine, viene considerato l'ordine di resilienza} e introdotta una nuova proprietà crittografica per le S-box generate da AC, l'immunità all'asincronia. La terza linea di ricerca riguarda i disegni combinatorici generati tramite AC. Più precisamente, viene considerato il caso dei Quadrati Latini Ortogonali} (Orthogonal Latin Squares, OLS), poiché sono equivalenti ai codici di autenticazione perfetti e agli schemi di condivisione dei segreti a soglia. Il primo contributo in questa linea di ricerca concerne la costruzione e il conteggio degli OLS generati da AC lineari, basandosi su risultati della teoria dei campi finiti. Il secondo contributo, d'altro canto, generalizza questa analisi a OLS generati da AC nonlineari, sia attraverso un metodo combinatorico per l'enumerazione esaustiva, sia tramite un approccio euristico basato su GA e GP.