Having briefly surveyed the state of the art in dynamical systems cryptography, we now begin the main work of this paper: to engineer a cryptosystem based on cellular automata. This is done so as to best confront the ability of dynamical systems to generate complexity with the cryptanalyst's tools for cutting through such complexity. Cellular automata (CA) are discrete dynamical systems. They are also simple parallel computers. They consist of a lattice of sites and a rule which updates the state of each site according to the states of neighboring sites. All sites are updated in synchrony and according to the same local rule. CA are attractive candidates for next-generation DES-like cryptosystems since they are naturally adapted to massively parallel computation.
The approach to using CA in cryptography taken here involves application of both reversible and irreversible cellular automaton rules, and has a unique block-link structure described below.
The method of using cellular automata to build cryptosystems is flexible and powerful; it can be used to solve a wide variety of practical cryptographic problems. These applications motivate careful investigation of the security properties of such systems. A example cryptosystem has been constructed on which to focus such investigations. This system will henceforth be referred to as CA-1.0. CA-1.0 will be introduced (in section 2.2 ) after some background material on cellular automata has been covered. The name CA-1.0 is chosen to underscore the newness of the ideas involved and the expectation that further investigations will bring maturity to the system.
From a physicist's point of view, the level of detail used in the specification of this system may seem excessive, given the level of development of the underlying theory. From the cryptanalyst's point of view, however, such detail is necessary. In its present state of development, cryptanalysis operates best on fully specified devices, not on principles for building such devices. By offering up a sequence of concrete devices for cryptanalysis, one can hope for increases both in theoretical understanding, and in communication security in practice.