Advanced
A New Public Key Encryption Scheme based on Layered Cellular Automata
A New Public Key Encryption Scheme based on Layered Cellular Automata
KSII Transactions on Internet and Information Systems (TIIS). 2014. Oct, 8(10): 3572-3590
Copyright © 2014, Korean Society For Internet Information
  • Received : February 24, 2014
  • Accepted : September 10, 2014
  • Published : October 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Xing Zhang
School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore
Rongxing Lu
School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore
Hong Zhang
School of Computer Sciences and Engineering, Nanjing University of Science & Technology, Nanjing, China
Chungen Xu
School of Science, Nanjing University of Science & Technology, Nanjing, China

Abstract
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 T-shaped neighborhood structure, we combine four one-dimensional reversible CAs (set as the private key) to form the transition rules of a two-dimension CA, where the two-dimension 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 chosen-plaintext attack (IND-CPA). 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 RSA-1024, and the simulation results demonstrate that our proposed scheme is more efficient.
Keywords
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 non-repudiation. 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 two-dimensional and multi-dimensional 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 multi-granularity 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 CA-based cryptosystems have been focused on traditional secret key cryptosystems, few CA-based public key cryptosystems has been found in the literature. Guan [14] proposes a public key encryption algorithm used non-homogeneous 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 key-size, 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 two-dimensional CA. The securities of these schemes are all based on the trapdoor function, which only achieves the one-way security. As a result, these schemes may not satisfy high level security requirements, i.e., secure against the chosen-plaintext attacks (CPA) [19] . To fill this gap, in this paper, we will define a layered cellular automata (LCA) and derive a new hard Decisional Dependent-CA (D-DCA) 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 D-DCA assumption. Specifically, the main contributions of this paper are two-fold.
  • Firstly, we define a layered cellular automata (LCA) with a new neighborhood structure, T-shaped 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 Dependent-CA (D-DCA) 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 one-dimensional reversible CAs to construct the transition rules of 2D CA with T-shaped 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 chosen-plaintext attacks, relative to the Decisional Dependent-CA 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 Zp be a finite field, p is a large prime number, then
