# An Effective Privacy-Preserving Algorithm Based on Logistic Map and Rubik’s Cube Transformation

Authors: Wenbin Yao; Pengdi Ye; Xiaoyong Li
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

Security and privacy issues present a strong barrier for users to adapt to cloud storage systems. In this paper, a new algorithm for data splitting called EPPA is presented to strengthen the confidentiality of data by two-phase process. In EPPA, data object is organized to be several Rubik’s cubes executed for several rounds transformation at the first phase. In every round, chaotic logistic maps generate pseudorandom sequences to cover the plaintext by executing Exclusive-OR operation to form the cipher. Then logistic map is used to create rotation policies to scramble data information based on Rubik’s cube transformation. At the second phase, all cubes are unfolded and combined together as a cross-shaped cube, which will be partitioned into a few data fragments to guarantee that every fragment does not contain continuous bytes. These fragments are stored on randomly chosen servers within cloud environment. Analyses and experiments show that this approach is efficient and useable for the confidentiality of user data in cloud storage system.


---

## Body

## 1. Introduction

As cloud services become more and more popular, securing data information within cloud environments has become a critical requirement [1]. The importance of minimizing information leakage in a cloud environment is highlighted by the current use of the cloud infrastructure for applications that require strong confidentiality guarantees.Cloud environment denotes an architectural shift toward thin clients and conveniently centralized provision of computing resources. However, users’ lack of direct resource control in the cloud prompts concern about the potential for data privacy violations, particularly abuse or leakage of sensitive information by service providers. The confidentiality in cloud systems is a big obstacle for users to step into it, as many users said “my sensitive corporate data will never be in the Cloud” [2].In traditional researches, cryptographic algorithms are employed to ensure data confidentiality, such as OceanStore [3], FarSite [4], and PAST [5]. However, there is a tendency among users to keep passwords simple and memorable [6–8] leading to the possibility of brute force attacks, and keys that provide adequate encryption today are likely to be cracked by computation effort in the future.Rabin designed information dispersal algorithm (IDA) [9] to deal with the security and reliability problem for the storage and transmission of data file in distributed systems. Nevertheless, it may stop malicious users from parsing information from one piece, and it still cannot prevent them from getting information from pieces. Therefore, Rabin’s algorithm is always combined with keyed encryption by some distributed storage system.The research of Subbiah and Blough [10] avoids the use of keyed encryption by using secret sharing threshold scheme that was introduced independently by Shamir [11] and Blakley [12]. Secret sharing is mostly used in distributed storage system, but if the attackers have the opportunity to get enough parts, the original object still can be reconstructed.Potshards [13, 14] separates security and redundancy by utilizing two levels of secret sharing, while Subbiah and Blough’s work only uses one level of secret sharing. It uses secret sharing to split an object into fragments at the first level. Then this scheme uses redundancy encoding to make shares. However, the algorithm has a storage overhead problem produced by two-level secret sharing.Jakimoski and Kocarev [15–17] discussed the relationship between cryptography and chaos theory and similarities of their crucial concepts such as mixing property and sensitivity to changes in initial conditions and parameters. They also present a systematic procedure for design of encryption algorithms based on chaotic maps.Parakh and Kak [18–20] use an approach that creates data partitions and distribute them over the network within cloud environment, which they called implicit security. Thus, data objects might be fragmented in such a way that one partition reveals no usable information to the attackers. The authors admit this method may be inefficient for large datasets, so they provide an alternate data security method which encrypts the data and stores it on a single server that data owner trusts. Then the partitions of the key are created and dispersed over the network to keep encryption key secret. However, when the attackers get these partitions, the key will be reconstructed and lead to information leak directly. However, it suffers from the drawback that the staff member generating the keys can access the entire data set and must be trusted not to reveal the keys to others.ESSA [21] is presented as a two-level information dispersal scheme, which takes advantage of knight’s tour problem as scramble policy. Because of figuring out tour paths may need a lot of computation, this approach needs to obtain and store all of tour paths before scrambling data. As the path number of knight’s tour on a 8 × 8 matrix is almost 3.3 × 1013 [22], if recording one tour path needs 128 bytes, it will cost about 4 PB storage space to save all of these tour paths, which is unaffordable for most information systems.Gentry [23] discovers a fully homomorphic encryption scheme based on ideal lattices. However, it remains far from being adopted in practice due to the expansion in cipher text and slow encryption and decryption speeds. A number of fully homomorphic encryption schemes have been discovered since then [24–27] however still suffer from the practical limitations.Kaddoum et al. [28, 29] focus on giving a good performance to chaos-based communication system, while other researchers [30–33] leverage Rubik’s cube and logistic sequence to provide image encryption. However, these researches are not for the cloud storage environment.The goal of this paper is not to provide a general encryption algorithm or privacy-preserving computation algorithm such as homomorphic encryption but rather offer a data privacy-preserving algorithm called EPPA, which combines data encryption and partition to address the problem of data confidentiality in cloud storage environment.Data object in EPPA is encrypted and partitioned into fragments and stored at randomly chosen servers in the cloud that are known only to the owner of the data. Access to data objects depends not only on the knowledge of initial value of logistic map but also on the knowledge of pieces combination order and where these pieces are stored. It scrambles data information in two phases to strengthen the confidentiality of data.In the first phase, original data objects are split into segments. Every segment is organized as ann×n×n scramble cube. Every scramble cube carries out r round rotations. Each round executes two operations, which are data encryption and scramble. Two mapping rules, which are XOR table mapping and rotation method table mapping, are used to map the sequences that are created by logistic map to XOR tables and rotation method tables.On the basis of XOR tables, the shifted subsquares are XORed to implement encryption. Then according to the rotation method tables, the data information covered on the subsquares of the scramble cubes may be scrambled several times based on the principles of Rubik’s cubes rotations. In this phase, the original data is split and rearranged, and thus the former semantics becomes meaningless. Though data information is scrambled, it still has locality feature. Therefore, the locality feature will be broken in the next phase.In the second phase, all of the scrambled Rubik’s cubes are unfolded and combined together as a cross-shaped cube, which will be split into fragments to guarantee that every fragment does not contain continuous bytes so that none of the individual fragment will reveal any useful information. At last, these fragments will be stored, respectively, on randomly chosen servers of cloud computing system. In this phase, data object is split and recombined to break the data locality feature, so that malicious users cannot parse any semantics information even if they obtain some fragments.Analyses prove the confidentiality of EPPA and the experiments show that EPPA has decent run-time efficiency.The rest of this paper is organized as follows. Section2 presents system model and security model. Section 3 introduces logistic map, Rubik’s cube, and the rotation model of Rubik’s cube. Section 4 describes the algorithm details of EPPA. Section 5 conducts a series of analyses and experiments to the EPPA’s confidentiality and run-time efficiency. The last section concludes our work.


## 2. System Model and Security Model

### 2.1. System Model

Figure1 shows the architecture of EPPA, which consists of the following system entities:(1)
a cloud provider which manages and operates a cloud infrastructure of storage services,(2)
cloud users that employ the cloud storage resource facilities to remotely store data. The Internet is the main communication backbone for exchanging information between the cloud users and the cloud.Figure 1
System overview.In this system model, the key which is kept by the cloud user consists of the fragments order, fragments location information, and the initial value of logistic map. EPPA processes data objects in two phases guaranteeing that every fragment does not contain any continuous bytes. Then it chooses several servers randomly and sends one fragment to each chosen server. At last, it records the fragments’ location information and combination order, which are needed when users try to read data.


### 2.2. Security Assumption

EPPA has the following assumptions.(i)
The cloud users’ environment is trusted and will not be corrupted by any adversary. Users keep fragments order, fragments location information, and the initial value of logistic map themselves.(ii)
The cloud service provider is semitrusted. It will not deny service to any authorized users and will correctly execute the tasks assigned by users. Besides, it has access control policy, so that users cannot access unauthorized data. However, it is curious about the data content.


### 2.3. Security Model

The security model of EPPA is described by summarizing the possible attacks and delimiting the antiattack capability.Brute Force Attack. EPPA should provide large key space so that the attackers cannot try all possible combinations in acceptable time to guess the key used to decrypt fragments stored in the cloud.Statistical Attack. A small change in the key of EPPA should cause a drastic change to resist statistical attack.Differential Cryptanalysis. EPPA should provide extremely low differential approximate probability so that the attackers cannot discover where the cipher exhibits nonrandom behavior, exploiting such properties to recover the secret key.Linear Cryptanalysis. EPPA should provide extremely low linear approximate probability so that the attackers cannot find affine approximations to the action of a cipher.


