Cellular automata (CA) based cryptosystem has been studied for almost three decades, yet most of previously reported researches focus on the symmetric key encryption schemes. Up to now, few CA based public key encryption scheme has been proposed. To fill the gap, in this paper, we propose a new public key encryption scheme based on layered cellular automata (LCA). Specifically, in the proposed scheme, based on the Tshaped neighborhood structure, we combine four onedimensional reversible CAs (set as the private key) to form the transition rules of a twodimension CA, where the twodimension CA is set as the corresponding public key. Based on the hardness assumption of the Decisional Dependent CA problem in LCA, we formally prove the proposed scheme is indistinguishably secure against the chosenplaintext attack (INDCPA). In addition, we also use a numeric example to demonstrate its feasibility. Finally, analysis of key space and time efficiency are also carried out along with RSA1024, and the simulation results demonstrate that our proposed scheme is more efficient.
1. Introduction
A
s the explosive growth of information and communication technology (ICT) and its wide applications today, information security has become indispensable and crucial to the success of ICT. Cryptographic technique is an essential component of any secure communication, which ensures the data confidentiality, authentication, integrity and nonrepudiation. Typical examples of cryptosystem include Data Encryption Standard (DES)
[1]
, Advanced Encryption Standard (AES)
[2]
, RSA
[3]
, and ElGamal
[4]
. Besides these typical examples, applying cellular automata (CA) techniques to design cryptosystem is also promising in cryptography. CA can be viewed as a simple model of a spatially extended decentralized system made up of a number of individual components (cells). Each individual cell lies in a specific state and will change over time depending upon the states of its local neighbors. In general, the overall structure can be viewed as a parallel processing device. However, the simple structure, when iterated several times, will produce complex patterns indicating its potential to simulate various sophisticated natural phenomena
[5]
. CA as a medium for encryption is an attractive idea in theory as most CA can be implanted on very fast hardware
[6
,
7]
, as well as owing to its inherent features like parallelism, locality, simplicity, unpredictability and homogeneity.
Since Wolfram studied the first secret key process based on CA
[8]
, many researchers have explored several possible cryptographic techniques based on the CA, and CA has become one of the important tools to design cryptographic algorithms. Several variants of CA like twodimensional and multidimensional automata with different types of neighborhood systems have been studied by Tomassini and Sipper for random number generation
[9]
, and recently by Seredinsky et al.
[10]
and Anghelescu et al.
[11]
for block encryption. In addition, the concept of Reversible cellular automata (RCA) has also been discussed by Xia et al. for multigranularity RCA data encryption
[12]
, and the Layered cellular automaton (LCA) has been studied by Ayanzadeh et al. for generating normal random numbers
[13]
.
While most of the investigations on CAbased cryptosystems have been focused on traditional secret key cryptosystems, few CAbased public key cryptosystems has been found in the literature. Guan
[14]
proposes a public key encryption algorithm used nonhomogeneous CA, and the security of this algorithm is based on the difficulty of solving a system of nonlinear polynomial equations. However, he does not give any specifications like keysize, key generation procedure and real life examples
[15]
. Kari
[16]
introduces an idea for a public key encryption based on RCA, and poses the question of how to implement the key generation algorithm. Then Clarridge and Salomaa
[17]
prove that under certain technical assumptions a marker CA has a unique inverse with a given neighborhood, and they use the result to develop a working key generation algorithm for a public key encryption based on RCA originally conceived by Kari. Zhu et al.
[18]
put forward a public key algorithm, which uses four one dimension RCA to build a Moore neighborhood twodimensional CA. The securities of these schemes are all based on the trapdoor function, which only achieves the oneway security. As a result, these schemes may not satisfy high level security requirements, i.e., secure against the chosenplaintext attacks (CPA)
[19]
. To fill this gap, in this paper, we will define a layered cellular automata (LCA) and derive a new hard Decisional DependentCA (DDCA) problem from the 2D CA reversibility problem. Then, built upon LCA, we propose a new public key encryption scheme and formally prove the proposed scheme is semantically secure against CPA, from the DDCA assumption. Specifically, the main contributions of this paper are twofold.

Firstly, we define a layered cellular automata (LCA) with a new neighborhood structure, Tshaped neighborhood. The LCA can be viewed as a highly parallel system and the encryption schemes based on LCA are more efficient than other traditional secret key cryptosystems[13]. Then we define a new hard Decisional DependentCA (DDCA) problem, which is derived from the hard 2D CA reversibility problem. Built on the LCA, we present a new efficient public key encryption (PKE) scheme that utilizes some onedimensional reversible CAs to construct the transition rules of 2D CA with Tshaped neighborhood structure, where the 1D CA is set as the private key, and the transition rules of the constructed 2D CA are set as the corresponding public key.

Secondly, we analyze the security of the PKE scheme. In particular, we apply the provable security technique to formally prove that the PKE scheme is semantically secure against the chosenplaintext attacks, relative to the Decisional DependentCA problem.
The remainder of this paper is organized as follows. In Section 2, we formalize the definition of public key encryption and the corresponding security model. In Section 3, we review the definition of CA, RCA, layered CA and a security assumption, which serve as the basis of our proposed scheme. In Section 4, we present our public key encryption scheme based on layered CA, followed by a formal security proof in Section 5. Then, we give a numerical example to demonstrate the feasibility of the proposed scheme in Section 6, and analyze its strengths in Section 7. Finally, we draw our conclusion in Section 8.
2. Definition and Security Model
 2.1 Notation
