Main Text

This abstract discusses a stream cipher based on a simple one-dimensional cellular automaton. The cellular automaton consists of a circular register with cells, each having a value equal to 0 or 1. The values are updated synchronously in discrete time steps according to the rule

or, equivalently,

The initial state of the register is used as a seed or key. The values attained by a particular cell through time can then serve as a random sequence. Ciphertext can be obtained from binary plaintext as usual according to ; the plaintext can be recovered by repeating the same operation, but only if the sequence is known.

Cellular automata such as (1) have been investigated in studies of the origins of randomness in physical systems [2]. They are related to non-linear feedback shift registers, but have slightly different boundary conditions.

Figure 1 shows the pattern of cell values produced by (1) with a seed consisting of a single nonzero cell in a large register. The time sequence of values of the centre cell shows no statistical regularities under the tests of ref. [3] (for sequence lengths up to ). Some definite spacetime patterns are nevertheless produced by the cellular automaton rule.

In the limit , the cellular automaton evolution is like an iterated continuous mapping of the Cantor set, and can be studied using dynamical systems theory [4]. One result is that the evolution is unstable with respect to small perturbations in the initial seed. A change produced by reversing a single cell value typically expands at a rate given by Lyapunov exponents, equal to 0.25 on the left, and 1 on the right. Length time sequences of cell values are found however to be affected on average only by about initial values.

[ Figure 1 ] Pattern produced by evolution according to the cellular automaton of eqn. (1) from a simple seed containing a single nonzero bit. 250 successive states of an arbitrarily large register are shown; black squares represent nonzero cells. Columns of cell values, say in the centre, seem random for practical purposes.

Iterations of the cellular automaton rule (1) can be considered as Boolean functions of initial cell values. Disjunctive normal forms (minimized using [5]) for these functions are found to increase in size roughly as , giving some indication of the complexity of the cellular automaton evolution.

Figure 2 shows the complete state transition diagram for the cellular automaton (1) in a register of size . For large , an overwhelming fraction of states lie on the longest cycle. But there are also shorter cycles, often corresponding to states with special symmetries. Figure 3 shows the length of the longest cycle as a function of . The results (up to , which gives cycle length 40114679273) fit approximately . The mapping (1) is not a bijection, but is almost so; only a fraction of states do not have unique predecessors [6] ( is the real root of ).

The security of a cryptographic system based on (1) relies on the difficulty of finding the seed from a time sequence of cell values. This problem is in the class NP. No systematic algorithm for its solution is currently known that takes a time less than exponential in . No statistical regularities have been found in sequences shorter than the cycle length.

One approach to the problem of finding the seed [6] uses the near linearity of the rule (1). Equation (1) can be written in the alternative form . Given the values of cells in two adjacent columns, this allows the values of all cells in a triangle to the left to be reconstructed. But the sequence provided gives only one column. Values in the other column can be guessed, and then determined from the consistency of Boolean equations for the seed. But in disjunctive normal form the number of terms in these equations increases linearly with , presumably making their solution take a time more than polynomial in .

[ Figure 2 ] Complete state transition diagram for the cellular automaton of eqn. (1) in a circular register of size . There are states, each represented by dots. Evolution from any state leads eventually to one of the cycles shown.

The cellular automaton (1) can be implemented efficiently on an integrated circuit; it requires less than ten gate delay times to generate each output bit, and can thus potentially be used in a variety of high-bandwidth cryptographic applications.

[ Figure 3 ] Length of the longest cycle as a function of register size .

Much of the work summarized here was done while I was consulting at Thinking Machines Corporation (Cambridge, MA). I am grateful for discussions with many people, including Persi Diaconis, Carl Feynman, Richard Feynman, Shafi Goldwasser, Erica Jen and John Milnor.

next