## 2.1. System Model

Figure1 shows the architecture of EPPA, which consists of the following system entities:(1)
a cloud provider which manages and operates a cloud infrastructure of storage services,(2)
cloud users that employ the cloud storage resource facilities to remotely store data. The Internet is the main communication backbone for exchanging information between the cloud users and the cloud.Figure 1
System overview.In this system model, the key which is kept by the cloud user consists of the fragments order, fragments location information, and the initial value of logistic map. EPPA processes data objects in two phases guaranteeing that every fragment does not contain any continuous bytes. Then it chooses several servers randomly and sends one fragment to each chosen server. At last, it records the fragments’ location information and combination order, which are needed when users try to read data.


## 2.2. Security Assumption

EPPA has the following assumptions.(i)
The cloud users’ environment is trusted and will not be corrupted by any adversary. Users keep fragments order, fragments location information, and the initial value of logistic map themselves.(ii)
The cloud service provider is semitrusted. It will not deny service to any authorized users and will correctly execute the tasks assigned by users. Besides, it has access control policy, so that users cannot access unauthorized data. However, it is curious about the data content.


## 2.3. Security Model

The security model of EPPA is described by summarizing the possible attacks and delimiting the antiattack capability.Brute Force Attack. EPPA should provide large key space so that the attackers cannot try all possible combinations in acceptable time to guess the key used to decrypt fragments stored in the cloud.Statistical Attack. A small change in the key of EPPA should cause a drastic change to resist statistical attack.Differential Cryptanalysis. EPPA should provide extremely low differential approximate probability so that the attackers cannot discover where the cipher exhibits nonrandom behavior, exploiting such properties to recover the secret key.Linear Cryptanalysis. EPPA should provide extremely low linear approximate probability so that the attackers cannot find affine approximations to the action of a cipher.


## 3. Logistic Map and Rubik’s Cube Transformation

A discrete dynamical system is a dynamical system whose state evolves over state space in discrete time steps according to a fixed rule, which can be described as a mapping G of a phase spacex to itself. Therefore, the logistic map and Rubik’s cube, which are employed in EPPA, are all discrete dynamical systems.


### 3.1. Logistic Map

Chaos and cryptography have some common features, the most prominent being sensitivity to variables’ and parameters’ changes. Iteration of encryption roundleads to the desired diffusion and confusion. Iteration of the chaotic map spreads the initial region over the entire phase space.An important difference between the encryption round and the chaotic map is that the encryption round is defined on a finite set and depends on the key value. This is not the case within the chaotic map. A mapping defined on a finite set can be derived from a chaotic map by discretization, in which EPPA substitutes the continuous variables and the operations defined over real numbers with variables that take values from the finite set of integers and appropriate integer operations.Researches [34–36] numerically observe that the average cycle and transient lengths of a chaos derived pseudorandom number generator (PRNG) grow exponentially with the precision of implementation and from this fact deduce that using high-precision arithmetic one can obtain PRNGs which are still of cryptographic interest.Logistic map is one of the most widely used chaotic maps, which has distinctive properties for encryption, such as the natural concealment and high sensibility to initial condition. It is employed to generate rotation policies for Rubik’s cubes and XOR table for encryption, the function of which is shown as(1)xn+1=μxn1-xn.By using formula (1) iteratively, a sequence can be created. In order to keep the iterate sequence chaotic from almost all of initial conditions, μ=4 is in common use. According to the initial value sensibility of logistic map, no same sequences will be generated while two initial values are different. Consequently, the initial value could be regarded as a secret key for encryption and decryption.


### 3.2. Rubik’s Cube

Rubik’s cube is a kind of toy, which is divided into several subcubes. Inn×n×n Rubik’s cube, one sticker covers one subsquare, so n×n stickers cover each of the six squares. Every column can be rotated clockwise or anticlockwise around one axis. By turning the columns, a certain picture can be pieced together on the surface of the Rubik’s cube.


### 3.3. Rubik’s Cube Rotation Model

One row or column rotation of Rubik’s cube can be represented as the movement of several subcubes, which can be decomposed into two parts, subcube’s position shift and subsquare’s orientation shift.


#### 3.3.1. Subcube’s Position Shift

The process of subcube’s position shift can be defined as(2)C′=RC.ParametersC and C′ indicate the state of subcube before and after rotation, respectively. R indicates state transition matrix of one rotation of Rubik’s cube.A Rubik’s cube can build three-dimensional coordinates like Figure1 shows, and the position coordinate of one subcube can be described as follows:
(3)C=xyz.From (2) and (3), the process of subcube’s position shift can be represented by
(4)x′y′z′=Rxyz.Figure2 uses 3 × 3 × 3 Rubik’s cube as an example to describe the three-dimensional coordinates of every subcube. The central point of Rubik’s cube is regarded as the origin of coordinates. Then coordinate of every subcube on the surface of Rubik’s cube can be represented by [xyz], x,y,z∈{1,0,-1}.Figure 2
3 × 3 × 3 Rubik’s cube.According to three-dimensional coordinates in Figure2, substitute any subcube’s position coordinate before rotation and position coordinate after rotation into (4), and the state transition matrix of clockwise rotation around x-axis can be figured up by
(5)Rx=C′C-1=1000010-10.Anticlockwise rotation aroundx-axis can be figured up by the same way:
(6)Rx-anti=C′C-1=10000-1010.R
y, Ry-anti, Rz, and Rz-anti, which can be figured out by the same way, are described as follow:
(7)Ry=00-1010100,Ry-anti=001010-100,Rz=010-100001,Rz-anti=0-10100001.


#### 3.3.2. Subsquare’s Direction Shift

As Figure3 shows, six different direction squares of Rubik’s cube are marked as Up (U), Down (D), Front (F), Back (B), Left (L), and Right (R).Figure 3
3 × 3 × 3 scramble cube with 54 bytes of data.While a row or column rotates around one axis, its subsquares that are parallel to this axis will change their direction. Figure3 shows an example that if a column rotates around y-axis, then the subsquares in red color should change their direction. Define a function:
(8)Dx:U⟶L⟶D⟶R⟶U
which means that when a column makes clockwise rotation around x-axis, the subsquare in Up direction will change its direction to Left, the subsquare in Up direction will change its direction to Left, the subsquare in Left direction will change its direction to Down, the subsquare in Down direction will change its direction to Right, and the subsquare in Right direction will change its direction to Up.Other functions can be defined in the same way:(9)Dx-anti:U⟶R⟶D⟶L⟶UDy:U⟶B⟶D⟶F⟶UDy-anti:U⟶F⟶D⟶B⟶UDz:F⟶L⟶B⟶R⟶FDz-anti:F⟶R⟶B⟶L⟶F.


## 3.1. Logistic Map

Chaos and cryptography have some common features, the most prominent being sensitivity to variables’ and parameters’ changes. Iteration of encryption roundleads to the desired diffusion and confusion. Iteration of the chaotic map spreads the initial region over the entire phase space.An important difference between the encryption round and the chaotic map is that the encryption round is defined on a finite set and depends on the key value. This is not the case within the chaotic map. A mapping defined on a finite set can be derived from a chaotic map by discretization, in which EPPA substitutes the continuous variables and the operations defined over real numbers with variables that take values from the finite set of integers and appropriate integer operations.Researches [34–36] numerically observe that the average cycle and transient lengths of a chaos derived pseudorandom number generator (PRNG) grow exponentially with the precision of implementation and from this fact deduce that using high-precision arithmetic one can obtain PRNGs which are still of cryptographic interest.Logistic map is one of the most widely used chaotic maps, which has distinctive properties for encryption, such as the natural concealment and high sensibility to initial condition. It is employed to generate rotation policies for Rubik’s cubes and XOR table for encryption, the function of which is shown as(1)xn+1=μxn1-xn.By using formula (1) iteratively, a sequence can be created. In order to keep the iterate sequence chaotic from almost all of initial conditions, μ=4 is in common use. According to the initial value sensibility of logistic map, no same sequences will be generated while two initial values are different. Consequently, the initial value could be regarded as a secret key for encryption and decryption.