Let
N
= {1,2,3,ㆍㆍㆍ} denote the set of natural numbers, and
k
∈
N
be a security parameter. An event is said to be negligible if it happens with a probability less than the inverse of any polynomial in
k
. If
n
∈
N
, then 0
^{n}
denotes the string of
n
zeros. Let
Z_{p}
be a finite field,
p
is a large prime number, then
indicates the process of selecting
s
uniformly and at random in
Z_{p}
. If
A
is a randomized algorithm, then
y
←
A
(
x
_{1}
,
x
_{2}
, ㆍㆍㆍ) denotes the processing of
x
_{1}
,
x
_{2}
, ㆍㆍㆍ, and
y
denotes its output.
 2.2 Definition
In general, a public key encryption scheme PKE= (
Kgen, Enc, Dec
) consists of three algorithms:

The randomized key generation algorithmKgentakes a system parameterkas input, and returns a pair (pk, sk) which consists of a private keyskand a corresponding public keypk, we write

The randomized encryption algorithmEnctakes a public keypk, a random numberα, and a plaintextMas inputs and returns a ciphertextC, we write C ←Enc(pk,α,M).

The deterministic decryption algorithmDectakes the private keyskand a ciphertextCas inputs, and returns the corresponding plaintextM, we writeM←Dec(sk,C).
All algorithms should satisfy the standard consistency constraint of public key encryption, i.e., for any message
M , Dec
(
sk,C
=
Enc
(
pk,α,M
))=
M
.
 2.3 Security Model
We recall the standard notion of security of public key encryption schemes in terms of indistinguishability. Concretely, we consider the security notion of a public key encryption scheme is indistinguishable against the chosen plaintext attacks, call it the ‘INDCPA’ security model for brevity
[20]
. In INDCPA, a probabilistic polynomial timebounded adversary, given a public key, generates two equallength messages and sends to a challenger, the challenger randomly chooses one of the messages to encrypt and sends the corresponding ciphertext to the adversary. The semantic security means the adversary cannot distinguish which message was encrypted.
Definition 1: (INDCPA):
Let
k
and
t
be integers and
ε
a real number in [0,1], and
PKE
a secure public key encryption scheme with the security parameter
k
. Let
A
be an INDCPA adversary, we consider the following random experiment:
We define the success probability of
A
via
The proposed PKE scheme is said to be (
k,t,ε
)INDCPA secure, if no adversary
A
running in time
t
has a success
3. Cellular Automata and Security Assumption
 3.1 Cellular Automata (CA)
A CA is a discrete model that consists of grids of cells in which each cell can exist in a finite number of states. All cells change their states synchronously, according to a local rule that specifies the new state of each cell based on the old states of its neighbors. A CA is a dynamical system in which space and time are discrete, CAs exhibit some inherent features like parallelism, locality, simplicity, unpredictability and homogeneity, thus CAs are naturally efficient in hardware and software implementations.
A CA can be defined by a quadruple {
D,S,N,f
} with the dimension
D
, the state set
S
, the neighboring states set
N
and the transition rule
f
.

D. The existing studies of cellular automata mostly focused on onedimensional (1D) and twodimensional (2D) CA.

S. The state setSholds the set of possible states of all cells in a CA.

N. There exist various neighborhood structures, and most popular structures are 3neighborhood, Von Neumann neighborhood and Moore neighborhood, which are respectively shown inFig. 1(a), (b), and (c).
Different neighborhood structures

f . f:S→Sis transition rule (transition function).
Let
denote the state of the
ith
cell at
t
time step and
denote the state of the
ith
cell at
t
+
1
time step, the states of all cells in a CA at
t
time step
called a configuration, denoted by
S^{t}
. The state of a cell at the next time step is determined by the transition rule along with its current state and states of neighboring cells, this can be represented by the following formula:
where
r
is the neighborhood radius.
Onedimensional CA with twostate (i.e.
S
= {0, 1}) and 3neighborhood (i.e.
r
=1) called Elementary cellular automata (ECA). The state transition of the cell can be represented as follows:
There are 8 = 2
^{3}
possible configurations for a cell and its two immediate neighbors. The rule
f
defines the CA must specify the resulting state for each of these possibilities, so there are
=256 possible rules. Wolfram
[29]
proposes a scheme, to assign each rule a number from 0 to 255 which have become standard. Each possible configuration is written in order, 111, 110... 001, 000, and the resulting state for each of these configurations is written in the same order and interpreted as the binary representation of an integer, where the number is considered to be the rule number of the automaton. For example, 90 written in binary is 010110102, so rule 90 is defined by the transition rule:
Rule 90
Although the cellular automata is an infinite system, yet it should be finitedimensional in practical applications. Therefore, it is necessary to define the boundary conditions. Several types of boundary conditions can be considered, such as periodic boundary condition (
Fig. 2
(a)), a CA with periodic boundary has the extreme cells are adjacent to each other. Another one is mapped boundary condition (
Fig. 2
(b)), which can be obtained by mapping the extreme cells at the boundary, often this boundary condition can be usefully combined with another, e.g. periodic boundary condition on different boundaries. To simulate a long channel, one would use periodic boundary in horizontal direction, and mapped boundary in vertical direction. The other one is fixed boundary (
Fig. 2
(c)), can be obtained by simply prescribing a fixed value for the cells on the boundary. The periodic boundary comes closest to simulate an infinite lattice, and is therefore often used. So, in our proposed scheme, we set the periodic boundary condition for the CA, both in the private key and public key.
Different boundary conditions
 3.2 Reversible Cellular Automata (RCA)
