INVERSION OF CELLULAR-AUTOMATA ITERATIONS

An algorithm for inverting an iteration of the one-dimensional cellula r automaton is presented. The algorithm is based on the linear approxi mation of the updating function, and requires less than exponential ti me for particular classes of updating functions and seed values. For e xample, an n-cell cellular automaton based on the updating function CA 30 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 a lgorithm requires at most 2((q-1)(1-alpha)n) trials for arbitrary nonl inear functions and seed values, where q is the number of variables of the updating function, and alpha is the probability of agreement betw een the function and its best affine approximation. The inversion algo rithm coupled with the method of Meier and Staffelbach becomes a power ful tool to cryptanalyse the random number generators based on one-dim ensional cellular automata, showing that these random number generator s provide less security than their state size would imply.