## 3.2. Rubik’s Cube

Rubik’s cube is a kind of toy, which is divided into several subcubes. Inn×n×n Rubik’s cube, one sticker covers one subsquare, so n×n stickers cover each of the six squares. Every column can be rotated clockwise or anticlockwise around one axis. By turning the columns, a certain picture can be pieced together on the surface of the Rubik’s cube.


## 3.3. Rubik’s Cube Rotation Model

One row or column rotation of Rubik’s cube can be represented as the movement of several subcubes, which can be decomposed into two parts, subcube’s position shift and subsquare’s orientation shift.


### 3.3.1. Subcube’s Position Shift

The process of subcube’s position shift can be defined as(2)C′=RC.ParametersC and C′ indicate the state of subcube before and after rotation, respectively. R indicates state transition matrix of one rotation of Rubik’s cube.A Rubik’s cube can build three-dimensional coordinates like Figure1 shows, and the position coordinate of one subcube can be described as follows:
(3)C=xyz.From (2) and (3), the process of subcube’s position shift can be represented by
(4)x′y′z′=Rxyz.Figure2 uses 3 × 3 × 3 Rubik’s cube as an example to describe the three-dimensional coordinates of every subcube. The central point of Rubik’s cube is regarded as the origin of coordinates. Then coordinate of every subcube on the surface of Rubik’s cube can be represented by [xyz], x,y,z∈{1,0,-1}.Figure 2
3 × 3 × 3 Rubik’s cube.According to three-dimensional coordinates in Figure2, substitute any subcube’s position coordinate before rotation and position coordinate after rotation into (4), and the state transition matrix of clockwise rotation around x-axis can be figured up by
(5)Rx=C′C-1=1000010-10.Anticlockwise rotation aroundx-axis can be figured up by the same way:
(6)Rx-anti=C′C-1=10000-1010.R
y, Ry-anti, Rz, and Rz-anti, which can be figured out by the same way, are described as follow:
(7)Ry=00-1010100,Ry-anti=001010-100,Rz=010-100001,Rz-anti=0-10100001.


### 3.3.2. Subsquare’s Direction Shift

As Figure3 shows, six different direction squares of Rubik’s cube are marked as Up (U), Down (D), Front (F), Back (B), Left (L), and Right (R).Figure 3
3 × 3 × 3 scramble cube with 54 bytes of data.While a row or column rotates around one axis, its subsquares that are parallel to this axis will change their direction. Figure3 shows an example that if a column rotates around y-axis, then the subsquares in red color should change their direction. Define a function:
(8)Dx:U⟶L⟶D⟶R⟶U
which means that when a column makes clockwise rotation around x-axis, the subsquare in Up direction will change its direction to Left, the subsquare in Up direction will change its direction to Left, the subsquare in Left direction will change its direction to Down, the subsquare in Down direction will change its direction to Right, and the subsquare in Right direction will change its direction to Up.Other functions can be defined in the same way:(9)Dx-anti:U⟶R⟶D⟶L⟶UDy:U⟶B⟶D⟶F⟶UDy-anti:U⟶F⟶D⟶B⟶UDz:F⟶L⟶B⟶R⟶FDz-anti:F⟶R⟶B⟶L⟶F.


## 3.3.1. Subcube’s Position Shift

The process of subcube’s position shift can be defined as(2)C′=RC.ParametersC and C′ indicate the state of subcube before and after rotation, respectively. R indicates state transition matrix of one rotation of Rubik’s cube.A Rubik’s cube can build three-dimensional coordinates like Figure1 shows, and the position coordinate of one subcube can be described as follows:
(3)C=xyz.From (2) and (3), the process of subcube’s position shift can be represented by
(4)x′y′z′=Rxyz.Figure2 uses 3 × 3 × 3 Rubik’s cube as an example to describe the three-dimensional coordinates of every subcube. The central point of Rubik’s cube is regarded as the origin of coordinates. Then coordinate of every subcube on the surface of Rubik’s cube can be represented by [xyz], x,y,z∈{1,0,-1}.Figure 2
3 × 3 × 3 Rubik’s cube.According to three-dimensional coordinates in Figure2, substitute any subcube’s position coordinate before rotation and position coordinate after rotation into (4), and the state transition matrix of clockwise rotation around x-axis can be figured up by
(5)Rx=C′C-1=1000010-10.Anticlockwise rotation aroundx-axis can be figured up by the same way:
(6)Rx-anti=C′C-1=10000-1010.R
y, Ry-anti, Rz, and Rz-anti, which can be figured out by the same way, are described as follow:
(7)Ry=00-1010100,Ry-anti=001010-100,Rz=010-100001,Rz-anti=0-10100001.


## 3.3.2. Subsquare’s Direction Shift

As Figure3 shows, six different direction squares of Rubik’s cube are marked as Up (U), Down (D), Front (F), Back (B), Left (L), and Right (R).Figure 3
3 × 3 × 3 scramble cube with 54 bytes of data.While a row or column rotates around one axis, its subsquares that are parallel to this axis will change their direction. Figure3 shows an example that if a column rotates around y-axis, then the subsquares in red color should change their direction. Define a function:
(8)Dx:U⟶L⟶D⟶R⟶U
which means that when a column makes clockwise rotation around x-axis, the subsquare in Up direction will change its direction to Left, the subsquare in Up direction will change its direction to Left, the subsquare in Left direction will change its direction to Down, the subsquare in Down direction will change its direction to Right, and the subsquare in Right direction will change its direction to Up.Other functions can be defined in the same way:(9)Dx-anti:U⟶R⟶D⟶L⟶UDy:U⟶B⟶D⟶F⟶UDy-anti:U⟶F⟶D⟶B⟶UDz:F⟶L⟶B⟶R⟶FDz-anti:F⟶R⟶B⟶L⟶F.


## 4. Details of EPPA

### 4.1. Definitions

Definition 1 (segment).
EPPA treats the original data object as byte stream and splits it into fixed length pieces, which are recorded as segment. Every byte of a segment is attached to the subsquare of Rubik’s cube. Therefore, each segment has6×n×n bytes.Definition 2 (scramble cube).
Scramble cube is ann×n×n Rubik’s cube that contains data from a segment on its surfaces. Data information on the cube will be scrambled by Rubik’s cube rotation. Figure 3 shows a 3 × 3 × 3 scramble cube with 54 bytes.Definition 3 (split cube).
Every three-dimensional cube can be unfolded by opening the cube from the Up direction square. Figure4 shows the flat pattern of an opened cube. Arranging all of the unfolded scramble cubes one by one as a cross-shaped cube, as shown in Figure 5, forms a split cube. Figure 6 indicates a split cube combined by three unfolded scramble cubes, and each unfolded scramble cube is parallel to YOZ coordinate plane.Figure 4
Unfolded 3 × 3 × 3 scramble cube.Figure 5
Unfolded scramble cube arrange method.Figure 6
A split cube with 3 unfolded scramble cubes.Definition 4 (fragment).
Fragment is the data piece made by split cube. The subcubes with red color in Figure6 composed a typical fragment. EPPA divides original data objects into 6×n×n fragments.


### 4.2. Algorithm Details

Figure7 shows the details of EPPA, which is mainly combined by two-phase process.Figure 7
EPPA progress.In the first phase, original data objects are split into segments. Then this segment is organized as ann×n×n scramble cube.Two mapping rules, which are XOR table mapping and rotation method table mapping, are used to map the sequences that are created by logistic map according to XOR table and rotation method tables.Every scramble cube carries outr round rotations. Each round executes two operations, which are data encryption and scramble. According to XOR tables, the shifted subsquares are XORed to implement data encryption. Besides, on the basis of the rotation method tables, the data information covered on the subsquares of the scramble cubes may be scrambled several times based on the principles of Rubik’s cubes rotations. In this phase, the original data is encrypted and scrambled, and thus the former semantics becomes meaningless. However, data information still has locality feature. Therefore, the locality feature will be broken in the next phase.In the second phase, all of the scrambled Rubik’s cubes are unfolded and combined together as a cross-shaped cube, which will be split into fragments to guarantee that every fragment does not contain continuous bytes. At last, these fragments will be stored, respectively, on randomly chosen servers of cloud storage system. In this phase, data object is split and recombined to break the data locality feature, so that malicious users cannot parse any semantics information even if they only obtain some fragments.


