Automates cellulaires, fonctions booléennes et dessins combinatoires / Luca Mariot ; sous la direction de Enrico Formenti et de Alberto Leporati

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Catalogue Worldcat

Automates cellulaires

Fonctions booléennes

Cryptographie

Carrés latins

Formenti, Enrico (1968-....) (Directeur de thèse / thesis advisor)

Leporati, Alberto (19..-....) (Directeur de thèse / thesis advisor)

Carlet, Claude (Président du jury de soutenance / praeses)

Durand, Bruno (1968-.... ; informaticien) (Rapporteur de la thèse / thesis reporter)

Solé, Patrick (1960-....) (Rapporteur de la thèse / thesis reporter)

Tokareva, Natalia (19..-....) (Rapporteur de la thèse / thesis reporter)

Gadouleau, Maximilien (Membre du jury / opponent)

Université Côte d'Azur (2015-2019) (Organisme de soutenance / degree-grantor)

Università degli studi di Milano - Bicocca (Organisme de cotutelle / degree co-grantor)

École doctorale Sciences et technologies de l'information et de la communication (Sophia Antipolis, Alpes-Maritimes) (Ecole doctorale associée à la thèse / doctoral school)

Université de Nice (1965-2019) (Autre partenaire associé à la thèse / thesis associated third party)

Laboratoire Informatique, signaux et systèmes (Sophia Antipolis, Alpes-Maritimes) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Le but de cette thèse est l'étude des Automates Cellulaires (AC) dans la perspective des fonctions booléennes et des dessins combinatoires. Au-delà de son intérêt théorique, cette recherche est motivée par ses applications à la cryptographie, puisque les fonctions booléennes et les dessins combinatoires sont utilisés pour construire des générateurs de nombres pseudo aléatoires (Pseudorandom Number Generators, PRNG) et des schémas de partage de secret (Secret Sharing Schemes, SSS). Les résultats présentés dans la thèse ont été développés sur trois lignes de recherche, organisées comme suit. La première ligne porte sur l'utilisation des algorithmes d'optimisation heuristique pour chercher des fonctions booléennes ayant des bonnes propriétés cryptographiques, à utiliser comme des règles locales dans des PRNG basés sur les AC. La motivation principale est l'amélioration du générateur de Wolfram basé sur la règle 30, qui a été montré être vulnérable vis à vis de deux attaques cryptanalytiques. La deuxième ligne s'occupe des fonctions booléennes vectorielles engendrées par les règles globales des AC. La première contribution considère la période des pré-images des configurations spatialement périodiques dans les AC surjectifs, et l'analyse des propriétés cryptographiques des règles globales des AC. La troisième ligne se concentre sur les dessins combinatoires engendrés par les AC, en considérant les Carrés Latins Orthogonaux (Orthogonal Latin Squares, OLS), qui sont équivalents aux SSS. En particulier, on donne une caractérisation algébrique des OLS engendrés par les AC linéaires, et on utilise des algorithmes heuristiques pour construire des OLS basés sur des AC non linéaires.

Résumé / Abstract : The goal of this thesis is the investigation of Cellular Automata (CA) from the perspective of Boolean functions and combinatorial designs. Beside its theoretical interest, this research finds its motivation in cryptography, since Boolean functions and combinatorial designs are used to construct Pseudorandom Number Generators (PRNG) and Secret Sharing Schemes (SSS). The results presented in the thesis are developed along three research lines, organized as follows. The first line considers the use of heuristic optimization algorithms to search for Boolean functions with good cryptographic properties, to be used as local rules in CA-based PRNG. The main motivation is to improve Wolfram's generator based on rule 30, which has been shown to be vulnerable against two cryptanalytic attacks. The second line deals with vectorial Boolean functions induced by CA global rules. The first contribution considers the period of preimages of spatially periodic configurations in surjective CA, and analyze the cryptographic properties of CA global rules. The third line focuses on the combinatorial designs generated by CA, specifically considering Orthogonal Latin Squares (OLS), which are equivalent to SSS. In particular, an algebraic characterization of OLS generated by linear CA is given, and heuristic algorithms are used to build OLS based on nonlinear CA.