A CA is said to be an RCA if for every current configuration of the CA there is exactly one past configuration. In other words, a CA is reversible, if and only if the transition function is reversible and hence every configuration not only has one successor, but also has one predecessor.
For example, we let
f
is the transition rule for moving forward and g is the transition rule for moving backward,
to be the current configuration of the
ith
cell and its neighbors, where
r
is the neighborhood radius. Then the successor
of the
ith
cell can be achieved by:
and the predecessor
of the
ith
cell is:
If the rule
g
is the reverse of the rule
f
, a CA moved to
n
time steps by using rule
f
, the reverse rule
g
can be applied till the same number of time steps to obtain the original configuration of the CA.
Concretely, we define four onedimensional, 4state and
radius RCAs, labeled CA
_{1}
, CA
_{2}
, CA
_{3}
and CA
_{4}
, where
CA_{i}
= (
1,S,N_{r}, f_{i}
), (1≤
i
≤ 4) ,
S
is the state set and S = {0,1,2,3},
N_{r}
is neighborhood with
radius. Set each cell takes the cell at its right position as its neighbor (
Fig. 3
), the transition rules of these CAs are shown in
Table 2
.
The neighborhood structure of the 1D RCA
These CAs are all reversible and their reverse rules are themselves. For example, we take 01132012030130032 as the initial configuration, which adopts periodic boundary and right neighborhood structure. Then use rules of CA
_{1}
evolve one time step, and for the new configuration we can return to the initial state by CA
_{1}
.
Reversible rules of four 1D 4state 1/2radius RCAs
Reversible rules of four 1D 4state 1/2radius RCAs
From the
Fig. 4
, we can see that CA
_{1}
is reversible, the reverse rule is itself and the other three can also prove to be selfreversing.
CA_{1} state transition
In addition, we can set that each RCA has a specific operational direction and each cell in 1D RCA only has one adjacent neighborhood, which is illustrated in
Fig. 5
.
Each 1D CA neighbor structure in construction algorithm
Reversible rules in order to be useful for cryptography only if they should be numerous and exhibit complex behavior. Analysis
[21]
showed that the ECA turns out that only a small number of rules have the property of being reversible. For example, among all 256 oneradius ECA transition rules, only six are reversible. For CA of two or more dimensions, it has been proved that the reversibility is undecidable for arbitrary rules
[22]
. So the twodimensional CA used for encryption has an advantage. Most of the encryption schemes based on the RCA are focused on the symmetric encryption
[23

28]
, there appears to be a very few RCAbased public key encryption schemes in the literature. In this paper, we propose a new public key encryption scheme based on RCA, which utilizes several onedimensional (1D) RCAs to construct a twodimensional (2D) CA, the 1D CA set as the private key and the 2D CA set as the corresponding public key. At the same time, we try to construct the encryption scheme based on the layered cellular automata (LCA) with a new Tshaped neighborhood structure, to achieve high level security.
 3.3 Layered Cellular Automata and Tshaped Neighborhood
A layered cellular automata (LCA) can be viewed as a highly parallel system that consists of layers and each layer consisting of rows of onedimensional CA, the number of layers can be changed according to actual situation
[13]
. This stacked structure allows the cell in it has more complex and volatile neighborhood, which may lead to analysis of a new class of CA and is much of theoretical interest. In
[28]
, an 8layer CA is used in block encryption scheme, the scheme is observed to possess better confusion and diffusion properties when compared with AES, and is more efficient than AES. A twolayer CA and Tshaped neighborhood are shown in
Fig. 6
and
Fig. 7
, respectively.
A twolayer CA
Tshaped neighbor in twolayer CA
From
Fig. 7
, we can clearly see what Tshaped neighborhood is, i.e., a cell in the first layer, its state changed based on not only its left and right neighbor, but also the cell at the same position in the next layer, so the neighbors of central cell ‘ 2 ’ is the left neighbor ‘3 ’, the right neighbor ‘ 0 ’and the ‘ 0 ’ at the next layer. This neighborhood structure joins two layers of the CA and let them become a linked system, can effectively improve the diffusion property of the encryption algorithm with Tshaped neighborhood
[23]
.
In summary, we have the reason to believe that the interaction between layers of the LCA with Tshaped neighborhood structure, in our proposed scheme, will lead to a dynamic and complex behavior and contribute to achieve better properties of confusion and diffusion.
 3.4 Security Assumption