#### 4.2.1. Initialization

EPPA needs users to choose the split parameters. Then the system can figure out the scramble method. The split parameters that need to be determined are as follows:(i)
the size of Rubik’s cube isn×n×n, n≥3;(ii)
the initial value of logistic map isx00∈(0,1);(iii)
the size of rotation round isr.Users can choosen based on the need of fragments’ number, which is 6×n×n.


#### 4.2.2. First Phase

The first phase is composed by segment chaining andr round transformation. Every round transformation has two operations, which are data encryption and data scramble based on the rotation of scramble cube.(
1) Segment Chaining. In this step, when segment Si finishes its rotation round, it will be XORed with segment Si+1. After that, segment Si+1 can start its own rotation round. A sequence with 6×n×n element is created by using formula (1) iteratively with initial value of logistic map x00, whose element is uniformly partitioned and mapped to integers within {0,…,255}. It can be treated as segment S0 to complete segment chaining with segment S1.(
2) Mapping Rules. EPPA leverages logistic map to create XOR table and rotation method table for every scramble cube. Formula (10) is defined to generate a sequence by using formula (1) iteratively:
(10)Xi=xi1,xi2,…,xir.Parameteri∈{1,…,N/(6×n×n)} that represents this sequence is prepared for the ith scramble cube, which is created from the last element xi-1r in Xi-1 by formula (1). Parameter r indicates the size of rotation round.Since the output of logistic mapXn belongs to [0,1], discretization is essential process to map Xn to Rubik’s cube rotation policy and replace schedule. As a result, the logistic map is scaled so that input and output values of the map are in the interval. Meanwhile, the scaled logistic map is discretized. Two mapping functions of rotation method vector mapping and replacing table mapping rules are needed to achieve target.(a) XOR Table Mapping. Since EPPA uses XOR operation to encrypt data information, a XOR element set can be indicated as {0,1,2,…,255}. Because every segment has 6×n×n bytes data, a sequence with 6×n×n elements is needed and will be mapped to the element within {0,…,255} to complete XOR operation.When in thejth round rotation of Rubik’s cube, xij is used as initial value to generate r different logistic sequence Xij={xij1,xij2,…,xij6×n×n}, j=1,2,…,r, by formula (1). Then the XOR table can be created by the mapping function below:
(11)Wij=MWXij=floor4xij1-xij×256.FunctionMW maps every element in sequence Xij to an integer that in the range {0,…,255}. Then the XOR table Wij={w1,w2,…,w6×n×n} is constructed.(b) Rotation Method Table Mapping. As n×n×n Rubik’s cube has three axes, and every axis has two rotation directions, which are clockwise and anticlockwise, there will be 2×3×n basic rotation methods. A rotation tuple (ma, R, D) is defined to represent a rotation method, in which parameter m∈{1,…,n} means themth row or column perpendicular to a(a∈{x,y,z}) axis, parameter R means the state transition matrix, and parameter D means the direction shift function.So a rotation method set with6×n element can be described as {(1x,Rx,Dx), (1x,Rx-anti,Dx-anti), (2x,Rx,Dx),…,(nx,Rx-anti,Dx-anti), (1y,Ry,Dy), (1x,Ry-anti,Dy-anti),…,(ny,Ry-anti,Dy-anti), (1z,Rz,Dz), (1z,Rz-anti,Dz-anti),…, (nz,Rz-anti,Dz-anti)}.Therefore, a random sequence, whose elements are integral numbers within[1, 6×n], is needed in order to map numbers to the 6×n different rotation methods.Rotation method vector mapping function for each scramble cube is created as follows:(12)Vi=MVXi,
where i∈{1,…,N/(6×n×n)}, N means the number of bytes of original data object. MV maps every element in Xi to an integer that in the range [1, 6×n] and then maps the integers to the rotation method set. In this way, the rotation method table Vi={v1,v2,…,vr} is constructed. Every element in Vi is a rotation tuple (ma, R, D). Since every segment is treated as a scramble cube, which may be rotated several times based on the rotation methods table, the scramble cube can be rotated several times. As a result, the segments are scrambled.(
3) Round Transformation. After generating scramble cube from segment Si, rotation method table Vi={v1,v2,…,vr} can be created by rotation method table mapping, and XOR table Wij={w1,w2,…,w6×n×n}, j=1,2,…,r, can be created by XOR table mapping. According to vj and Wij, j=1,2,…,r, data encryption and scramble can be described as follows.(a) Data Encryption. Let Bj,k, k=1,2,…,6×n×n denote every byte in one segment. On the basis of XOR table Wij={w1,w2,…,w6×n×n}, the partial encryption is given with
(13)Bj,2=Bj-1,1⊕f0Bj,3=Bj-1,2⊕f1⋮Bj,0=Bj-1,6×n×n⊕f6×n×n-1Bj,1=Bj-1,0⊕f6×n×n,
where the functions fk have the following form:
(14)fk=Bj-1,1⊕⋯⊕Bj-1,k⊕wj,k.(b) Data Scramble. Scramble cube can be regarded as a normal Rubik’s cube with 6×n×n bytes data attached to the surface of it. Since vj is a rotation tuple (ma, R, D), which indicates three element of rotation, sub-cube’s position shift and sub-square’s orientation shift can be done following these three element.In the fact that every subsquare of the scramble cube is covered by one byte data, at least4n byte data will be scrambled in one round.


#### 4.2.3. Second Phase

At the beginning of the second phase, each scramble cube still has its own six squares, but the bytes on the squares have changed. Then all of the scrambled cubes are unfolded and combined together as a new split cube like Figure5 shown, which will be split into 6×n×n fragments in the direction vertical to YOZ coordinate plane. The sub-cube with red color in Figure 6 indicates a typical fragment. At last, every fragment contains one byte from each segment. These fragments will be sent to the randomly chosen servers. The location and order information of fragments will be recorded in the fragment index.


### 4.3. Data Restoration Process

The restoration process is the opposite way as follows.Firstly, the second phase is redone in an opposite way to get the split cube. Based on the location and order information of fragments, all of the fragments can be combined together exactly to get the split cube.Secondly, all of the scramble cubes are restored by dividing the split cube in the direction parallel toYOZ coordinate plane. Then calculate the rotation method table Vi={v1,v2,…,vr} and XOR table Wij={w1,w2,…,w6×n×n} (i={1,2,…,N/(6×n×n)}, j=1,2,…,r) using the initial value of logistic map, which is input by user.Thirdly, carry out the first phase of EPPA in an opposite way from the last segment to the first one. In every round, the reverse rotation method table with reverse direction is represented as follows:(15)Vi-1=v1-1,v2-1,…,vr-1.V
i
-
1 is converted from Vi by changing the state transition matrix R and the direction shift function D to the opposite way. For example, Rx in Vi will be converted to Rx-anti in Vi-1.According toVi-1 and Wij, the reversed process of data scramble and partial encryption can be executed. Then reorganize the scramble cube to segment and do the full encryption again with the previous segment. In this way, a segment is restored.Finally, all these segments are combined together to restore the original data object.


## 4.1. Definitions

Definition 1 (segment).
EPPA treats the original data object as byte stream and splits it into fixed length pieces, which are recorded as segment. Every byte of a segment is attached to the subsquare of Rubik’s cube. Therefore, each segment has6×n×n bytes.Definition 2 (scramble cube).
Scramble cube is ann×n×n Rubik’s cube that contains data from a segment on its surfaces. Data information on the cube will be scrambled by Rubik’s cube rotation. Figure 3 shows a 3 × 3 × 3 scramble cube with 54 bytes.Definition 3 (split cube).
Every three-dimensional cube can be unfolded by opening the cube from the Up direction square. Figure4 shows the flat pattern of an opened cube. Arranging all of the unfolded scramble cubes one by one as a cross-shaped cube, as shown in Figure 5, forms a split cube. Figure 6 indicates a split cube combined by three unfolded scramble cubes, and each unfolded scramble cube is parallel to YOZ coordinate plane.Figure 4
Unfolded 3 × 3 × 3 scramble cube.Figure 5
Unfolded scramble cube arrange method.Figure 6
A split cube with 3 unfolded scramble cubes.Definition 4 (fragment).
Fragment is the data piece made by split cube. The subcubes with red color in Figure6 composed a typical fragment. EPPA divides original data objects into 6×n×n fragments.


