Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption

Additive cellular automata over a finite abelian group are a wide class of cellular automata (CA) that are able to exhibit the complex behaviors of general CA and are often exploited for designing applications in different practical contexts. We provide decidable characterizations for Additive CA of the following important properties defining complex behaviors of complex systems: injectivity, surjectivity, equicontinuity, sensitivity to the initial conditions, topological transitivity, and ergodicity. Since such properties describe the main features required by real systems, the decision algorithms from our decidability results are then important tools for designing proper applications based on Additive CA. Indeed, we describe how our results can be exploited in some emblematic applications of cryptosystems, a paradigmatic and nowadays crucial applicative domain in which Additive CA are extensively used. We deal with methods for data encryption and, namely, we propose some strong modifications to the existing schemes in order to increase their security level and make attacks much harder. (c) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper provides decidable characterizations for additive cellular automata over a finite abelian group, including injectivity, surjectivity, equicontinuity, sensitivity to initial conditions, topological transitivity, and ergodicity, which are important for designing applications based on additive CA. The authors also discuss how these results can be utilized in cryptographic applications and propose modifications to existing schemes to enhance security and increase the difficulty of attacks.