The
Reversibility problem of CA
: Kari has proven that the reversibility of twodimensional (2D) CA is undecidable, even when restricted to CA using the Von Neumann neighborhood
[16]
. And there does not exist any algorithms that would decide on a given twodimensional transition rule whether it is reversible or not
[22]
. So it is impossible that a 2D CA retrace its computation steps backwards in polynomial time, if only known the transition rules.
That is, let
f_{ca}
:
Z_{p}
→
Z_{p}
be the transition rule of a 2D CA. For arbitrary message
m
∈
Z_{p}
, evolved by the transition rule
f_{ca}
for
k
time steps (
k
→
N
), will change to a new message
m'
, i.e.,
The reversibility problem is that if given the message
m'
and the 2D rule
f_{ca}
, we cannot get the initial message
m
.
In our proposed encryption scheme, we set
k
∈
N
as a security parameter and kept private, where the
k
is vitally important for the security of the scheme. The bigger
k
is, the more difficult the Reversibility problem of CA is. In Section 6, we will give a numerical example to discuss the influences of different
k
on the diffusion property of our proposed scheme.
Then we define two hard problems, the Computation DependentCA (CDCA) problem and the Decisional DependentCA (DDCA) problem, all based on the Reversibility problem of CA. If the Reversibility problem of CA can be solved, then we can solve the CDCA problem, later we can solve the DDCA problem. Based on these hard problems, we give a Decisional DependentCA (DDCA) Assumption, in section 5 we will formally prove our proposed scheme is INDCPA security, based on the DDCA assumption.
Definition 2. (Computation DependentCA (CDCA) problem)
Let
f_{ca}
:
Z_{p}
→
Z_{p}
be the transition rule of a 2D CA and
F_{ca}
:
Z_{p}
→
Z_{p}
, where
F_{ca}
=
k
∈
N
. Given α =
F_{ca}
(
a
) (
a
∈
Z_{p}
), i.e.,
α
=
F_{ca}
(
a
) =
α
is the result of
α
evolved by transition rule
f_{ca}
for
k
time steps. The CDCA problem is for some unknown
a
∈
Z_{p}
, computing
F_{ca}
(
a+1
) .
The CDCA assumption holds if for any probabilistic polynomial time adversary, the probability
Succ(A)
is negligible, where,
Definition 3. (Decisional DependentCA (DDCA) problem)
The DDCA problem is stated as follows: Let
f_{ca}
:
Z_{p}
→
Z_{p}
be the transition rule of a 2D CA, and
F_{ca}
:
Z_{p}
→
Z_{p}
, where
F_{ca}
=
k
→
N
. There are two distributions:
Where,
F_{ca}(a)
means arbitrary
a
∈
Z_{p}
evolved by the 2D transition rule
f_{ca}
for
k
time steps. The DDCA problem is that for given (
α, β
) ∈
Z_{p}
, deciding (
α, β
) ∈
Rand
or (
α, β
) ∈
DCA
.
The advantage of a distinguisher A denoted by
Adv(A)
and defined by:
Definition 4. (Decisional DependentCA (DDCA) Assumption)
Given
f_{ca}
:
Z_{p}
→
Z_{p}
be the transition rule of a 2D CA, let
F_{ca}
:
Z_{p}
, →
Z_{p}
,
F_{ca}
, =
k
∈
N
, and a pair (
α, β
) ∈
Z_{p}
, an adversary takes (
α, β
) as input and distinguishes (
α, β
) comes from the
Rand
or the
DCA
distribution. We consider the following random experiment on the DDCA problem.

that if existε∈ [0,1] is nonnegligible andAdv(A) ≥ε,

then returnb= 1, else returnb= 0 .
We define the corresponding success probability of
A
in solving DDCA problem via
The PKE scheme is said to be (
t, ε
)secure if no polynomial algorithm
A
running in time
t
has success Experiment
4. Proposed Scheme
In this section, we present our public key encryption scheme PKE based on the layered cellular automata with Tshaped neighborhood, which mainly consists of three algorithms, namely
Kgen, Enc
and
Dec.
Kgen.
Given a security parameter
k
∈
N
, we define four onedimension (1D) RCAs, labeled CA
_{1}
, CA
_{2}
, CA
_{3}
and CA
_{4}
, and each
CA_{i}
= (
1, S, N_{r}, f_{i}
), where
S
is the state set and
N_{r}
is the neighborhood with
r
radius (
r
∈
N
). Set each
CA_{i}
has
n
state, where (
r
∈
N
) . Set each
CA_{i}
has
n
state, where
n
∈
N
and
n
≥ 2, the state set
S
= {0,1,ㆍㆍㆍ,
n
1}. Set the transition rule
f_{i}
:
S
→
S
(1 →
i
→ 4) to be reversible. In addition, we define all 1D CAs with periodic boundary. Choose a random string
s
=
a
_{1}
a
_{2}
a
_{3}
a
_{4}
comprised by integers {1, 2, 3, 4} which defines the order of the four 1D CAs in the generate 2D rules procedure. Set the private key is
sk
= (CAa
_{1}
, CAa
_{2}
, CAa
_{3}
, CAa
_{4}
).
We set the corresponding public key is the transition rules of a 2D CA denoted by
CA
^{*}
, where
CA
^{*}
= (2,
S, N^{*} , f_{ca}
) is constructed by the 1D RCAs in the private key
sk
, so its state set is
S
. Set its transition rule
The neighborhood structure is Tshaped neighborhood, we set a number
r'
∈
N
to define the neighborhood radius of
CA
^{*}
. Define a function
F_{ca}
:
S
→
S
,
F_{ca}
=
A r' radius Tshaped neighborhood structure in plane
Construct a
r'
radius Tshaped neighborhood structure in a twodimensional plane, as shown in
Fig. 8
, and set all possible configurations. Take every configuration as the input of the transition rule
and evolved successively, the final state of the central cell set as the output. There are 3
r'
+1 inputs in the transition rule and each has
n
state.
For example, we let
denote the state of the central cell at
i
row and
j
column at t time step, and the states of the central cell and its 3
r'
neighbors constitute a configuration, this configuration as the input of the transition rules and evolved to get a new configuration, the final state of the central cell as the output of evolving procedure. This procedure can be presented as follows:
And we set the map of the states of the central cell and its neighbors to its new state, i.e.,
is a 2D transition rule. For all cells, performing this procedure to get the new states, and then get the corresponding 2D transition rules.
Set the private key
sk
= (CAa
_{1}
, CAa
_{2}
, CAa
_{3}
, CAa
_{4}
) and the corresponding public key
pk
=
f_{ca}
.
In general, the value of state number
n
is always chosen 2, 3 or 4, i.e. the state set
S
is always set as {0,1}, {0,1,2} or {0,1,2,3}, the radius of the Tshaped neighborhood structure
r'
is always chosen 1, 2 or 3. With the increase of the state number and the radius, the number of the constructed 2D transition rules will grow exponentially. The more rules in the public key, the more secure the algorithm will be. However, if the values of the state number
n
and the radius
r'
are too large, the computation complexity will increase and the efficiency of the algorithm will be greatly reduced.
Enc.
Randomly chosen a random number
α
∈
Z_{p}
, given message
M
∈
Z_{p}
and the public key
pk
=
CA
^{*}
.