## 4.2. Algorithm Details

Figure7 shows the details of EPPA, which is mainly combined by two-phase process.Figure 7
EPPA progress.In the first phase, original data objects are split into segments. Then this segment is organized as ann×n×n scramble cube.Two mapping rules, which are XOR table mapping and rotation method table mapping, are used to map the sequences that are created by logistic map according to XOR table and rotation method tables.Every scramble cube carries outr round rotations. Each round executes two operations, which are data encryption and scramble. According to XOR tables, the shifted subsquares are XORed to implement data encryption. Besides, on the basis of the rotation method tables, the data information covered on the subsquares of the scramble cubes may be scrambled several times based on the principles of Rubik’s cubes rotations. In this phase, the original data is encrypted and scrambled, and thus the former semantics becomes meaningless. However, data information still has locality feature. Therefore, the locality feature will be broken in the next phase.In the second phase, all of the scrambled Rubik’s cubes are unfolded and combined together as a cross-shaped cube, which will be split into fragments to guarantee that every fragment does not contain continuous bytes. At last, these fragments will be stored, respectively, on randomly chosen servers of cloud storage system. In this phase, data object is split and recombined to break the data locality feature, so that malicious users cannot parse any semantics information even if they only obtain some fragments.


### 4.2.1. Initialization

EPPA needs users to choose the split parameters. Then the system can figure out the scramble method. The split parameters that need to be determined are as follows:(i)
the size of Rubik’s cube isn×n×n, n≥3;(ii)
the initial value of logistic map isx00∈(0,1);(iii)
the size of rotation round isr.Users can choosen based on the need of fragments’ number, which is 6×n×n.


### 4.2.2. First Phase

The first phase is composed by segment chaining andr round transformation. Every round transformation has two operations, which are data encryption and data scramble based on the rotation of scramble cube.(
1) Segment Chaining. In this step, when segment Si finishes its rotation round, it will be XORed with segment Si+1. After that, segment Si+1 can start its own rotation round. A sequence with 6×n×n element is created by using formula (1) iteratively with initial value of logistic map x00, whose element is uniformly partitioned and mapped to integers within {0,…,255}. It can be treated as segment S0 to complete segment chaining with segment S1.(
2) Mapping Rules. EPPA leverages logistic map to create XOR table and rotation method table for every scramble cube. Formula (10) is defined to generate a sequence by using formula (1) iteratively:
(10)Xi=xi1,xi2,…,xir.Parameteri∈{1,…,N/(6×n×n)} that represents this sequence is prepared for the ith scramble cube, which is created from the last element xi-1r in Xi-1 by formula (1). Parameter r indicates the size of rotation round.Since the output of logistic mapXn belongs to [0,1], discretization is essential process to map Xn to Rubik’s cube rotation policy and replace schedule. As a result, the logistic map is scaled so that input and output values of the map are in the interval. Meanwhile, the scaled logistic map is discretized. Two mapping functions of rotation method vector mapping and replacing table mapping rules are needed to achieve target.(a) XOR Table Mapping. Since EPPA uses XOR operation to encrypt data information, a XOR element set can be indicated as {0,1,2,…,255}. Because every segment has 6×n×n bytes data, a sequence with 6×n×n elements is needed and will be mapped to the element within {0,…,255} to complete XOR operation.When in thejth round rotation of Rubik’s cube, xij is used as initial value to generate r different logistic sequence Xij={xij1,xij2,…,xij6×n×n}, j=1,2,…,r, by formula (1). Then the XOR table can be created by the mapping function below:
(11)Wij=MWXij=floor4xij1-xij×256.FunctionMW maps every element in sequence Xij to an integer that in the range {0,…,255}. Then the XOR table Wij={w1,w2,…,w6×n×n} is constructed.(b) Rotation Method Table Mapping. As n×n×n Rubik’s cube has three axes, and every axis has two rotation directions, which are clockwise and anticlockwise, there will be 2×3×n basic rotation methods. A rotation tuple (ma, R, D) is defined to represent a rotation method, in which parameter m∈{1,…,n} means themth row or column perpendicular to a(a∈{x,y,z}) axis, parameter R means the state transition matrix, and parameter D means the direction shift function.So a rotation method set with6×n element can be described as {(1x,Rx,Dx), (1x,Rx-anti,Dx-anti), (2x,Rx,Dx),…,(nx,Rx-anti,Dx-anti), (1y,Ry,Dy), (1x,Ry-anti,Dy-anti),…,(ny,Ry-anti,Dy-anti), (1z,Rz,Dz), (1z,Rz-anti,Dz-anti),…, (nz,Rz-anti,Dz-anti)}.Therefore, a random sequence, whose elements are integral numbers within[1, 6×n], is needed in order to map numbers to the 6×n different rotation methods.Rotation method vector mapping function for each scramble cube is created as follows:(12)Vi=MVXi,
where i∈{1,…,N/(6×n×n)}, N means the number of bytes of original data object. MV maps every element in Xi to an integer that in the range [1, 6×n] and then maps the integers to the rotation method set. In this way, the rotation method table Vi={v1,v2,…,vr} is constructed. Every element in Vi is a rotation tuple (ma, R, D). Since every segment is treated as a scramble cube, which may be rotated several times based on the rotation methods table, the scramble cube can be rotated several times. As a result, the segments are scrambled.(
3) Round Transformation. After generating scramble cube from segment Si, rotation method table Vi={v1,v2,…,vr} can be created by rotation method table mapping, and XOR table Wij={w1,w2,…,w6×n×n}, j=1,2,…,r, can be created by XOR table mapping. According to vj and Wij, j=1,2,…,r, data encryption and scramble can be described as follows.(a) Data Encryption. Let Bj,k, k=1,2,…,6×n×n denote every byte in one segment. On the basis of XOR table Wij={w1,w2,…,w6×n×n}, the partial encryption is given with
(13)Bj,2=Bj-1,1⊕f0Bj,3=Bj-1,2⊕f1⋮Bj,0=Bj-1,6×n×n⊕f6×n×n-1Bj,1=Bj-1,0⊕f6×n×n,
where the functions fk have the following form:
(14)fk=Bj-1,1⊕⋯⊕Bj-1,k⊕wj,k.(b) Data Scramble. Scramble cube can be regarded as a normal Rubik’s cube with 6×n×n bytes data attached to the surface of it. Since vj is a rotation tuple (ma, R, D), which indicates three element of rotation, sub-cube’s position shift and sub-square’s orientation shift can be done following these three element.In the fact that every subsquare of the scramble cube is covered by one byte data, at least4n byte data will be scrambled in one round.


### 4.2.3. Second Phase

At the beginning of the second phase, each scramble cube still has its own six squares, but the bytes on the squares have changed. Then all of the scrambled cubes are unfolded and combined together as a new split cube like Figure5 shown, which will be split into 6×n×n fragments in the direction vertical to YOZ coordinate plane. The sub-cube with red color in Figure 6 indicates a typical fragment. At last, every fragment contains one byte from each segment. These fragments will be sent to the randomly chosen servers. The location and order information of fragments will be recorded in the fragment index.


## 4.2.1. Initialization

EPPA needs users to choose the split parameters. Then the system can figure out the scramble method. The split parameters that need to be determined are as follows:(i)
the size of Rubik’s cube isn×n×n, n≥3;(ii)
the initial value of logistic map isx00∈(0,1);(iii)
the size of rotation round isr.Users can choosen based on the need of fragments’ number, which is 6×n×n.


## 4.2.2. First Phase

