The work contains a research about a reversibility property of cellular automata. Using computational methods, local connection functions, that provide a property of reversibility to cellular one-dimensional and two-dimensional automata of different dimensions, were explicitly obtained. Reversibility criteria were obtained for simple cases, as well as properties for which reversibility is preserved. Authors provided several directions for theoretical analysis, such as polynomial and group model and gain several results, which could be relatively easy extended and generalized. The property of cyclicity represent interest for developing a theory, similar to theory of LFSR. Reversible cellular automata with non-linear local function contains properties of cyclicity and non-linearity, which could be interesting for cryptographic applications.
INTRODUCTION
For the first time cellular automata were mentioned by John von Neumann in the 40s of the twentieth century. In 1985 Steven Wolfram described the first stream encryption algorithm on cellular automata [1]. A classical cellular automaton is an ordered set of memory cells forming some regular n-dimensional lattice. Many theoretical studies, especially concerning the theory of dynamical systems, mostly consider infinite lattice. In practice, the most widespread cellular automata of small dimension-with one-, two- and threedimensional lattices, usually infinite. In cryptography, as shown in the review [2] – [5], onedimensional and two-dimensional finite-lattice automata, or models based on generalized cellular automata, have so far found their application. On the basis of a two-dimensional cellular automaton, a high-performance stream cipher was obtained [6].
Based on the second model, a hash function was recently obtained [7]. A reversible cellular automaton such that each of its states has only one antecedent. In a recent review [8] it is shown that the main results of studies of reversible cellular automata affect only automata with infinite lattice. For cryptographic applications, it makes no sense to consider such automata. Authors have found examples of reversible cellular automata with finite lattice, as well as proposed areas of theoretical research and obtained some results.
II.
An autonomous finite automaton (1) is called a
cellular automaton over a set with
d-dimensional lattices, which has size ,
with a radius of locality , a neighborhood local coupling
function that specifies the transition rule.
where is the set of possible States of the automaton,
is the initial state of the automaton, is the transition function.
Denote by the lattice cell of the cellular
automaton with coordinates . Denote by
this value if we need to specify its value at the
time . Each internal state of the automaton corresponds to
the filling of its lattice. It is described by an ordered set whose
components are the values of memory cells, as shown in the
formula (
coefficients from .
cellular
automaton
with
Cellular automaton is called a one-dimensional Boolean
cellular automaton (
is a set of internal states, 0 ∈ is an initial state, is a transition function.
The internal state is described by the set
The action of is to apply a local
communication function to the neighborhood of each cell of
the cellular automaton, as shown in (
Let the lattice is finite. In this case we should
understand how acts near boundaries of lattice. We consider
2 cases. In the first cells near boundary are neighbors to each
other, i.e. in the one-dimensional case, the neighbor of the
rightmost cell is the leftmost cell (shown at figure 1).
In the second case we assume that beyond the boundaries of
the finite lattice there are cells filled with zeros, and they do
not change when the cellular automata works. We call such
situations a nonzero and zero boundary, respectively. A
cellular automaton is called reversible if each of its states has
the only one preceding state such that .
Obviously this condition is equivalent to the periodicity of the
cellular automaton: for each there is such that .
For cryptography, there are two interesting questions: how to
calculate the period efficiently and how to construct automata
with maximal possible period (or almost maximal). Let a
lattice be finite and a set of cell states is . It’s easy to see
that the reversibility is guaranteed if a local communication
function of automaton is a shift. In the two-dimensional case,
the cell takes the value of its neighbor, or its inversion. That is,
a function of the form (
In the course of the program, a large number of functions were obtained that provide reversibility to automata of dimension 1 and the number of cells from 7 to 23 in the case of a function of three variables, and up to 19 for equilibrium functions of 5 variables. Among them were a large number of the aforementioned shift functions as well as linear functions. Linear functions are a fairly simple case, they provide reversibility to the automaton if and only if the matrix of the corresponding linear operator acting on the vector representing the current state of the automaton is not degenerate. In addition to linear functions as well as shift functions, 542 functions with a nonlinear local communication function were obtained. Among them, the following facts are noticed: the inversion of each function providing reversibility also provides reversibility.
The non-obvious results prompted a detailed theoretical analysis of the reversible cellular automaton as a model. The following will list the properties that hold for cellular automata.
Property 1. If is a local communication function that provides reversibility for given Boolean cellular automata then also provides reversibility.
Proof: We will use rule of contraries. For simplicity, consider the one-dimensional case ( ). Let be some state of the cellular automaton . And let the transition function translate the automaton into a state Then will translate to - state with inverted coordinates. Suppose that after applying the inverted function, the state has another predecessor . But then in the original automaton, . will be translated by into (its own inversion), and it has only one predecessor, and that is . That is, coincides with . Similarly, it is proved for large dimensions.
The following 2 properties are essentially an adaptation of the classical results from [9] to the case of a finite lattice. Property 2. A map over a vector space is a cellular automaton if and only if it commutes with a cyclic shift operator. Proof: For one-dimensional cellular automata with a nonzero boundary, there is a fact, which is also true for automata with an infinite lattice, namely, commutativity with a shift operation. That is, if is the function of the cellular automaton, and is the function of the cyclic shift vector , then . This statement is quite obvious, because when applying the cyclic shift, the content of the neighborhood of each cell will not change, and therefore its value will not change when applying the transformation of the cellular automaton. The converse is also true, if a map over a vector space commutes with a shift operator, then this map is a cellular automaton with a nonzero boundary. To do this, we show that shift invariance means the homogeneity of the transformation. Let be a boolean function showing the change of the -th coordinate of an -bit vector when the function
acts on it, depending on the value
of neighboring coordinates. Since we work with binary
vectors, we can get it explicitly by applying to each set of
neighboring coordinates (and itself). Having received a
column of values, we write the function f through Zhegalkin
polynom:
(
Property 3. For a reversible binary one-dimensional cellular automaton with a nonzero boundary, there is an inverse cellular automaton.
We write the commutativity condition with shift in terms of functions:
Theorem 1. A substitutional polynomial written using a normal basis will have coefficients from the field . By normal bases we mean such that each element of the field is represented as below:
An reversible cellular automaton is a substitution, so we write
for it a substitution polynomial in the normal basis:
Then the condition of commutativity with shift will be written
as:
(
This approach allows us to work with cellular automata as mappings over the extension field, which are also representable as polynomials. More about the properties of such a construction is written in [10].
Definition 1. Let’s determine a graph by the following rule. Let be a finite group
, and each vertex of the graph is bijectively mapped to some element of the group. Let also be fixed some subset (not necessarily subgroup), and the following property holds: the edge number leading to the vertex comes from the vertex . on the graph thus described, one can specify a cellular automaton (both homogeneous and inhomogeneous). We will call such an automaton a group automaton, and a group a carrier automaton. The connection function will take the form , and the equation describing the operation of the automaton will have the form: (15) A quasi-group automaton can be defined similarly by replacing the word "group" with "quasi-group". Recall that in a quasigroup, the associativity property is not necessarily, unlike a group. This definition can be very useful for studying the periodicity properties of the cellular automaton. In addition, the considered classical automata can be considered as automata whose carrier is a cyclic group, which naturally leads to the idea of generalizing the developed theory by transferring it to a wider class of groups (for example, finite Abelian). Reversible cellular automata are a fairly simple described transformation. They can provide the properties of nonlinearity and dispersion (the value of the cell on the next cycle affects the entire neighborhood). These properties are very useful for construction of symmetric cryptosystems. In addition, [13] and [14] show ways to construct asymmetric cryptosystems based on reversible cellular automata. The theoretical basis of cellular automata with finite lattice is not yet fully developed. Authors have taken steps in this direction. Obtained results may well serve as the beginning of the construction of a theory similar to the theory of linear feedback shift registers (LFSR).