=Paper=
{{Paper
|id=Vol-2603/short3
|storemode=property
|title=The Research of Reversible Cellular Automata with a Finite Lattice
|pdfUrl=https://ceur-ws.org/Vol-2603/short3.pdf
|volume=Vol-2603
|authors=Alexey Chilikov,Alexey Zhukov,Alexey Verkhovsky
}}
==The Research of Reversible Cellular Automata with a Finite Lattice==
https://ceur-ws.org/Vol-2603/short3.pdf
Copyright ยฉ 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
The Research of Reversible Cellular Automata with a
Finite Lattice
Alexey Chilikov, Alexey Zhukov, Alexey Verkhovsky
Information Security department
Bauman Moscow State Technical University, Moscow Institute of Physics and Technology
Moscow, Russia
chilikov@passware.com, aez_iu8@rambler.ru, alexey.verkhovsky@mail.ru
Abstract. 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 Based on the second model, a hash function was
were obtained for simple cases, as well as properties for which recently obtained [7]. A reversible cellular
reversibility is preserved. Authors provided several directions for
theoretical analysis, such as polynomial and group model and gain
automaton such that each of its states has only
several results, which could be relatively easy extended and one antecedent. In a recent review [8] it is shown
generalized. The property of cyclicity represent interest for that the main results of studies of reversible cellular
developing a theory, similar to theory of LFSR. Reversible cellular
automata with non-linear local function contains properties of
automata affect only automata with infinite lattice.
cyclicity and non-linearity, which could be interesting for
cryptographic applications. For cryptographic applications, it makes no sense to
Keywords โ cellular automata, reversible transformations, consider such automata. Authors have found
nonlinear transformations, cryptographic primitive, algebraic examples of reversible cellular automata with finite
models
lattice, as well as proposed areas of theoretical
I. INTRODUCTION research and obtained some results.
For the first time cellular automata were II. FORMAL STATEMENT OF PROBLEM
mentioned by John von Neumann in the 40s of the
twentieth century. In 1985 Steven Wolfram An autonomous finite automaton (1) is called a
described the first stream encryption algorithm on cellular automaton over a set with
cellular automata [1]. A classical cellular automaton d-dimensional lattices, which has size ,
is an ordered set of memory cells forming some with a radius of locality ๐, a neighborhood local coupling
function ๐ that specifies the transition rule.
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 three-
dimensional lattices, usually infinite. In
cryptography, as shown in the review [2] โ [5], one- where ๐ is the set of possible States of the automaton,
dimensional and two-dimensional finite-lattice is the initial state of the automaton, ๐น is the transition function.
Denote by the lattice cell of the cellular
automata, or models based on generalized cellular
automaton with coordinates . Denote by
automata, have so far found their application. On
this value if we need to specify its value at the
the basis of a two-dimensional cellular automaton, a
time ๐ก. Each internal state ๐ of the automaton corresponds to
high-performance stream cipher was obtained [6]. 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 (2)
This work was supported by Russian Scientific Foundation Grant N 17-
11-01377.
12
(2) situations a nonzero and zero boundary, respectively. A
cellular automaton is called reversible if each of its states has
Consider a one-dimensional cellular automaton with the only one preceding state such that .
coefficients from . 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
Cellular automaton is called a one-dimensional Boolean calculate the period efficiently and how to construct automata
cellular automaton (3) with a lattice of size , locality with maximal possible period (or almost maximal). Let a
radius , neighborhood and the local communication lattice be finite and a set of cell states is . Itโs easy to see
function ๐ that the reversibility is guaranteed if a local communication
function of automaton is a shift. In the two-dimensional case,
(3) the cell takes the value of its neighbor, or its inversion. That is,
a function of the form (6):
described by an autonomous finite state machine (4):
. (6)
(4)
In order to identify nontrivial local communication functions,
we wrote a program in C++. This program reveals functions
Here ๐ = is a set of internal states, ๐ 0 โ ๐ is an initial state, that provide reversibility to a cellular automaton with a given
is a transition function. number of cells by the method of brute force. The source code
and the results can be found in the repository [9].
The internal state is described by the set
The action of is to apply a local III. AUTOMATA, OBTAINED BY BRUTE FORCE
communication function to the neighborhood of each cell of
the cellular automaton, as shown in (5) In the course of the program, a large number of
functions were obtained that provide reversibility to automata
,0โค๐ฅ<๐ (5) 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
Let the lattice is finite. In this case we should
large number of the aforementioned shift functions as well as
understand how acts near boundaries of lattice. We consider linear functions. Linear functions are a fairly simple case, they
2 cases. In the first cells near boundary are neighbors to each provide reversibility to the automaton if and only if the matrix
other, i.e. in the one-dimensional case, the neighbor of the of the corresponding linear operator acting on the vector
rightmost cell is the leftmost cell (shown at figure 1). 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.
IV. THEORETICAL ANALYSIS
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
Figure 1. Identification of cells, located near with a lattice then also provides reversibility.
boundary, of a one-dimensional cellular automaton
Proof: We will use rule of contraries. For simplicity, consider
In the second case we assume that beyond the boundaries of the one-dimensional case ( ). Let be some state of the
the finite lattice there are cells filled with zeros, and they do cellular automaton . And let the
not change when the cellular automata works. We call such transition function translate the automaton into a state
13
Then will translate (8)
to - state with inverted coordinates.
Suppose that after applying the inverted function, the state
has another predecessor . But then in the original Thus, for any coordinate we have the same function depending
automaton, . will be translated by into (its own on the neighboring coordinates of the vector, which means
inversion), and it has only one predecessor, and that is . That that this map is a cellular automaton. It is worth noting that the
is, coincides with . Similarly, it is proved for large function may not be local โ it may well depend on all the
dimensions. values of all cells of the lattice. The influence of the
parameters of the local communication function on the
The following 2 properties are essentially an adaptation of the distribution of values was studied in [10].
classical results from [9] to the case of a finite lattice.
Property 3. For a reversible binary one-dimensional cellular
automaton with a nonzero boundary, there is an inverse
Property 2. A map over a vector space is a cellular automaton cellular automaton.
if and only if it commutes with a cyclic shift operator. We write the commutativity condition with shift in terms of
functions:
Proof: For one-dimensional cellular automata with a nonzero (9)
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
Applying right and left , we get:
cellular automaton, and is the function of the
cyclic shift vector , then . This (10)
statement is quite obvious, because when applying the cyclic
shift, the content of the neighborhood of each cell will not That is, the inverse map also commutes with shifts, and
change, and therefore its value will not change when applying therefore is a cellular automaton.
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 Theorem 1. A substitutional polynomial written using a
homogeneity of the transformation. Let be a boolean normal basis will have coefficients from the field .
function showing the change of the -th coordinate of an -bit
By normal bases we mean such that each element of the field
vector when the function acts on it, depending on the value
is represented as below:
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: The shift condition in this case is written as
(7)
. (11)
Since the value after the shift does not change for any such
coordinates, and the values of all neighboring cells do not An reversible cellular automaton is a substitution, so we write
change, then the function does not change during the shift. For for it a substitution polynomial in the normal basis:
example, if you shift by , the coordinate value is (8): (12)
14
Then the condition of commutativity with shift will be written V. CONCLUSION
as:
(13) Reversible cellular automata are a fairly simple described
transformation. They can provide the properties of
Combining with (14), we obtain: 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
So and . with finite lattice is not yet fully developed. Authors have
taken steps in this direction. Obtained results may well
This approach allows us to work with cellular automata as serve as the beginning of the construction of a theory
mappings over the extension field, which are also similar to the theory of linear feedback shift registers
representable as polynomials. More about the properties of (LFSR).
such a construction is written in [10].
REFERENCES
Definition 1. Letโs determine a graph by the following rule.
[1] Wolfram S. Cryptography with cellular automata // Lecture Notes in
Let be a finite group , and each vertex of the graph is Computer Science. 1986. Vol. 218. P. 429โ432.
[2] Klyucharev P. Methods of designing cryptographic hash-functions based
bijectively mapped to some element of the group. Let also be on iteration of the uniform cellular automat. Voprosy kiberbezopasnosti
[Cybersecurity issues], 2017. No 1 (19), pp. 45-50. DOI:
fixed some subset (not necessarily a 10.21681/2311-3456-2017-1-45-50.
[3] Zhukov A.E. Kletochnye avtomaty v kriptografii. Chastโ 1, Voprosy
subgroup), and the following property holds: the edge number kiberbezopasnosti [Cybersecurity issues]. 2017, No 3 (21). P. 70-76.
DOI: 10.21581/2311-3456-2017-2-70-76.
leading to the vertex comes from the vertex . on the
[4] Zhukov A.E. Kletochnye avtomaty v kriptografii. Chastโ 1, Voprosy
kiberbezopasnosti [Cybersecurity issues]. 2017, No 4 (22) โ 2017 P. 47-
graph thus described, one can specify a cellular automaton 66. DOI: 10.21681/2311-3456-2017-4-47-66
(both homogeneous and inhomogeneous). We will call such an [5] Zotov Ya. Usage of cellular automaton in symmetric-key algorithm.
Voprosy kiberbezopasnosti [Cybersecurity issues], 2015. No 3 (11) , pp.
automaton a group automaton, and a group a carrier 43-45.
[6] Suhinin B.M. Vysokoskorostnye generatory
automaton. The connection function will take the form psevdosluchajnyh posledovatelโnostej na osnove kletochnyh avtomatov,
, and the equation describing the operation of the Prikladnaya diskretnaya matematika. โ 2010. โ No2. โ S. 34โ41.
[7] Klyucharev P.G. Metod postroeniya kriptograficheskikh khesh-funktsiy
na osnove iteratsiy obobshchennogo kletochnogo avtomata, Voprosy
automaton will have the form: kiberbezopasnosti [Cybersecurity issues]. 2017. N 1 (19). P. 45-50.
[8] Kari, J.: Reversible Cellular Automata: From Fundamental Classical
Results to Recent Developments.: New Generation Computing 36, 145โ
(15) 172 (2018)
[9] Bitbucket: repository
https://bitbucket.org/KleshIvanovich/bruterca/src/master/
[10] Suhinin B.M. O vliyanii parametrov lokalโnoj funkcii svyazi na
A quasi-group automaton can be defined similarly by raspredelenie znachenij yacheek dvoichnyh kletochnyh avtomatov,
replacing the word "group" with "quasi-group". Recall that in Obedinennyj nauchnyj zhurnal. โ 2010. โ No. 8. โ S. 39โ41.
a quasigroup, the associativity property is not necessarily, [11] Hedlund, G.A.: Endomorphisms and automorphisms of the shift
unlike a group. This definition can be very useful for studying dynamical systems. Math. Syst. Theory 3(4), 320โ375 (1969)
the periodicity properties of the cellular automaton. In [12] Lidl R., Niederreiter H. (1997), Finite Fields (2nd ed.), Cambridge
addition, the considered classical automata can be considered University Press, ISBN 0-521-39231-4
as automata whose carrier is a cyclic group, which naturally [13] Puhua Guan.: Cellular Automaton Public-Key Cryptosystem. Complex
Systems 1 51- 57 (1987)
leads to the idea of generalizing the developed theory by
[14] Xing Zhang, Rongxing Lu, Hong Zhang, and Chungen Xu: A New
transferring it to a wider class of groups (for example, finite Public Key Encryption Scheme based on Layered Cellular Automata.
Abelian). KSII Transactions on internet and information systems. Vol. 8, No. 10
(2014)
15