The first phase is composed by segment chaining andr round transformation. Every round transformation has two operations, which are data encryption and data scramble based on the rotation of scramble cube.(
1) Segment Chaining. In this step, when segment Si finishes its rotation round, it will be XORed with segment Si+1. After that, segment Si+1 can start its own rotation round. A sequence with 6×n×n element is created by using formula (1) iteratively with initial value of logistic map x00, whose element is uniformly partitioned and mapped to integers within {0,…,255}. It can be treated as segment S0 to complete segment chaining with segment S1.(
2) Mapping Rules. EPPA leverages logistic map to create XOR table and rotation method table for every scramble cube. Formula (10) is defined to generate a sequence by using formula (1) iteratively:
(10)Xi=xi1,xi2,…,xir.Parameteri∈{1,…,N/(6×n×n)} that represents this sequence is prepared for the ith scramble cube, which is created from the last element xi-1r in Xi-1 by formula (1). Parameter r indicates the size of rotation round.Since the output of logistic mapXn belongs to [0,1], discretization is essential process to map Xn to Rubik’s cube rotation policy and replace schedule. As a result, the logistic map is scaled so that input and output values of the map are in the interval. Meanwhile, the scaled logistic map is discretized. Two mapping functions of rotation method vector mapping and replacing table mapping rules are needed to achieve target.(a) XOR Table Mapping. Since EPPA uses XOR operation to encrypt data information, a XOR element set can be indicated as {0,1,2,…,255}. Because every segment has 6×n×n bytes data, a sequence with 6×n×n elements is needed and will be mapped to the element within {0,…,255} to complete XOR operation.When in thejth round rotation of Rubik’s cube, xij is used as initial value to generate r different logistic sequence Xij={xij1,xij2,…,xij6×n×n}, j=1,2,…,r, by formula (1). Then the XOR table can be created by the mapping function below:
(11)Wij=MWXij=floor4xij1-xij×256.FunctionMW maps every element in sequence Xij to an integer that in the range {0,…,255}. Then the XOR table Wij={w1,w2,…,w6×n×n} is constructed.(b) Rotation Method Table Mapping. As n×n×n Rubik’s cube has three axes, and every axis has two rotation directions, which are clockwise and anticlockwise, there will be 2×3×n basic rotation methods. A rotation tuple (ma, R, D) is defined to represent a rotation method, in which parameter m∈{1,…,n} means themth row or column perpendicular to a(a∈{x,y,z}) axis, parameter R means the state transition matrix, and parameter D means the direction shift function.So a rotation method set with6×n element can be described as {(1x,Rx,Dx), (1x,Rx-anti,Dx-anti), (2x,Rx,Dx),…,(nx,Rx-anti,Dx-anti), (1y,Ry,Dy), (1x,Ry-anti,Dy-anti),…,(ny,Ry-anti,Dy-anti), (1z,Rz,Dz), (1z,Rz-anti,Dz-anti),…, (nz,Rz-anti,Dz-anti)}.Therefore, a random sequence, whose elements are integral numbers within[1, 6×n], is needed in order to map numbers to the 6×n different rotation methods.Rotation method vector mapping function for each scramble cube is created as follows:(12)Vi=MVXi,
where i∈{1,…,N/(6×n×n)}, N means the number of bytes of original data object. MV maps every element in Xi to an integer that in the range [1, 6×n] and then maps the integers to the rotation method set. In this way, the rotation method table Vi={v1,v2,…,vr} is constructed. Every element in Vi is a rotation tuple (ma, R, D). Since every segment is treated as a scramble cube, which may be rotated several times based on the rotation methods table, the scramble cube can be rotated several times. As a result, the segments are scrambled.(
3) Round Transformation. After generating scramble cube from segment Si, rotation method table Vi={v1,v2,…,vr} can be created by rotation method table mapping, and XOR table Wij={w1,w2,…,w6×n×n}, j=1,2,…,r, can be created by XOR table mapping. According to vj and Wij, j=1,2,…,r, data encryption and scramble can be described as follows.(a) Data Encryption. Let Bj,k, k=1,2,…,6×n×n denote every byte in one segment. On the basis of XOR table Wij={w1,w2,…,w6×n×n}, the partial encryption is given with
(13)Bj,2=Bj-1,1⊕f0Bj,3=Bj-1,2⊕f1⋮Bj,0=Bj-1,6×n×n⊕f6×n×n-1Bj,1=Bj-1,0⊕f6×n×n,
where the functions fk have the following form:
(14)fk=Bj-1,1⊕⋯⊕Bj-1,k⊕wj,k.(b) Data Scramble. Scramble cube can be regarded as a normal Rubik’s cube with 6×n×n bytes data attached to the surface of it. Since vj is a rotation tuple (ma, R, D), which indicates three element of rotation, sub-cube’s position shift and sub-square’s orientation shift can be done following these three element.In the fact that every subsquare of the scramble cube is covered by one byte data, at least4n byte data will be scrambled in one round.


## 4.2.3. Second Phase

At the beginning of the second phase, each scramble cube still has its own six squares, but the bytes on the squares have changed. Then all of the scrambled cubes are unfolded and combined together as a new split cube like Figure5 shown, which will be split into 6×n×n fragments in the direction vertical to YOZ coordinate plane. The sub-cube with red color in Figure 6 indicates a typical fragment. At last, every fragment contains one byte from each segment. These fragments will be sent to the randomly chosen servers. The location and order information of fragments will be recorded in the fragment index.


## 4.3. Data Restoration Process

The restoration process is the opposite way as follows.Firstly, the second phase is redone in an opposite way to get the split cube. Based on the location and order information of fragments, all of the fragments can be combined together exactly to get the split cube.Secondly, all of the scramble cubes are restored by dividing the split cube in the direction parallel toYOZ coordinate plane. Then calculate the rotation method table Vi={v1,v2,…,vr} and XOR table Wij={w1,w2,…,w6×n×n} (i={1,2,…,N/(6×n×n)}, j=1,2,…,r) using the initial value of logistic map, which is input by user.Thirdly, carry out the first phase of EPPA in an opposite way from the last segment to the first one. In every round, the reverse rotation method table with reverse direction is represented as follows:(15)Vi-1=v1-1,v2-1,…,vr-1.V
i
-
1 is converted from Vi by changing the state transition matrix R and the direction shift function D to the opposite way. For example, Rx in Vi will be converted to Rx-anti in Vi-1.According toVi-1 and Wij, the reversed process of data scramble and partial encryption can be executed. Then reorganize the scramble cube to segment and do the full encryption again with the previous segment. In this way, a segment is restored.Finally, all these segments are combined together to restore the original data object.


## 5. Evaluation

A series of analyses and experiments are designed to analyze the efficiency of EPPA. The experiments are run on a computer with Intel core 2 Duo 2.93 GHz processer and 2 GB RAM. In these experiments, the initial value of logistic map is randomly chosen.


### 5.1. Safe Threshold

Safe threshold algorithms can be characterized by three parameters(p,m,n), which means in ap-m-n threshold scheme, data object is encoded into n shares such that any m of the shares can reconstruct data object and less than p reveals no information about the encoded data. EPPA, IDA, and secret sharing all belong to safe threshold algorithms.Both of IDA and secret sharing encode data inton shares and need just m shares to reconstruct the original data object, so attackers have the opportunity to reconstruct data object with m shares. Besides, IDA will breach the confidentiality while the attackers get only one share.The original data object is split inton shares in EPPA, which can be reconstructed only if the attackers get all of the shares and encryption key. Though data information of each fragment comes from the original data object, it is useless until the attackers reconstruct the whole data object.


### 5.2. Key Sensibility Analysis and Key Space Analysis

While the size of Rubik’s cube is chosen, every segment can be considered as a fixed-length group of bits. Therefore, EPPA can be considered as a block encryption algorithm operating on these groups of bits with an unvarying transformation that is specified by a symmetric key. According to the Strict Avalanche Criterion, a small change in either the key or the plaintext should cause a drastic change in the ciphertext.Figure8 shows the percentage of changed cipher text in different rotation round and different size of Rubik’s cube, when the initial value of logistic map changes 1 × 10−10. The results indicate that a small change in the initial value will cause a drastic change in the ciphertext. This result means that when a new initial value of logistic map changes 1 × 10−10, it can be considered as a new key.Figure 8
Key sensibility.Because the cipher text created by EPPA contributes very little to the key, EPPA can resist statistical attack. According to the result in Figure8, the key space of EPPA is determined by the following parameters.


#### 5.2.1. Initial Value of Logistic Map

It is a double-precision floating-point format value. Due to the limitation of the accuracy of computer, the computational accuracy of logistic map is 10−10 in the experiments.


#### 5.2.2. The Combination Order of Fragments