For the random numberα∈Zp, because the state set of CA in the private and public key isS= {0,1, ㆍㆍㆍ,n1}, so codingαtoα', whereα'=α1α2α3ㆍㆍㆍ,αi∈S. Then arrangedα'into a layered CA, as the radius of the Tshaped neighborhood of theCA*isr', we set the layer number equal tor'+1, in this way, each cell in the layered CA can selectr'neighbors from the otherr'layers.
For example, if we set
r'
= 3, the layered CA consists of 4 layers (
Figure 9
), and the number of cells in each layer depends on the length of the plaintext.
Fig. 9
shadows the cells which are the neighbors of the central cell ‘2’ at the first layer, and the central cell has 10=3
r'
+1 neighbors.
A 4layer CA with 3radius Tshaped neighborhood

Let(l=r'+1,1 ≤i≤a, 1 ≤j≤b) denote the state of the cell at thellayer,irow andjcolumn atttime step, whereais the row number andbis the column number.

Select the neighbors of each cell according to the Tshaped neighborhood structure withr'radius, and each cell has 3r'+1 neighbors. Take the states of the neighbors as the input of the ruleFca=then compare with the input of 2D transition rules in the public key and get the corresponding output. That is,
All the outputs will comprise the ciphertext of the
α
, denoted by
F_{ca}
(
α
), and then it will be coded into
F'_{ca}
(
α
) ∈
Zp
.

Encryptα+ 1 intoF'ca(α+1) ∈Zp, then computeF'ca(α+1)+M)modp.

SetC1=F'caαmodpandC2= (F'ca(α+1)+M)modp.

Set the ciphertext ofMisC= (C1,C2) .
Dec.
Given a ciphertext
C
= (
C
_{1}
,
C
_{2}
) and the private key
sk
= (CAa
_{1}
, CAa
_{2}
, CAa
_{3}
, CAa
_{4}
).

Compute the reverse rules of the four 1D CAs in the private key, get

For givenC1, =F'caαmodp, coding it toarranged into the layered CA, then successively cyclic evolvedktimes by four 1D transition rulesthe final states of all cells made up the plaintextα'. That is,

Encodeα'toα∈Zp, and computeα+ 1 ∈Zp, then use theEncalgorithm encryptα+ 1 intoF'ca(α+1)modp.

