Published January 1, 1997
| Version v1
Journal article
Open
Inversion of cellular automata iterations
Creators
Description
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.
Files
bib-ea29dd87-073e-42bd-bac3-23d6939443e8.txt
Files
(138 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:e91b222041bda0ea5089b71a73f093cf
|
138 Bytes | Preview Download |