A cryptographic and coding-theoretic perspective on the global rules of cellular automata

Abstract

Cellular Automata (CA) have widely been studied to design cryptographic primitives such as stream ciphers and pseudorandom number generators, focusing in particular on the properties of the underlying local rules. On the other hand, there have been comparatively fewer works concerning the applications of CA to the design of S-boxes and block ciphers, a task that calls for a study of CA global rules in terms of vectorial boolean functions. The aim of this paper is to analyze some of the most basic cryptographic criteria of the global rules of CA. We start by observing that the algebraic degree of a CA global rule equals the degree of its local rule. Then, we characterize the Walsh spectrum of CA induced by permutive local rules, from which we derive a formula for the nonlinearity of such CA. Additionally, we prove that the 1-resiliency property of bipermutive local rules transfers to the corresponding global rules. This result leads us to consider CA global rules from a coding-theoretic point of view: in particular, we show that linear CA are equivalent to linear cyclic codes, observing that the syndrome computation process corresponds to the application of the CA global rule, while the error-correction capability of the code is related to the resiliency order of the global rule.