Cryptography by Cellular Automata

Abstract

Cellular Automata (CA) have been studied for a long time as a possible way to implement cryptographic primitives. Indeed, CA are interesting for cryptography for two reasons: first, the complexity emerging from the dynamical behavior of certain CA can be used to design cryptosystems satisfying strong security properties. Second, being a massively parallel computational model, CA are especially interesting for implementing efficient cryptographic algorithms in hardware. Nowadays, there are some well known block ciphers who include in their design transformations based on CA. This is the case of the $\chi$ nonlinear transformation used in the KECCAK sponge construction, which won the SHA-3 competition for the NIST cryptographic hash function standard. In this talk, I will present the research carried out during my PhD about the applications of CA to cryptography. In particular, I will address two main topics. The first one concerns the analysis of the cryptographic properties of CA, viewed as a particular type of Boolean functions. There, I will present some theoretical bounds on the properties achievable by CA, as well as some experimental results on evolving CA rules by means of Evolutionary Computation (EC) techniques. The second topic of the talk is about the design of Secret Sharing Schemes (SSS) based on CA. In this case, I will present a theoretical characterization of CA-based SSS in terms of orthogonal Latin squares (OLS), and also how to evolve such OLS through EC techniques.