Inversion of cellular automata iterations

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. 2(n/2) trials are required for arbitrary seed values. The inversion algorithm requires at most 2((q-1)(1-alpha)n) trials for arbitrary nonlinear functions and seed values, where q is the number of variables of the updating function, and alpha 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.