Suppose that the attacker gets all fragments. Since the number of fragments needed to reconstruct the whole split cubes is6×n×n, n≥3, there will be (6×n×n)! kinds of ways to make all the bytes into cubes.In conclusion, the total size of key space should be(16)1010×6×n×n!.If 3 × 3 × 3 Rubik’s cube is chosen, the size of key space will be 1010  × 54! ≈ 2.3 × 1081. Correspondingly, while 4 × 4 × 4 Rubik’s cube is chosen, the size of key space will be 1010 × 96! ≈ 9.9 × 10159.As(6×n×n)! will become extremely huge while n increased, the total size of key space increases sharply while choosing larger cube. As a result, the brute force attack is impossible for EPPA, because even if the attacker uses one thousand servers in the cloud environment and every server executes one billion exhaustive search attacks in a second, it may still cost him 7.3 × 1061 years while 3 × 3 × 3 Rubik’s cube is chosen.


### 5.3. Linear Cryptanalysis and Differential Cryptanalysis

The linear cryptanalysis and the differential cryptanalysis are two essential methods of cryptanalysis. Differential cryptanalysis is up to now one of the most efficient attacks known for iterating cryptography [37]. The differential cryptanalysis belongs to the known plaintext attack. Its basic idea is that we analyze how the difference between a pair of plaintext influences the difference between a pair of cipher to recover certain key bits.EPPA’s differential approximate probability (DP) and linear approximate probability (LP) can be described, respectively, as follows:(17)DP≤DPrCO×RM,LP≤LPrCO×RM.DP
r and LPr indicate differential approximate probability and linear approximate probability of r round transformation, respectively. CO denotes the combination order of fragments, while RM denotes the scramble cubes’ rotation method.Jakimoski and Kocarev [16] have proposed that the functionf’s differential approximate probability (DPf) in a block encryption algorithm is 2−5 < DPf = 12/256 < 2−4, and its linear approximate probability (LPf) is LPf = 2−4. Reference [16] has also proven that 11 round transformations’ differential (linear) track at least contains 17 chaos sequences in the block encryption algorithm. In EPPA, the round-transformation time isr, which leads to that r round transformation contains (r×17)/11 chaos sequences at least, so DPr = (2−4.678)(r×17)/11 and LPr = (2−4.678)(r×17)/11.However, the attacker also needs the combination order of the6×n×n fragments and the scramble cubes’ rotation method to get the original data information.LetNSC∣n×n×n represent the pattern space of the n×n×n scramble cube. For example, as the 3 × 3 × 3 Rubik’s cube has eight corners and twelve edges, there are 8! ways to arrange the corner cubes. Seven can be oriented independently, and the orientation of the eighth depends on the preceding seven, giving 37 possibilities. There are 12!/2 ways to arrange the edges, since an even permutation of the corners implies an even permutation of the edges as well. Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones, giving 211 possibilities. As a result, the size of pattern space of a 3 × 3 × 3 scramble cube is NSC∣3×3×3 = 8! × 37 × 12!/2 × 211 ≈ 4.3 × 1019. Another size scramble cube’s pattern space, such as NSC∣4×4×4, can be figured out in the same way. Since NSC∣n×n×n is really large, using exhaustive search attack on the scramble cubes’ rotation methods will be the choice when r is small. As one scramble cube has 6×n rotation methods, RM=6×nr.Since there will be(6×n×n)! kinds of ways to make all the bytes into cubes, CO=(6×n×n)!. As a result, DP and LP can be described, respectively, as follows:
(18)DP≤2-4.678(r×17)/11(6×n×n)!×6×nr,LP≤2-4(r×17)/11(6×n×n)!×6×nr.So ifn=3 and r=10 are chosen, the results of DP and LP, respectively, are
(19)DP≈2-351,LP≈2-340.Based on Jakimoski and Kocarev’s research, it is impossible to construct the differential (linear) characteristic of the block encryption algorithm. This means the differential or the linear cryptanalysis cannot decipher the information generated by this algorithm.


### 5.4. Memory Cost Analysis

A three-dimensional array is used to represent the subcube’s position, so the rotation of cube can work by matrix operations. The value of every element in the array is an object, which contains one-byte data and another byte that used to represent the subsquare’s direction. Therefore, only2×6×n×n bytes are needed to represent one scramble cube. If 5 × 5 × 5 scramble cube is chosen, EPPA only needs 300 bytes to represent one scramble cube. Since the iterative calculations also need little memory, EPPA is really cost effective on memory occupation.


### 5.5. Time Cost Analysis

#### 5.5.1. Time Cost in Different Situation

Figure9 shows the time cost of EPPA under different size data and different size of scramble cube while rotation round r=5. The time cost of EPPA declines, when the bigger size of scramble cube is chosen.Figure 9
Time cost of EPPA under different size of scramble cube while rotation round isr=5.Figure10 indicates the time cost of EPPA under different size data and different rotation round size while 5 × 5 × 5 scramble cube is chosen. The time cost of EPPA increases along with the rotation round.Figure 10
Time cost of EPPA under different rotation round while 5 × 5 × 5 scramble cube is chosen.These two figures all indicate that EPPA takes liner time to process data object.


#### 5.5.2. Time Cost Compared with AES and DES

Encrypt algorithm library called soft crypto, which is a kind of software cryptographic algorithm library, is used in the experiments. The comparison between EPPA and AES and DES by processing different size of data and calculating the time cost of processing is carried out. These encryption algorithms are widely used.Figure11 compares split time cost by EPPA with AES and DES. These experiments choose 5 × 5 × 5 scramble cube with rotation transformation r=5.Figure 11
Time cost comparison of EPPA, AES, and DES.Statistics indicate that EPPA with 5 × 5 × 5 scramble cube are faster than AES-128, but slower than DES. AES-128’s encryption time is almost 7 times as EPPA (n=5, r=5). However, the time cost of DES is only 0.75 times as EPPA (n=5, r=5).


## 5.1. Safe Threshold

Safe threshold algorithms can be characterized by three parameters(p,m,n), which means in ap-m-n threshold scheme, data object is encoded into n shares such that any m of the shares can reconstruct data object and less than p reveals no information about the encoded data. EPPA, IDA, and secret sharing all belong to safe threshold algorithms.Both of IDA and secret sharing encode data inton shares and need just m shares to reconstruct the original data object, so attackers have the opportunity to reconstruct data object with m shares. Besides, IDA will breach the confidentiality while the attackers get only one share.The original data object is split inton shares in EPPA, which can be reconstructed only if the attackers get all of the shares and encryption key. Though data information of each fragment comes from the original data object, it is useless until the attackers reconstruct the whole data object.


## 5.2. Key Sensibility Analysis and Key Space Analysis

While the size of Rubik’s cube is chosen, every segment can be considered as a fixed-length group of bits. Therefore, EPPA can be considered as a block encryption algorithm operating on these groups of bits with an unvarying transformation that is specified by a symmetric key. According to the Strict Avalanche Criterion, a small change in either the key or the plaintext should cause a drastic change in the ciphertext.Figure8 shows the percentage of changed cipher text in different rotation round and different size of Rubik’s cube, when the initial value of logistic map changes 1 × 10−10. The results indicate that a small change in the initial value will cause a drastic change in the ciphertext. This result means that when a new initial value of logistic map changes 1 × 10−10, it can be considered as a new key.Figure 8
Key sensibility.Because the cipher text created by EPPA contributes very little to the key, EPPA can resist statistical attack. According to the result in Figure8, the key space of EPPA is determined by the following parameters.


### 5.2.1. Initial Value of Logistic Map

It is a double-precision floating-point format value. Due to the limitation of the accuracy of computer, the computational accuracy of logistic map is 10−10 in the experiments.


### 5.2.2. The Combination Order of Fragments

Suppose that the attacker gets all fragments. Since the number of fragments needed to reconstruct the whole split cubes is6×n×n, n≥3, there will be (6×n×n)! kinds of ways to make all the bytes into cubes.In conclusion, the total size of key space should be(16)1010×6×n×n!.If 3 × 3 × 3 Rubik’s cube is chosen, the size of key space will be 1010  × 54! ≈ 2.3 × 1081. Correspondingly, while 4 × 4 × 4 Rubik’s cube is chosen, the size of key space will be 1010 × 96! ≈ 9.9 × 10159.As(6×n×n)! will become extremely huge while n increased, the total size of key space increases sharply while choosing larger cube. As a result, the brute force attack is impossible for EPPA, because even if the attacker uses one thousand servers in the cloud environment and every server executes one billion exhaustive search attacks in a second, it may still cost him 7.3 × 1061 years while 3 × 3 × 3 Rubik’s cube is chosen.


