As noted in the introduction, the use of reversible rules in cryptography has been championed by Kari[10]. Kari considers in particular public-key cryptosystems based on reversible cellular automata. In such systems security depends on the difficulty of finding the inverse cellular automaton given the forward cellular automaton. An advantage of reversible cellular automata for cryptography is that both encryption and decryption can be performed in an entirely data-parallel fashion.
CA-1.0 uses reversible rules for some phases of encryption, but for reasons rather different from those which motivate Kari's proposals. Here the reversible CA function 1) as a way to introduce full nonlinearity into the system, compensating for the partial linearity of the irreversible rules, and 2) as a way to globally broadcast the information in the link (see section 2.2.1) to the entire block and in a single iteration.
These functions can be accomplished with reversible rules which
are trivially inverted: permutations on the set of cell states.
The set of cell states for the irreversible rules is {0,1}. n-site frames
of such states are taken together to form states for the reversible
CA. The number of possible states per cell for the
reversible CA is thus
. Block encryption uses 6-site frames, while link encryption
uses 4-site frames. In CA-1.0 the block length is a multiple
of the frame size. Periodic boundary conditions are
imposed. In this way, there are several 1-1 transformation
from the block for the 2-state CA to the block for the
-state CA. These transformations are indexed by a shift in
the reading frame relative to to some fixed reference. In CA-1.0
each reversible rule is applied for several iterations. In each
iteration the reading frame shifts.
Figure 2 shows the evolution
of a configuration under a
-state reversible CA such as
used in link encryption in CA-1.0. Figure 2a shows the evolution
of an initial random block of length 256 for 256 generations
where the block is interpreted as composed of cells with 2 possible states.
Figure 2b shows the same evolution viewed as the operation of
a 16 state per cell CA.
Shades of gray are assigned to the states in a
arbitrary fashion. At each iteration the reading frame shifts by
1. For further details see section 3.2.