PPT Slide
Lager Image
indicates the process of selecting s uniformly and at random in Zp . 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 ‘IND-CPA’ security model for brevity [20] . In IND-CPA, a probabilistic polynomial time-bounded adversary, given a public key, generates two equal-length 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: (IND-CPA): 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 IND-CPA adversary, we consider the following random experiment:
PPT Slide
Lager Image
We define the success probability of A via
PPT Slide
Lager Image
The proposed PKE scheme is said to be ( k,t,ε )-IND-CPA secure, if no adversary A running in time t has a success
PPT Slide
Lager Image
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 one-dimensional (1D) and two-dimensional (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 3-neighborhood, Von Neumann neighborhood and Moore neighborhood, which are respectively shown inFig. 1(a), (b), and (c).
PPT Slide
Lager Image
Different neighborhood structures
  • f . f:S→Sis transition rule (transition function).
Let
PPT Slide
Lager Image
denote the state of the i-th cell at t time step and
PPT Slide
Lager Image
denote the state of the i-th cell at t + 1 time step, the states of all cells in a CA at t time step
PPT Slide
Lager Image
called a configuration, denoted by St . 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:
PPT Slide
Lager Image
where r is the neighborhood radius.
One-dimensional CA with two-state (i.e. S = {0, 1}) and 3-neighborhood (i.e. r =1) called Elementary cellular automata (ECA). The state transition of the cell can be represented as follows:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
=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
PPT Slide
Lager Image
Rule 90
Although the cellular automata is an infinite system, yet it should be finite-dimensional 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.
PPT Slide
Lager Image
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,
PPT Slide
Lager Image
to be the current configuration of the i-th cell and its neighbors, where r is the neighborhood radius. Then the successor
PPT Slide
Lager Image
of the i-th cell can be achieved by:
PPT Slide
Lager Image
and the predecessor
PPT Slide
Lager Image
of the i-th cell is:
PPT Slide
Lager Image
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 one-dimensional, 4-state and
PPT Slide
Lager Image
-radius RCAs, labeled CA 1 , CA 2 , CA 3 and CA 4 , where CAi = ( 1,S,Nr, fi ), (1≤ i ≤ 4) , S is the state set and S = {0,1,2,3}, Nr is neighborhood with
PPT Slide
Lager Image
-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 .
PPT Slide
Lager Image
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 4-state 1/2-radius RCAs
PPT Slide
Lager Image
Reversible rules of four 1D 4-state 1/2-radius 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 self-reversing.
PPT Slide
Lager Image
CA1 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 .
PPT Slide
Lager Image
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 one-radius 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 two-dimensional 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 RCA-based public key encryption schemes in the literature. In this paper, we propose a new public key encryption scheme based on RCA, which utilizes several one-dimensional (1D) RCAs to construct a two-dimensional (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 T-shaped neighborhood structure, to achieve high level security.
- 3.3 Layered Cellular Automata and T-shaped 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 one-dimensional 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 8-layer 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 two-layer CA and T-shaped neighborhood are shown in Fig. 6 and Fig. 7 , respectively.
PPT Slide
Lager Image
A two-layer CA
PPT Slide
Lager Image
T-shaped neighbor in two-layer CA
From Fig. 7 , we can clearly see what T-shaped 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 T-shaped neighborhood [23] .
In summary, we have the reason to believe that the interaction between layers of the LCA with T-shaped 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 two-dimensional (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 two-dimensional 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 fca : Zp Zp be the transition rule of a 2D CA. For arbitrary message m Zp , evolved by the transition rule fca for k time steps ( k N ), will change to a new message m' , i.e.,
PPT Slide
Lager Image
The reversibility problem is that if given the message m' and the 2D rule fca , 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 Dependent-CA (C-DCA) problem and the Decisional Dependent-CA (D-DCA) problem, all based on the Reversibility problem of CA. If the Reversibility problem of CA can be solved, then we can solve the C-DCA problem, later we can solve the D-DCA problem. Based on these hard problems, we give a Decisional Dependent-CA (D-DCA) Assumption, in section 5 we will formally prove our proposed scheme is IND-CPA security, based on the D-DCA assumption.
Definition 2. (Computation Dependent-CA (C-DCA) problem)
Let fca : Zp Zp be the transition rule of a 2D CA and Fca : Zp Zp , where Fca =
PPT Slide
Lager Image
k N . Given α = Fca ( a ) ( a Zp ), i.e., α = Fca ( a ) =
PPT Slide
Lager Image
α is the result of α evolved by transition rule fca for k time steps. The C-DCA problem is for some unknown a Zp , computing Fca ( a+1 ) .
The C-DCA assumption holds if for any probabilistic polynomial time adversary, the probability Succ(A) is negligible, where,
PPT Slide
Lager Image
Definition 3. (Decisional Dependent-CA (D-DCA) problem)
The D-DCA problem is stated as follows: Let fca : Zp Zp be the transition rule of a 2D CA, and Fca : Zp Zp , where Fca =
PPT Slide
Lager Image
k N . There are two distributions:
PPT Slide
Lager Image
Where, Fca(a) means arbitrary a Zp evolved by the 2D transition rule fca for k time steps. The D-DCA problem is that for given ( α, β ) ∈ Zp , deciding ( α, β ) ∈ Rand or ( α, β ) ∈ DCA .
The advantage of a distinguisher A denoted by Adv(A) and defined by:
PPT Slide
Lager Image
Definition 4. (Decisional Dependent-CA (D-DCA) Assumption)
Given fca : Zp Zp be the transition rule of a 2D CA, let Fca : Zp , → Zp , Fca , =
PPT Slide
Lager Image
k N , and a pair ( α, β ) ∈ Zp , an adversary takes ( α, β ) as input and distinguishes ( α, β ) comes from the Rand or the DCA distribution. We consider the following random experiment on the D-DCA problem.
  • Experiment
PPT Slide
Lager Image
  • that if existε∈ [0,1] is non-negligible andAdv(A) ≥ε,
  • then returnb= 1, else returnb= 0 .
We define the corresponding success probability of A in solving D-DCA problem via
PPT Slide
Lager Image
The PKE scheme is said to be ( t, ε )-secure if no polynomial algorithm A running in time t has success Experiment
PPT Slide
Lager Image
4. Proposed Scheme
In this section, we present our public key encryption scheme PKE based on the layered cellular automata with T-shaped neighborhood, which mainly consists of three algorithms, namely Kgen, Enc and Dec.
Kgen. Given a security parameter k N , we define four one-dimension (1D) RCAs, labeled CA 1 , CA 2 , CA 3 and CA 4 , and each CAi = ( 1, S, Nr, fi ), where S is the state set and Nr is the neighborhood with r -radius ( r N ). Set each CAi has n -state, where ( r N ) . Set each CAi has n -state, where n N and n ≥ 2, the state set S = {0,1,ㆍㆍㆍ, n -1}. Set the transition rule fi : 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* , fca ) is constructed by the 1D RCAs in the private key sk , so its state set is S . Set its transition rule
PPT Slide
Lager Image
The neighborhood structure is T-shaped neighborhood, we set a number r' N to define the neighborhood radius of CA * . Define a function Fca : S S , Fca =
PPT Slide
Lager Image
PPT Slide
Lager Image
A r' -radius T-shaped neighborhood structure in plane
Construct a r' -radius T-shaped neighborhood structure in a two-dimensional plane, as shown in Fig. 8 , and set all possible configurations. Take every configuration as the input of the transition rule
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
And we set the map of the states of the central cell and its neighbors to its new state, i.e.,
PPT Slide
Lager Image
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 = fca .
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 T-shaped 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 α Zp , given message M Zp 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, ㆍㆍㆍ,n-1}, so codingαtoα', whereα'=α1α2α3ㆍㆍㆍ,αi∈S. Then arrangedα'into a layered CA, as the radius of the T-shaped 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.
PPT Slide
Lager Image
A 4-layer CA with 3-radius T-shaped neighborhood
  • Let(l=r'+1,1 ≤i≤a, 1 ≤j≤b) denote the state of the cell at thel-layer,i-row andj-column atttime step, whereais the row number andbis the column number.
  • Select the neighbors of each cell according to the T-shaped 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,
PPT Slide
Lager Image
All the outputs will comprise the ciphertext of the α , denoted by Fca ( α ), 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,
PPT Slide
Lager Image
  • Encodeα'toα∈Zp, and computeα+ 1 ∈Zp, then use theEncalgorithm encryptα+ 1 intoF'ca(α+1)modp.
  • ComputeM= (C2-F'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 chosen-plaintext attack under the assumption that the D-DCA 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 fca : S S, S is the state set, set function Fca : S S , Fca =
PPT Slide
Lager Image
For arbitrary a Zp , coding a to a' = a1a2a3 ㆍㆍㆍ, where ai S . We set Fca α denote a' evolved by function Fca , and code Fca ( a ) to F'ca ( a ), where F'ca Zp .
Assume that there is an adversary A which runs in polynomial time and has a non-negligible 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 non-negligible advantage to break the D-DCA problem.
First, A chooses two messages m 0 Zp and m 1 Zp , and returns them to B . At this moment, B flips a bit b ∈ {0,1} and generates a ciphertext C = ( C 1 , C 2 ), = ( α , mb + β ) mod p , where ( α , β ) ∈ Zp . 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 (α,β) ∈ Zp comes from the random distribution Rand , the pair
PPT Slide
Lager Image
is uniformly distributed, hence independently of b . Then
PPT Slide
Lager Image
On the other hand, when the pair ( α,β ) ∈ Zp comes from DCA distribution, one can remark that ( C 1 , C 2 ) is a valid ciphertext of mb , following a uniform distribution among the possible ciphertexts. Then
PPT Slide
Lager Image
The advantage of B in distinguishing the DCA and Rand distributions is
PPT Slide
Lager Image
therefore greater than ε /2 .
Since ε is non-negligible, the above result contradicts with the assumption that the D-DCA problem is hard. As a result, the ciphertext C = C 1 , C 2 ), is semantically secure under the chosen-plaintext attack (IND-CPA).
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 one-dimensional 4-state 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 * , fca ), CA * is a 2D CA where the transition rule
PPT Slide
Lager Image
set the radius of the T-shaped 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
PPT Slide
Lager Image
as the input of, where
PPT Slide
Lager Image
S is the state of the i -th row j -th column cell, and the corresponding 2D transition rule can be expressed as fca :
PPT Slide
Lager Image
There is a concrete example of the rule generation process in Fig. 10 , and fca : (2031) → 3 is a 1-radius 2D rule. Table 3 shown some 2D rules generated by Kgen algorithm.
PPT Slide
Lager Image
The process of generating a 2D rule
Part of the generated 2D rules
PPT Slide
Lager Image
Part of the generated 2D rules
Enc. Randomly select a large prime number p = 37591 , and a random number α = 30930 ∈ Zp . Given a message M = 29753 ∈ Zp . 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 two-layer CA because of the radius of the T-shaped neighborhoodr'= 1. The structure of the two-layer CA is shown inFig. 11(a), and its second layer is shown inFig. 11(b).
PPT Slide
Lager Image
Two-layer Cellular Automata
  • SetFca:S→S,Fca=wherefcais the transition rule of the public keyCA*. Take each cell of the two-layer 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 self-reversible, i.e.
PPT Slide
Lager Image
, so we should not compute their reverse rules.
  • ForC1= 10791 , change it to quanternary form 02220213 and arrange it into a two-layer CA.
  • Use the transition rulesf1,f2,f3,f4in sk to cyclic evolve every cell successively for 5 times. The final configuration of the two-layer CA is the plaintext ofC1, that is the random numberα.
  • Compute and encryptα+ 1 intoF'ca(α+1)modp= 17210.
  • ComputeM= (C2-F'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
PPT Slide
Lager Image
different from the
PPT Slide
Lager Image
Based on the Reversibility problem of CA, only more than half bits in
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 D-DCA 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 T-shaped neighborhood with r' -radius, so there may be
PPT Slide
Lager Image
possible rules generated as the public key, i.e., the key space is
PPT Slide
Lager Image
. 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
PPT Slide
Lager Image
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 RSA-1024 to compare with the proposed PKE.
Because the key space of RSA-1024 algorithm is 2 1024 , as well as the plaintext space and ciphertext space, here we set n =2 and r' = 3, such that
PPT Slide
Lager Image
= 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 RSA-1024 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 RSA-1024, which obviously demonstrates the efficiency of our proposed scheme.
Average execution time for RSA-1024 and PKE
PPT Slide
Lager Image
Average execution time for RSA-1024 and PKE
8. Conclusion
In this paper, we have proposed an efficient public key encryption scheme based on layered cellular automata. We use four one-dimensional (1D) RCAs to construct a two-dimensional (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 chosen-plaintext attacks (IIND-CPA) in the standard model, based on the difficult Decisional Dependent-CA 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 RSA-1024, and the results demonstrate that proposed scheme is more efficient than RSA-1024.
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.
References
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 One-way 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 High-quality Random Numbers by Two-dimensional 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 Multi-Granularity 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 “Multi-layer 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 T-shaped 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 Non-uniform 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)