## 5.2.1. Initial Value of Logistic Map

It is a double-precision floating-point format value. Due to the limitation of the accuracy of computer, the computational accuracy of logistic map is 10−10 in the experiments.


## 5.2.2. The Combination Order of Fragments

Suppose that the attacker gets all fragments. Since the number of fragments needed to reconstruct the whole split cubes is6×n×n, n≥3, there will be (6×n×n)! kinds of ways to make all the bytes into cubes.In conclusion, the total size of key space should be(16)1010×6×n×n!.If 3 × 3 × 3 Rubik’s cube is chosen, the size of key space will be 1010  × 54! ≈ 2.3 × 1081. Correspondingly, while 4 × 4 × 4 Rubik’s cube is chosen, the size of key space will be 1010 × 96! ≈ 9.9 × 10159.As(6×n×n)! will become extremely huge while n increased, the total size of key space increases sharply while choosing larger cube. As a result, the brute force attack is impossible for EPPA, because even if the attacker uses one thousand servers in the cloud environment and every server executes one billion exhaustive search attacks in a second, it may still cost him 7.3 × 1061 years while 3 × 3 × 3 Rubik’s cube is chosen.


## 5.3. Linear Cryptanalysis and Differential Cryptanalysis

The linear cryptanalysis and the differential cryptanalysis are two essential methods of cryptanalysis. Differential cryptanalysis is up to now one of the most efficient attacks known for iterating cryptography [37]. The differential cryptanalysis belongs to the known plaintext attack. Its basic idea is that we analyze how the difference between a pair of plaintext influences the difference between a pair of cipher to recover certain key bits.EPPA’s differential approximate probability (DP) and linear approximate probability (LP) can be described, respectively, as follows:(17)DP≤DPrCO×RM,LP≤LPrCO×RM.DP
r and LPr indicate differential approximate probability and linear approximate probability of r round transformation, respectively. CO denotes the combination order of fragments, while RM denotes the scramble cubes’ rotation method.Jakimoski and Kocarev [16] have proposed that the functionf’s differential approximate probability (DPf) in a block encryption algorithm is 2−5 < DPf = 12/256 < 2−4, and its linear approximate probability (LPf) is LPf = 2−4. Reference [16] has also proven that 11 round transformations’ differential (linear) track at least contains 17 chaos sequences in the block encryption algorithm. In EPPA, the round-transformation time isr, which leads to that r round transformation contains (r×17)/11 chaos sequences at least, so DPr = (2−4.678)(r×17)/11 and LPr = (2−4.678)(r×17)/11.However, the attacker also needs the combination order of the6×n×n fragments and the scramble cubes’ rotation method to get the original data information.LetNSC∣n×n×n represent the pattern space of the n×n×n scramble cube. For example, as the 3 × 3 × 3 Rubik’s cube has eight corners and twelve edges, there are 8! ways to arrange the corner cubes. Seven can be oriented independently, and the orientation of the eighth depends on the preceding seven, giving 37 possibilities. There are 12!/2 ways to arrange the edges, since an even permutation of the corners implies an even permutation of the edges as well. Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones, giving 211 possibilities. As a result, the size of pattern space of a 3 × 3 × 3 scramble cube is NSC∣3×3×3 = 8! × 37 × 12!/2 × 211 ≈ 4.3 × 1019. Another size scramble cube’s pattern space, such as NSC∣4×4×4, can be figured out in the same way. Since NSC∣n×n×n is really large, using exhaustive search attack on the scramble cubes’ rotation methods will be the choice when r is small. As one scramble cube has 6×n rotation methods, RM=6×nr.Since there will be(6×n×n)! kinds of ways to make all the bytes into cubes, CO=(6×n×n)!. As a result, DP and LP can be described, respectively, as follows:
(18)DP≤2-4.678(r×17)/11(6×n×n)!×6×nr,LP≤2-4(r×17)/11(6×n×n)!×6×nr.So ifn=3 and r=10 are chosen, the results of DP and LP, respectively, are
(19)DP≈2-351,LP≈2-340.Based on Jakimoski and Kocarev’s research, it is impossible to construct the differential (linear) characteristic of the block encryption algorithm. This means the differential or the linear cryptanalysis cannot decipher the information generated by this algorithm.


## 5.4. Memory Cost Analysis

A three-dimensional array is used to represent the subcube’s position, so the rotation of cube can work by matrix operations. The value of every element in the array is an object, which contains one-byte data and another byte that used to represent the subsquare’s direction. Therefore, only2×6×n×n bytes are needed to represent one scramble cube. If 5 × 5 × 5 scramble cube is chosen, EPPA only needs 300 bytes to represent one scramble cube. Since the iterative calculations also need little memory, EPPA is really cost effective on memory occupation.


## 5.5. Time Cost Analysis

### 5.5.1. Time Cost in Different Situation

Figure9 shows the time cost of EPPA under different size data and different size of scramble cube while rotation round r=5. The time cost of EPPA declines, when the bigger size of scramble cube is chosen.Figure 9
Time cost of EPPA under different size of scramble cube while rotation round isr=5.Figure10 indicates the time cost of EPPA under different size data and different rotation round size while 5 × 5 × 5 scramble cube is chosen. The time cost of EPPA increases along with the rotation round.Figure 10
Time cost of EPPA under different rotation round while 5 × 5 × 5 scramble cube is chosen.These two figures all indicate that EPPA takes liner time to process data object.


### 5.5.2. Time Cost Compared with AES and DES

Encrypt algorithm library called soft crypto, which is a kind of software cryptographic algorithm library, is used in the experiments. The comparison between EPPA and AES and DES by processing different size of data and calculating the time cost of processing is carried out. These encryption algorithms are widely used.Figure11 compares split time cost by EPPA with AES and DES. These experiments choose 5 × 5 × 5 scramble cube with rotation transformation r=5.Figure 11
Time cost comparison of EPPA, AES, and DES.Statistics indicate that EPPA with 5 × 5 × 5 scramble cube are faster than AES-128, but slower than DES. AES-128’s encryption time is almost 7 times as EPPA (n=5, r=5). However, the time cost of DES is only 0.75 times as EPPA (n=5, r=5).


## 5.5.1. Time Cost in Different Situation

Figure9 shows the time cost of EPPA under different size data and different size of scramble cube while rotation round r=5. The time cost of EPPA declines, when the bigger size of scramble cube is chosen.Figure 9
Time cost of EPPA under different size of scramble cube while rotation round isr=5.Figure10 indicates the time cost of EPPA under different size data and different rotation round size while 5 × 5 × 5 scramble cube is chosen. The time cost of EPPA increases along with the rotation round.Figure 10
Time cost of EPPA under different rotation round while 5 × 5 × 5 scramble cube is chosen.These two figures all indicate that EPPA takes liner time to process data object.


## 5.5.2. Time Cost Compared with AES and DES

Encrypt algorithm library called soft crypto, which is a kind of software cryptographic algorithm library, is used in the experiments. The comparison between EPPA and AES and DES by processing different size of data and calculating the time cost of processing is carried out. These encryption algorithms are widely used.Figure11 compares split time cost by EPPA with AES and DES. These experiments choose 5 × 5 × 5 scramble cube with rotation transformation r=5.Figure 11
Time cost comparison of EPPA, AES, and DES.Statistics indicate that EPPA with 5 × 5 × 5 scramble cube are faster than AES-128, but slower than DES. AES-128’s encryption time is almost 7 times as EPPA (n=5, r=5). However, the time cost of DES is only 0.75 times as EPPA (n=5, r=5).


## 6. Conclusions

EPPA is presented to provide data privacy preserving for cloud storage environments, which can be used as a security algorithm to encrypt and partition original data object into fragments. EPPA strengthens the confidentiality of data in two phases. Data object is the original data which is encrypted and scrambled at the first phase, and thus the former semantics becomes meaningless. At the second phase, data object is partitioned to break the data locality feature, so that malicious users cannot parse any semantics information even if they obtain some continuous fragments. Analysis proves that the confidentiality of EPPA is useable. Moreover, experiments show that EPPA has decent run-time efficiency.



---

*Source: 178585-2014-11-27.xml*