In CA-1.0, each encryption subround except the first includes the application of an irreversible and a reversible cellular automaton. The irreversible rule for each subround is specified by information in the key, while the reversible rule for each subround is specified by information in the link. This section provides details on how the link information is used to specify the reversible rule during both encryption and decryption.
The reversible rules used in CA-1.0 are radius-0
rules which operate on cells
which have 
possible states. Such rules are
mearly permutations on 
objects. The problem addressed here
is that of finding a good representation for permutations.
In this context, a good representation is which one which
allows an arbitrary bit string of sufficient length to
be associated with a permutation, and such that construction
of the permutation from the bit string can be done quickly.
Probably the simplest way to represent a
permutation on N objects is as a list of images of the
integers 
. In this representation
bits are required to specify a permutation.
More compact representations capitalize on
the fact that as images for the integers are
specified in sequence, the number of remaining possible choices is
reduced, so that such choices can be specified with
fewer bits. Let 
. At the beginning, each
choice of an image under the permutation requires
n bits to specify. However, after 
images have been
specified, the remaining choices require at most n-1 bits of information. After
the first half of these have been specified, the remaining choices
require n-2 bits and so on.
Thus by taking into account the order in which the
specification of the permutation occurs, the number of
bits can be reduced to 
.
To take a concrete example, for the reversible rules used
in encryption of a block in CA-1.0, n=6,N=64. In the simple
representation 384 bits are required, while in the sequential
representation only 321 bits are required.
Further exploitation of sequential information leads to
a still more compact representation. Consider
labeling the leaves of a n-level binary tree with the
integers 
. Given an arbitrary bit string, a
permutation can be extracted from the tree which corresponds
to the bit string and uses a minimal number of bits. This
is done as follows: beginning at the root of the tree, and the
first bit in the string, a step
down is taken either to the left or right depending on whether
the bit read is 0 or 1. The process continues until a
leaf is reached, i.e. after n steps. The label of this leaf
gives the image of the integer 0 under the permutation. The
leaf is then dropped from the tree and the tree rebalanced as necessary
so that the tree stays close to a binary tree.
The process continues by reading more bits from the string to direct traversal
of the tree to find the image
of the integer 1, etc. Rebalancing after each leaf is
read can be avoided by
maintaining information at each intermediate node which
indicates whether leaves remain to be read below the node
to the left or right or both. Updating such information
can in practice be less costly than rebalancing the tree.
The total number of bits required to specify a permutation
in this way is less than or equal to the number of bits computed
for the sequential method above, and is typically significantly less
(expect log(64!)= 296 bits/permutation on average).
A simple example may help to understand this representation.
Let us find the permutation on 4 objects specified by the four bits
1110 (see figure 7).
Starting from the root, the first two 1 bits lead to the leaf labeled
3, thus 
under the permutation (figure 7 a).
The next 1 bit leads directly to the leaf label 2 in the rebalanced
tree, this yields 
(figure 7 b). The last
bit read (0) leads to the integer 0, hence 
(figure 7 c).
Finally,
by necessity.
In CA-1.0, the block permutation is specified by the bits in the link reading from left to right. The permutation is specified by the information in the raw (non-link-key encrypted) link (see subsection 3.3).
Note that one could in general construct many different permutations using the process described above and a key-scheduling algorithm. This is avoided here, however, since permutation generation from the link is necessarily sequential, and CA-1.0 is designed to maximize parallel operations.