ComputeM= (C2F'ca(α+1)modp, i.e., the plaintext ofC.
5. Security Analysis
In this section, we formally prove that the ciphertext
C
= (
C
_{1}
,
C
_{2}
) in the proposed PKE scheme is semantically secure against chosenplaintext attack under the assumption that the DDCA problem is hard.
The proposed PKE consists of three algorithms, namely
Kgen, Enc
and
Dec
. The private key is
sk
= (CAa
_{1}
, CAa
_{2}
, CAa
_{3}
, CAa
_{4}
,
k
) which consists of four 1D RCAs and a security parameter
k
, and the corresponding public key is
pk
=
CA^{*}
. The transition rule of
CA^{*}
is denoted as
f_{ca}
:
S
→
S, S
is the state set, set function
F_{ca}
:
S
→
S
,
F_{ca}
=
For arbitrary
a
∈
Z_{p}
, coding
a
to
a'
=
a_{1}a_{2}a_{3}
ㆍㆍㆍ, where
a_{i}
∈
S
. We set
F_{ca}
α
denote
a'
evolved by function
F_{ca}
, and code
F_{ca}
(
a
) to
F'_{ca}
(
a
), where
F'_{ca}
∈
Z_{p}
.
Assume that there is an adversary
A
which runs in polynomial time and has a nonnegligible advantage
ε
to break the semantic security of the ciphertext
C
= (
C
_{1}
,
C
_{2}
) in PKE scheme, then we can construct another adversary
B
which has access to
A
and achieves a nonnegligible advantage to break the DDCA problem.
First,
A
chooses two messages
m
_{0}
∈
Z_{p}
and
m
_{1}
∈
Z_{p}
, and returns them to
B
. At this moment,
B
flips a bit
b
∈ {0,1} and generates a ciphertext
C
= (
C
_{1}
,
C
_{2}
), = (
α
,
m_{b}
+
β
)
mod
p
, where (
α
,
β
) ∈
Z_{p}
. In the end,
B
sends
C
= (
C
_{1}
,
C
_{2}
) to
A
. After received
C
=
C
_{1}
,
C
_{2}
),
A
returns
B
a bit
b'
as the guess to
b
.
B
then returns 1 if
b'
=
b
, else returns 0.
On one hand, if the pair (α,β) ∈
Z_{p}
comes from the random distribution Rand , the pair
is uniformly distributed, hence independently of
b
. Then
On the other hand, when the pair (
α,β
) ∈
Z_{p}
comes from
DCA
distribution, one can remark that (
C
_{1}
,
C
_{2}
) is a valid ciphertext of
m_{b}
, following a uniform distribution among the possible ciphertexts. Then
The advantage of
B
in distinguishing the
DCA
and
Rand
distributions is
therefore greater than
ε
/2 .
Since
ε
is nonnegligible, the above result contradicts with the assumption that the DDCA problem is hard. As a result, the ciphertext
C
=
C
_{1}
,
C
_{2}
), is semantically secure under the chosenplaintext attack (INDCPA).
6. Numeric Example
In this section, we give a numeric example of our proposed encryption scheme, and discuss the selection of the security parameter
k
, which will show that our proposed scheme is correct and feasible.
Kgen.
Randomly choose the security parameter
k
= 5. We set the four onedimensional 4state 1 2 radius RCAs (i.e.
n
= 4 , the state set
S
{0,1,2,3} , the radius
r
=1/2 ), described in Section 3.2, as the private key, their reversible rules are shown in Table2. Randomly generate a string
s
= 1234 , so the private key is
sk
= (CA
_{1}
, CA
_{2}
, CA
_{3}
, CA
_{4}
).
Then we define the corresponding public key
pk
=
CA
^{*}
= (2,
S,N
^{*}
,
f_{ca}
),
CA
^{*}
is a 2D CA where the transition rule
set the radius of the Tshaped neighborhood to be one, i.e.
r'
= 1. There are (3
r'
+1)
^{n}
= 4
^{4}
= 256 possible 2D rules. We set all possible configurations
as the input of, where
∈
S
is the state of the
i
th row
j
th column cell, and the corresponding 2D transition rule can be expressed as
f_{ca}
:
There is a concrete example of the rule generation process in
Fig. 10
, and
f_{ca}
: (2031) → 3 is a 1radius 2D rule.
Table 3
shown some 2D rules generated by
Kgen
algorithm.
The process of generating a 2D rule
Part of the generated 2D rules
Part of the generated 2D rules
Enc.
Randomly select a large prime number
p
= 37591 , and a random number
α
= 30930 ∈
Z_{p}
. Given a message
M
= 29753 ∈
Z_{p}
. Because the state of the CA in the public and private key is
S
= {0,1,2,3}, so we first coding the number
α
= 30930 to
α'
= 13203102 .

Arrange theα'into a twolayer CA because of the radius of the Tshaped neighborhoodr'= 1. The structure of the twolayer CA is shown inFig. 11(a), and its second layer is shown inFig. 11(b).
Twolayer Cellular Automata

SetFca:S→S,Fca=wherefcais the transition rule of the public keyCA*. Take each cell of the twolayer CA shown inFigure 11and its neighbors as the input of the ruleFca, the all outputs make up the ciphertext ofα', that isFca(α)= 33102301. Then coding the ciphertext to decimal formF'ca(α)modp= 48382modp= 10791.

Computeα+ 1 = 30931 , coding it to (α+1)' = 13203103, encrypt it intoF'ca(α+1)modp= 17210 .

SetC1=F'ca(α+1)modp= 10791, andC2=F'ca(α+1)modp= 9372

So the ciphertext of the messageMisC= (C1,C2) = (10791,9372) .
Dec.
Given the ciphertext
C
= (
C
_{1}
,
C
_{2}
) and the private key
sk
= (CA
_{1}
, CA
_{2}
, CA
_{3}
, CA
_{4}
,
k
=5)). Because the four transition rules of 1D CA in the
sk
is selfreversible, i.e.
, so we should not compute their reverse rules.

ForC1= 10791 , change it to quanternary form 02220213 and arrange it into a twolayer CA.

Use the transition rulesf1,f2,f3,f4in sk to cyclic evolve every cell successively for 5 times. The final configuration of the twolayer CA is the plaintext ofC1, that is the random numberα.

Compute and encryptα+ 1 intoF'ca(α+1)modp= 17210.

