Observability and Reconstructibility of Affine Cellular Automata: Example on Random Number Reconstruction
Théo Plénet, Samira El Yacoubi, Clément Raïevsky and Laurent Lefévre
In this paper, the notions of observability and reconstructibility are defined for cellular automata. We extend the Kalman observability criterion to affine cellular automata with a time-varying output operator and apply this characterisation property to the observability and reconstructibility through mobile sensors. Then, a short and simple example is presented in order to detail the method for assessing the observability and reconstructibility of an affine cellular automata. Finally, an example where the random number stream is reconstructed from a cellular automata random number generators is considered in order to illustrate the concept of observability in the context of cybersecurity applications.
Keywords: cellular automata, observability, reconstructibility, mobile sensors, Kalman criterion, RNG attack