Inversion of cellular automata iterations
Çetin Kaya Koç, A. Murat Apohan · IEE Proceedings - Computers and Digital Techniques · 1997
An algorithm for inverting an iteration of the one-dimensional cellular automaton is presented. The algorithm is based on the linear approximation of the updating function, and requires less than exponential time for particular classes of updating functions and seed values. For example, an n-cell cellular automaton based on the updating function CA30 can be inverted in O(n) time for certain seed values, and, at most, 2n/2 trials are required for arbitrary seed values. The inversion algorithm requires at most 2(q-1)(1-α)n trials for arbitrary nonlinear functions and seed values, where q is the number of variables of the updating function, and α is the probability of agreement between the function and its best affine approximation. The inversion algorithm coupled with the method of Meier and Staffelbach becomes a powerful tool to cryptanalyse the random number generators based on one-dimensional cellular automata, showing that these random number generators provide less security than their state size would imply.