ComputeM= (C2F'ca(α+1)modp= 29753 , that is the plaintext.
For the security parameter
k
∈
N
, we give an experiment on the difference between
F'_{ca}
(
α
) and
F'_{ca}
(
α
+1) when choosing different values. We define a parameter
δ
∈ [0,1] to denote the proportion of the
different from the
Based on the Reversibility problem of CA, only more than half bits in
are changed, i.e.
δ
≥ 1/2 , the semantic security of our proposed scheme is achieved. More detailed, the result is shown in Table 4.
The comparison ofandwith differentk
The comparison of and with different k
We can see that the bigger
k
is, the better diffusion property we can achieve, which profits to effectively prevent the adversary from solving the DDCA problem. So in the practical application, the value of
k
should be as big as possible on the premise of no obvious reduction of encryption efficiency.
7. Performance Analysis
The numeric example has shown the feasibility of the proposed encryption scheme PKE. In this section, we will exhibit its strengths by giving a comparison between the proposed PKE and the algorithm RSA.
Since the radius and state sets of the CAs used in the proposed PKE are not appointed, we can achieve different size key space by varying the radius and state number. Moreover, different key space means more or less calculations and time cost. In our proposed PKE, we set the 2D CA in
Kgen
algorithm has
n
state and Tshaped neighborhood with
r'
radius, so there may be
possible rules generated as the public key, i.e., the key space is
.
Table 5
shows the key space size and the time of generating the public key when
n
and
r'
are chosen different values and compared with RSA. It’s obviously observed from the table that the key space increases quickly as
n
and
r'
become large, and the time cost of generating the public key of the proposed PEK is less than that of RSA.
The key space and timing analysis between PKE and RSA
The key space and timing analysis between PKE and RSA
As we know that an RSA algorithm is secure if and only if the public key
n
^{*}
=
pq
is large enough to secure against factorization, where
p
and
q
are set as the private key. In general,
p
and
q
are at least chosen as 512 bits large primes so that the corresponding product
n
^{*}
will be 1024 bits. Factoring a number with this length that is far beyond the capability of existing factorization algorithms. Therefore, we consider RSA1024 to compare with the proposed PKE.
Because the key space of RSA1024 algorithm is 2
^{1024}
, as well as the plaintext space and ciphertext space, here we set
n
=2 and
r'
= 3, such that
= 2
^{1024}
. Now, we randomly choose 100 plaintexts from the plaintext space and encrypt them to get the cipehertexts, and then decrypt these ciphertexts. All the encryption and decryption are executed by the RSA1024 and our proposed PKE on an Intel Core 2 Duo 2.0 GHZ, in C
^{++}
platform. The average execution time of the 100 encryption and 100 decryption processes are calculated separately and the results are tabulated in Table 6. It is observed that the time taken by our proposed PKE is less than RSA1024, which obviously demonstrates the efficiency of our proposed scheme.
Average execution time for RSA1024 and PKE
Average execution time for RSA1024 and PKE
8. Conclusion
In this paper, we have proposed an efficient public key encryption scheme based on layered cellular automata. We use four onedimensional (1D) RCAs to construct a twodimensional (2D) CA, as the reversibility of 2D CA is undecidable, we set the transition rules of the constructed 2D CA as the public key, the 1D RCAs as the private key. And we have formally shown the proposed encryption scheme is semantically secure against chosenplaintext attacks (IINDCPA) in the standard model, based on the difficult Decisional DependentCA assumption. Moreover, the proposed scheme is developed with a numerical example, and analysis of key space and time efficiency are also carried out along with RSA1024, and the results demonstrate that proposed scheme is more efficient than RSA1024.
BIO
Xing Zhang received the B.S.degree from Xuchang University, China, in 2010. From 2010 to now, she is working her Ph.D. degree in Computer Application from Nanjing University of Science and Technology (NUST), Jiangsu, China. During the period from November 2013 to May 2014, she was also a visiting Ph.D. student at School of Electrical and Electroic Engnieering, Nanyang Technological University, Singapore. Her research interests include information security and cryptography, and the encryption scheme based on cellular automata.
Rongxing Lu received the Ph.D degree in computer science from Shanghai Jiao Tong University, Shanghai, China in 2006 and the Ph.D. degree (awarded Canada Governor General Gold Medal) in electrical and computer engineering from the University of Waterloo, Waterloo, Ontario, Canada, in 2012. Since May 2013, he has been with the School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, as an Assistant Professor. His research interests include computer, network and communication security, applied cryptography, security and privacy analysis for vehicular network, eHealthcare system, and smart grid communications. He won the IEEE Communications Society (ComSoc) Asia Pacific (AP) Outstanding Young Researcher Award in 2013.
Hong Zhang is a professor in the Department of Computer Science, Nanjing University of Science and Technology. His current interests are in the areas of theory and technology of information security, data mining and network fault diagnosis.
Chungen Xu received the M.S. degree from East China Normal University, Shanghai, China, in 1996 and the Ph.D degree from Nanjing University of Science and Technology in 2003. He is a professor in the Department of Applied Mathematics, School of Sciences, Nanjing University of Science and Technology. His current interests are in the areas of computer and network security, cryptography and coding.
Announcing the Data Encryption Standard (DES).
1999
Federal Information Processing Standards Publication 197.
Article (CrossRef Link)
Announcing the Advanced Encryption Standard (AES).
2001
Federal Information Processing Standards Publication 197.
Article (CrossRef Link)
Rivest R.
,
Shamir A.
,
Adleman. L.
1978
“A Method for Obtaining Digital Signatures and Public Key Cryptosystems,”
Communications of the ACM
21
(2)
120 
126
DOI : 10.1145/359340.359342
ElGamal T.
1985
“A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,”
IEEE Transactions on Information Theory
Article (CrossRef Link)
31
(4)
469 
472
DOI : 10.1109/TIT.1985.1057074
Gan N.
2003
“A survey on cellular automata,”
Article (CrossRef Link)
Zheng Y.
,
Imai H.
1998
“A Cellular Automaton Based Fast Oneway Hash Function Suitable for Hardware Implementation,”
Public Key Cryptography, Lecture Notes in Computer Science
Article (CrossRef Link)
Franti E.
,
Slav C.
,
Balan T.
2004
“Design of Cellular Automata Hardware for Cryptographic Application,”
in Proc. of CAS2004 Int. Semiconductor Conference, 2
Article (CrossRef Link)
463 
466
Wolfram S.
1986
“Random Sequence Generation by Cellular Automata,”
Advance in Applied Mathematics
Article (CrossRef Link)
Tomassini M.
,
Sipper M.
2000
“On the Generation of Highquality Random Numbers by Twodimensional Cellular Automata,”
IEEE Trans. On computers
Article (CrossRef Link)
49
(10)
1140 
1151
Seredynski M.
,
Bouvry P.
2004
“Block Encryption Using Reversible Cellular Automata,”
Proceedings of ACRI 2004, LNCS3305
Article (CrossRef Link)
785 
792
Anghelescu P.
,
EmilSofron S.
2007
“Block Encryption Using Hybrid Additive Cellular Automata,”
in Proc. of Seventh International Conference on Hybrid Intelligent Systems
Article (CrossRef Link)
132 
137
Xia X.
,
Li Y.
,
Xia Z.
,
Wang R.
2009
“Data Encryption Based on MultiGranularity Reversible Cellular Automata,”
in Proc. of International Conference on Computational Intelligence and Security
Article (CrossRef Link)
192 
196
Ayanzadeh R.
,
Hassani K.
,
Moghaddas Y.
,
Gheiby H.
,
Setayeshi S.
2010
“Multilayer Cellular Automata for Generating Normal Random Numbers,”
in Proc. of Numbers Proceedings of ICEE 2010
Article (CrossRef Link)
Guan P.
1987
“Cellular Automaton public key cryptosystem,”
Complex System
Article (CrossRef Link)
1
Joshi P.
,
Mukhopadhyay D.
,
RoyChow D.
2006
“Design and analysis of a robust and efficient block cipher using cellular automata,”
Proceeding of Advanced Information Networking and Applications
Article (CrossRef Link)
Kari J.
1992
“Cryptosystems based on reversible cellular automata,”
Article (CrossRef Link)
Clarridge A.
,
Salomaa K.
2009
“A cryptosystem based on the composition of reversible cellular automata,” LATA2009, LNCS5457
Article (CrossRef Link)
314 
325
Zhu B.
,
Zhu L.
2007
“Public key cryptosystem based on cellular automata,”
Journal of Nanjing University of Science and Technology
Schneier B.
1996
“Applied cryptography,”
Wiley
New York
Article (CrossRef Link)
Lu R.
,
Lin X.
,
Liang X.
,
Shen X.
2011
“An efficient and provably secure public key encryption scheme based on coding theory,”
Security and Communication Networks
Article (CrossRef Link)
1440 
1447
Das D.
,
Ray A.
2010
“A parallel encryption algorithm for block ciphers based on reversible programmable cellular automata,”
Journal of Computer Science and Engineering
Article (CrossRef Link)
82 
90
Kari J.
1994
“Reversibility and surjectivity problems of cellular automata,”
Journal of Computer and System Science
Article (CrossRef Link)
149 
182
Wu Y.
,
Hao L.
,
Chen J.
2009
“Block cipher based on Tshaped cellular automata,”
Journal on Communication
30
Seredynski M.
,
Bouvry P.
2005
“Block cipher based on reversible cellular automata,”
New Generation Computing
Article (CrossRef Link)
245 
258
Wang X.
,
Luan D.
2013
“A novel image encryption algorithm using chaos and reversible cellular automata,”
Commun Nonlinear SCI Number Simulat
Article (CrossRef Link)
Kumaravel A.
,
Meetei O.
2013
“An Application of Nonuniform Cellular Automata for Efficient Cryptography,”
Indian Journal of Science and Technology
Article (CrossRef Link)
4560 
4566
Kishore M.
,
Kanthi S.
2011
“A novel encryption system using layered cellular automata,”
Proceedings of the World Congress on Engineering 2011
Article (CrossRef Link)
Rao C.
,
Attada S.
2011
“Implementation of object oriented encryption system using layered cellular automata,”
International Journal of Engineering Science and Technology
Article (CrossRef Link)
5786 
5795
Wolfram S.
2002
“A New Kind of Science,”
Article (CrossRef Link)