# Privacy-Preserving Sorting Algorithms Based on Logistic Map for Clouds

Authors: Hua Dai; Hui Ren; Zhiye Chen; Geng Yang; Xun Yi
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Outsourcing data in clouds is adopted by more and more companies and individuals due to the profits from data sharing and parallel, elastic, and on-demand computing. However, it forces data owners to lose control of their own data, which causes privacy-preserving problems on sensitive data. Sorting is a common operation in many areas, such as machine learning, service recommendation, and data query. It is a challenge to implement privacy-preserving sorting over encrypted data without leaking privacy of sensitive data. In this paper, we propose privacy-preserving sorting algorithms which are on the basis of the logistic map. Secure comparable codes are constructed by logistic map functions, which can be utilized to compare the corresponding encrypted data items even without knowing their plaintext values. Data owners firstly encrypt their data and generate the corresponding comparable codes and then outsource them to clouds. Cloud servers are capable of sorting the outsourced encrypted data in accordance with their corresponding comparable codes by the proposed privacy-preserving sorting algorithms. Security analysis and experimental results show that the proposed algorithms can protect data privacy, while providing efficient sorting on encrypted data.


---

## Body

## 1. Introduction

With the profits from data sharing and parallel, elastic, and on-demand computing, clouds are becoming more and more popular with companies and individuals. Many kinds of services are provided by cloud service providers (CSP), such as Amazon EC2 and Alibaba Cloud. As one of the most important technologies, machine learning is very useful and wildly adopted in many areas, such as prediction [1, 2] and multimedia data processing [3, 4]. And it usually utilizes huge data volume, such as wireless multimedia data and human health data, to build intelligent models and systems for practical applications. Due to the need of large and elastic scale of storage and computing resources, those huge volume data are usually processed in clouds [5–7]. Data owner (DO) outsources their data in the cloud server (CS) for on-demand services which enhance the efficiency of complex computation such as machine learning and save the hardware/software cost.However, in the cloud environment, DO lose direct control of their own data placed in remote CS, which may cause concerns about their outsourced data being illegally acquired or abused by CSPs, especially for sensitive data, such as national defence data and human health data. Although many CSPs claim that they deployed several safety measures in CS, such as access control, firewalls, or intrusion detection, doubts about the privacy of outsourced data obstruct the promotion and application of cloud computing. How to preserve the security and privacy of DO’s outsourced data while CS providing reliable and efficient computing services has become a hot issue [8–10].Data encryption is a common technique to protect the privacy of outsourced data on clouds, such as sensitive wireless multimedia data and human health data. Sorting is one of the basic methods in practical applications, such as machine learning, service recommending, and data query. However, applying to sort over encrypt data on clouds is a challenge without leaking private information. The existing privacy-preserving sorting algorithms based on order-preserved encryption (OPE) [11–14] have security problems [15]. In addition, privacy-preserving sorting algorithms based on fully homomorphic encryption (FHE) [16–19] are too slow because of the complexity of FHE. It is significant to research the efficient privacy-preserving sorting algorithms for clouds.In this paper, we assume that the honest-but-curious threat model [20] is adopted where CS strictly abides by established protocols but has the curiosity to snoop on DO’s private data. On the basis of the threat model, we propose privacy-preserving sorting algorithms based on the logistic map. The main contributions of this paper are as follows. Firstly, by introducing the logistic map, we propose a secure comparison model which can be utilized to compare data without knowing their real values. Secondly, we give a data preprocessing algorithm. Data owners preprocess their private data by a symmetric encryption and logistic map. The encrypted data and corresponding comparable codes are generated and then outsourced to clouds, where the former is to protect data privacy, while the latter is to support secure comparisons. Finally, on the basis of secure comparison model, we propose privacy-preserving sorting algorithms for clouds. Also, security analysis and performance experiment are given, where results show that the proposed algorithms can protect data privacy from curious cloud administrators while providing efficient sorting on encrypted data.The paper is organized as follows. Section2 describes the related work. Section 3 gives the problem descriptions. Section 4 gives notations and necessary preliminaries. In Section 5, we firstly present secure comparison model on the basis of the logistic map, and then the data preprocessing algorithm and privacy-preserving sorting algorithms are given. Section 6 analyzes the security of our schemes. Section 7 gives evaluations on correctness, correlation coefficient, and performance of our proposed schemes.


## 2. Related Works

There are two kinds of methods achieving encrypted data sorting on clouds, one is sorting algorithms based on order-preserving encryption (OPE) [11–14], and the other is sorting algorithms based on fully homomorphic encryption [16–19].Agrawal et al. [11] originally proposed an OPE method which is a deterministic encryption scheme whose encryption function preserves numerical ordering of the plaintext. Due to the unachievable of the indistinguishability against chosen-plaintext attack (IND-CPA) in [11], Boldyreva et al. proposed an efficient OPE scheme [12] which is based on a natural relation between a random order-preserving function and the hypergeometric probability distribution. Jaiman et al. [13] proposed an OPE algorithm by introducing shuffling, impurity insertion, and randomness in order-preserving functions. Liu et al. [14] propose a new OPE model which uses message space expansion and nonlinear space split to hide data distribution and frequency. Any proposed OPE is clearly suitable for application of privacy-preserving sorting in clouds if the data security is ensured. However, OPE is vulnerable to ciphertext-only attack [15], especially when encrypted data are massive. Therefore, those sorting algorithms based on OPE have potential security risks.Gentry et al. [21] proposed the fully homomorphic encryption (FHE) which is a special encryption algorithm which allows computation (such as addition and multiplication) on the ciphertext. Melchor et al. [16] give an idea about sorting encrypted data by FHE. Chatterjee et al. [17] propose the sorting algorithm over encrypted data on the basis of FHE. They tried to get higher sorting efficiency by reducing costs of reencryption. Afterwards, they applied the algorithm to clouds [18, 19]. The volume of encrypted data generated by FHE is very large, due to the inclusion of big floating-point numbers which take the place of numerous storage space. Thus, the calculation of comparison for sorting based on FHE is very complex and its time efficiency is also very slow. Since the fully homomorphic encryption based sorting requires CS to reencrypt data frequently, it is not suitable for storing and managing big data on clouds.To support efficiency and privacy in sorting algorithms for cloud environments, we propose logistic map based privacy-preserving sorting algorithms in this paper, the abstract of which has been shown in [22].


## 3. Problem Description

The model of the privacy-preserving sorting for clouds, proposed in this paper, is similar to recent works [18, 19]. It mainly consists of two entities, data owner (DO) and cloud server (CS). The interactions between DO and CS are introduced as follows: firstly, DO encrypts its sensitive data and generates corresponding codes which are used for privacy-preserving sorting. Then DO outsources the encrypted data and codes to CS. Secondly, CS stores the data uploaded by DO and performs data sorting over the received data. Any proved secure symmetric encryption could be adopted, such as DES and AES. If authorized users want to access DO’s sensitive data, they can get the encrypted data from CS and perform decryption to obtain the plaintext data by using the shared key with DO.In this paper, we assume that CS provides services following the curious-but-honest threat model [20]. CS is assumed to strictly follow the established protocols, but it attempts to snoop on DO’s private data. There are two kinds of attacks: (1) CS has already known DO’s preprocessing algorithms but does not know its initial parameters, and it tries to use exhaustive attacks against to encrypted data for plaintext information; (2) because of the massive quantity of outsourced encrypted data, statistical attacks are common methods for CS to analyze the distribution of ciphertext and speculate on the relationship between the ciphertext and plaintext to obtain plaintext information.We focus on privacy-preserving sorting for clouds, and the key issues of this paper are introduced as follows: (1) privacy protection on outsourced data: DO preprocesses its plaintext data to keep it in confidential. Thus, CS cannot obtain DO’s plaintext information via the outsourced data; (2) privacy-preserving sorting on encrypted data: if a symmetric encryption algorithm is adopted, the privacy is guaranteed, but the encrypted data is hard for data sorting. Therefore, privacy-preserving sorting algorithms have to support sorting on encrypted data even without knowing the values.


## 4. Preliminaries and Notations

### 4.1. Preliminaries

Chaos theory [23, 24] originated in the 1960s, which has been widely adopted in medicine, astrophysics, image encryption, and hydromechanics. The basic characteristic of chaotic motion is extremely sensitive to the initial value. The difference between two chaotic motions with different initial values will become larger and larger over time. Therefore, on the basis of any given initial conditions, the chaotic motion is unpredictable.Logistic map [25–27] is one of the important and practical chaotic motions and has been widely used in data encryption [28–32]. The equation of the logistic map is shown as(1)Lx,n=μ·Lx,n-1·1-Lx,n-1n>1xn=1,where x∈[0,1], μ∈[0,4] is called bifurcation parameter, and n is the iteration number. Studies [25–27] show that the sequence generated from (1) is chaotic if μ∈(3.5699456,4]. The output of such logistic map is extremely sensitive to the initial parameters. Any minor changes of initial parameters will lead to a tremendous difference of outputs. Therefore, the sequences generated by the logistic map are unpredictable.


### 4.2. Notations

The notations used in this paper are described as shown in Table1.Table 1
Notation descriptions.
Notations Descriptions μ The bifurcation parameter of the logistic map function. n The iteration number of the logistic map function. t The constraint factor where0<t<x/(2⋅μn) L ( t / x , n ) The logistic mapping function. d i A plaintext data item of DO. k The key of a symmetric encryption which is only owned by DO. E n c ( x , k ) The encryption function where x is the input plaintext data and k is a key. g i A secure data pair after data preprocessing ondi, gi=(e,c), where gi.e=Enc(di,k) and gi.c=L(t/x,n) are the corresponding encrypted data and logistic mapping codes of di.


## 4.1. Preliminaries

Chaos theory [23, 24] originated in the 1960s, which has been widely adopted in medicine, astrophysics, image encryption, and hydromechanics. The basic characteristic of chaotic motion is extremely sensitive to the initial value. The difference between two chaotic motions with different initial values will become larger and larger over time. Therefore, on the basis of any given initial conditions, the chaotic motion is unpredictable.Logistic map [25–27] is one of the important and practical chaotic motions and has been widely used in data encryption [28–32]. The equation of the logistic map is shown as(1)Lx,n=μ·Lx,n-1·1-Lx,n-1n>1xn=1,where x∈[0,1], μ∈[0,4] is called bifurcation parameter, and n is the iteration number. Studies [25–27] show that the sequence generated from (1) is chaotic if μ∈(3.5699456,4]. The output of such logistic map is extremely sensitive to the initial parameters. Any minor changes of initial parameters will lead to a tremendous difference of outputs. Therefore, the sequences generated by the logistic map are unpredictable.


## 4.2. Notations

The notations used in this paper are described as shown in Table1.Table 1
Notation descriptions.
Notations Descriptions μ The bifurcation parameter of the logistic map function. n The iteration number of the logistic map function. t The constraint factor where0<t<x/(2⋅μn) L ( t / x , n ) The logistic mapping function. d i A plaintext data item of DO. k The key of a symmetric encryption which is only owned by DO. E n c ( x , k ) The encryption function where x is the input plaintext data and k is a key. g i A secure data pair after data preprocessing ondi, gi=(e,c), where gi.e=Enc(di,k) and gi.c=L(t/x,n) are the corresponding encrypted data and logistic mapping codes of di.


## 5. Privacy-Preserving Sorting Algorithms

### 5.1. Secure Comparison Model Based on Logistic Map

The chaos characteristic of the logistic map can be used to compare data values secretly under certain conditions. Current work such as [28–32] mainly focuses on data encryption with logistic map algorithms, but there is no literature discussing the secure comparison of encrypted data with the logistic map.If we use the logistic map for data comparison directly, then we may get wrong comparison results during sorting. But if proper constraint factors are introduced in the logistic map, we will get correct compare results invariably. The main idea of the proposed secure comparison model based on the logistic map is briefly given by three lemmas as follows.Lemma 1.
For any given datax, where x≥1, t/x is settled as the initial value for the logistic map function, i.e., (1), where t is the constraint factor, where 0<t<x/(2·μn) and μ∈(3.5699456,4]. Then we have(2)0<Ltx,n<12.Proof.
We use mathematical inductions to prove Lemma1 as follows.
(1) Whenn=1, according to (1), we have(3)Ltx,1=tx.According to the given assumptions 0<t<x/(2·μ) and μ∈(3.5699456,4], we have 0<L(t/x,1)<1/(2·μ), and then 0<L(t/x,1)<1/2 is deduced.
(2) Whenn=2, according to (1), we have(4)Ltx,2=μ·Ltx,1·1-Ltx,1.According to the conclusion of (1), we have 1/2 < 1-L(t/x, 1) < 1 and L(t/x,1)>0. In addition, because of μ∈(3.5699456,4], then we deduce that(5)0<Ltx,2<μ·Ltx,1.According to the given assumption 0<t<x/(2·μ2) when n=2 and the deduced result L(t/x,1)=t/x in (3), we deduce (6) from (5), where(6)0<Ltx,2<μ2·μ2.Due to μ∈(3.5699456,4], then we have that 0<L(t/x,2)<1/2 holds.
(3) We assume that Lemma1 holds when n=k, i.e., 0<L(t/x,k)<1/2. According to the assumption 0<t<x/(2·μn) and the deduced result L(t/x,1)=t/x in (3), we have(7)0<Ltx,1<12·μk.
Whenn=k+1, according to (1), we have(8)Ltx,k+1=μ·Ltx,k·1-Ltx,k=μ2·Ltx,k-1·1-Ltx,k-1·1-Ltx,k=μk·Ltx,1·1-Ltx,1⋯1-Ltx,k-1·1-Ltx,k.According to the assumption of (3), i.e., 0<L(t/x,k)<1/2, we have(9)1-Ltx,1⋯1-Ltx,k-1·1-Ltx,k<1.On the basis of (7), (8), and (9), we have(10)Ltx,k+1=μk·Ltx,1·1-Ltx,1⋯1-Ltx,k-1·1-Ltx,k<μk·Ltx,1<μk·12·μk.Therefore, we have that L(t/x,k+1)<1/2 holds.
According to the above mathematical induction proofs, we have that Lemma1 holds.Lemma 2.
For any given datax and y, where 1≤x≤y, let t/x and t/y as initial values for the logistic map function, i.e., (1), and the nth iteration results are L(t/x,n) and L(t/y,n), respectively, then we have(11)Ltx,n≥Lty,n,where 0<t<x/(2·μn), μ∈(3.5699456,4], and x≥1.Proof.
We also use mathematical inductions to prove Lemma2 as follows.
(1) Whenn=1, according to (1), we have(12)Ltx,1=txand(13)Lty,1=ty.After applying subtraction between L(t/x,1) and L(t/y,1), we have (14)Ltx,1-Lty,1=tx-ty.Since 1≤x≤y and 0<t<x/(2·μ) are given conditions when n=1, we can easily deduce(15)Ltx,1-Lty,1=tx-ty≥0.Therefore, L(t/x,1)≥L(t/y,1) holds.
(2) Whenn=2, according to (1), we have (16)Ltx,2=μ·tx·1-txand(17)Lty,2=μ·ty·1-ty.After applying subtraction between L(t/x,2) and L(t/y,2), we have(18)Ltx,2-Lty,2=μ·tx·1-tx-μ·ty·1-ty=μ·tx-μ·tx2-μ·ty+μ·ty2=μ·tx-ty-μ·tx+ty·tx-ty=μ·tx-ty·1-tx+ty.In accordance with the given conditions 1≤x≤y, 0<t<x/(2·μn), n=2 and μ∈(3.5699456,4], we have(19)0<ty≤tx≤12·μ2<12.Then we have (20)tx-ty≥0and (21)1-tx+ty>0.According to (18), (20), and (21), we deduce that(22)Ltx,2-Lty,2=μ·tx-ty·1-tx+ty≥0.Therefore, L(t/x,2)≥L(t/y,2) holds.
(3) We assume that Lemma2 holds when n=k; then we have(23)Ltx,k≥Lty,k.
Whenn=k+1, according to (1), we have(24)Ltx,k+1=μ·Ltx,k·1-Ltx,kand (25)Lty,k+1=μ·Lty,k·1-Lty,k.After applying subtraction between L(t/x,k+1) and L(t/y,k+1), we have(26)Ltx,k+1-Lty,k+1=μ·Ltx,k-Lty,k·1-Ltx,k-Lty,k.According to Lemma 1, we have 0<L(t/x,k+1) < 1/2 and 0<L(t/y,k+1) < 1/2; then we deduce(27)0<1-Ltx,k-Lty,k<1.According to (7), (23), and (27) and the given condition μ∈(3.5699456,4], then we have(28)Ltx,k+1-Lty,k+1≥0.Therefore, L(t/x,k+1)≥L(t/y,k+1) holds.
According to the above mathematical induction proofs, we have that Lemma2 holds.Definition 3.
For a given data itemxi>1, L(t/xi,n) is denoted as the correspondingcomparable code of xi, where L(∗) is the logistic map function as (1).Lemma 4.
For a given data setX={x1,x2,…,xm}, where xi>1 and i∈1,2,…,m, we can get the corresponding comparable codes set Y={y1,y2,…,ym}, where yi=L(t/xi,n). Then we have(29)xi≤xj⟷yi≥yj,where xi∈X and xj∈X.Proof.
To prove Lemma4, we have to prove the sufficiency and necessity of Lemma 4, respectively, i.e., xi≤xj→yi≥yj and yi≥yj→xi≤xj.
(Sufficiency) According to Lemma2, we can easily deduce yi ≥ yj when xi ≤ xj, where yi =L(t/xi,n) and yj=L(t/xj,n). The sufficiency of Lemma 4 is proved.
(Necessity) We prove the necessity of Lemma4 by contradiction. Assuming that xi > xj holds when yi ≥ yj, where yi =L(t/xi,n) and yj =L(t/xj,n); then we haveL(t/xi,n) <L(t/xj,n) according to Lemma 2, i.e., yi < yj. It is obvious that the derivation is inconsistent with the given hypothesis yi ≥ yj. Therefore, if we have yi ≥ yj, where yi=L(t/xi,n) and yj=L(t/xj,n), then xi ≤ xj holds.
In accordance with the sufficiency and necessity proofs, we have that Lemma4 holds.According to Lemma4, the computation of comparable is order-preserving reversely with the increasing of input data. For any two real numbers both larger than 1, we can achieve the comparison by comparing their corresponding comparable codes. Obviously, such comparison does not need to know the real values of them. If the given real numbers are less than 1, they are still comparable by using our proposed secure comparison model based on the logistic map. For example, if they are less than -1, the corresponding absolute values will be bigger than 1. And if they are between -1 and 1, by adding the constant number 2, then the result data will be also bigger than 1. Therefore, any two real numbers can be compared. As a result, we have that the proposed secure comparison model based on the logistic map is capable of performing data comparison without knowing their corresponding values. In order to describe conveniently, we focus on the data larger than 1 in the subsequent chapters.On the basis of secure comparison model, the privacy-preserving sorting mechanism is proposed in the next sections, including the data preprocessing algorithm and privacy-preserving sorting algorithm. The brief flowchart of our proposed work is shown in Figure1.Figure 1
The brief flowchart of privacy-preserving sorting for clouds.


### 5.2. Data Preprocessing Algorithm

DO preprocesses its outsourced data with encryption and logistic map in order to protect private data from CS and support privacy-preserving sorting in CS. We use a symmetric encryption algorithm such as DES and AES to preserve data privacy and the logistic map is utilized to generate comparable codes for secure comparison.We assume that the outsourced data of DO are{d1,d2,…,dm}. After data preprocessing, a data pair gi = (e,c) will be generated for di, where gi.e and gi.c are the corresponding encrypted data and comparable code of di. In addition, we assume that k is a private key, while μ and n are bifurcation parameter and number of iterations of the logistic map function, respectively. And k, μ, and n are all owned by DO privately. The data preprocessing algorithm based on the logistic map (DP-LM) is shown in Algorithm 1.Algorithm 1: DP-LM(d1,d2,…,dm).
Begin (1) t=rand(0,min({d1,d2,…,dm})/(2⋅μn)); (2) FOR  di∈d1,d2,…,dm  DO (3)  Create a data pair gi for di; (4)  gi.e=Enc(di,k);  //generate encrypted data (5)  gi.c=L(t/di,n);  //generate comparable code (6) END FOR (7) Upload and outsource g1,g2,…,gm to CS; ENDIn Algorithm1, rand(0,x) is to randomly pick a float number between 0 and x, min(S) is to get the minimum of the set S, Enc(di,k) is to encrypt di with private key k by a symmetric encryption, and L(∗) is a logistic map function as (1). After finishing data preprocess, the generated data pairs will be uploaded and outsourced to CS.


### 5.3. Privacy-Preserving Sorting Algorithm

Privacy-preserving sorting is performed in CS after receiving the outsourced data from DO. Obviously, traditional sorting algorithms (e.g., merge sort, quicksort, and heap sort) cannot solve the problem of sorting encrypted data items, but by introducing the proposed secure comparison model, the encrypted data will be sorted by using the corresponding comparable codes.We give the privacy-preserving quick sorting algorithm based on the logistic map (PQS-LM) for sorting over encrypted data in CS. The specific implementation of PQS-LM is shown in Algorithm2.Algorithm 2: PQS-LM(g1,g2,…,gm, start, end).
Begin (1) IF  start < endTHEN (2)i = start, j = end +1; (3)WHILE TRUE DO (4)WHILE  i<end∧gstart.c<gi.c  DO (5)i++; (6)END WHILE (7)WHILE  j>start∧gj.c<gstart.c  DO (8)j--; (9)END WHILE (10)IF  i<j  THEN (11)Swap(gi,gj); (12)ELSE (13)Finish the current loop and start the next loop; (14)END IF (15)END WHILE (16)Swap(gj,gstart); (17)PQS-LM({g1,g2,…,gm}, start, j-1); (18)PQS-LM({g1,g2,…,gm}, j+1, end); (19) END IF ENDIn Algorithms2, Swap(x,y) is to swap the positions of elements x and y. The comparable codes are compared during sorting procedures, and the number of comparisons determines the efficiency of sorting. The complexity of the comparison based on our proposed model is equivalent to the comparison of plaintext. Therefore, the time complexity of PQS-LM is O(m·log2⁡m).Other classic sorting algorithms, such as merge sorting and heap sorting, can also be improved to be the corresponding privacy-preserving sorting algorithms as Algorithm2 on the basis of the proposed secure comparison model. We denote the privacy-preserving merge sorting and heap sorting as PMS-LM and PHS-LM, respectively. Because the implementation ideas are similar to PQS-LM, we omit the details of those algorithms. The analysis and performance evaluations of our proposed privacy-preserving sorting algorithms will be given in the latter sections.


## 5.1. Secure Comparison Model Based on Logistic Map

The chaos characteristic of the logistic map can be used to compare data values secretly under certain conditions. Current work such as [28–32] mainly focuses on data encryption with logistic map algorithms, but there is no literature discussing the secure comparison of encrypted data with the logistic map.If we use the logistic map for data comparison directly, then we may get wrong comparison results during sorting. But if proper constraint factors are introduced in the logistic map, we will get correct compare results invariably. The main idea of the proposed secure comparison model based on the logistic map is briefly given by three lemmas as follows.Lemma 1.
For any given datax, where x≥1, t/x is settled as the initial value for the logistic map function, i.e., (1), where t is the constraint factor, where 0<t<x/(2·μn) and μ∈(3.5699456,4]. Then we have(2)0<Ltx,n<12.Proof.
We use mathematical inductions to prove Lemma1 as follows.
(1) Whenn=1, according to (1), we have(3)Ltx,1=tx.According to the given assumptions 0<t<x/(2·μ) and μ∈(3.5699456,4], we have 0<L(t/x,1)<1/(2·μ), and then 0<L(t/x,1)<1/2 is deduced.
(2) Whenn=2, according to (1), we have(4)Ltx,2=μ·Ltx,1·1-Ltx,1.According to the conclusion of (1), we have 1/2 < 1-L(t/x, 1) < 1 and L(t/x,1)>0. In addition, because of μ∈(3.5699456,4], then we deduce that(5)0<Ltx,2<μ·Ltx,1.According to the given assumption 0<t<x/(2·μ2) when n=2 and the deduced result L(t/x,1)=t/x in (3), we deduce (6) from (5), where(6)0<Ltx,2<μ2·μ2.Due to μ∈(3.5699456,4], then we have that 0<L(t/x,2)<1/2 holds.
(3) We assume that Lemma1 holds when n=k, i.e., 0<L(t/x,k)<1/2. According to the assumption 0<t<x/(2·μn) and the deduced result L(t/x,1)=t/x in (3), we have(7)0<Ltx,1<12·μk.
Whenn=k+1, according to (1), we have(8)Ltx,k+1=μ·Ltx,k·1-Ltx,k=μ2·Ltx,k-1·1-Ltx,k-1·1-Ltx,k=μk·Ltx,1·1-Ltx,1⋯1-Ltx,k-1·1-Ltx,k.According to the assumption of (3), i.e., 0<L(t/x,k)<1/2, we have(9)1-Ltx,1⋯1-Ltx,k-1·1-Ltx,k<1.On the basis of (7), (8), and (9), we have(10)Ltx,k+1=μk·Ltx,1·1-Ltx,1⋯1-Ltx,k-1·1-Ltx,k<μk·Ltx,1<μk·12·μk.Therefore, we have that L(t/x,k+1)<1/2 holds.
According to the above mathematical induction proofs, we have that Lemma1 holds.Lemma 2.
For any given datax and y, where 1≤x≤y, let t/x and t/y as initial values for the logistic map function, i.e., (1), and the nth iteration results are L(t/x,n) and L(t/y,n), respectively, then we have(11)Ltx,n≥Lty,n,where 0<t<x/(2·μn), μ∈(3.5699456,4], and x≥1.Proof.
We also use mathematical inductions to prove Lemma2 as follows.
(1) Whenn=1, according to (1), we have(12)Ltx,1=txand(13)Lty,1=ty.After applying subtraction between L(t/x,1) and L(t/y,1), we have (14)Ltx,1-Lty,1=tx-ty.Since 1≤x≤y and 0<t<x/(2·μ) are given conditions when n=1, we can easily deduce(15)Ltx,1-Lty,1=tx-ty≥0.Therefore, L(t/x,1)≥L(t/y,1) holds.
(2) Whenn=2, according to (1), we have (16)Ltx,2=μ·tx·1-txand(17)Lty,2=μ·ty·1-ty.After applying subtraction between L(t/x,2) and L(t/y,2), we have(18)Ltx,2-Lty,2=μ·tx·1-tx-μ·ty·1-ty=μ·tx-μ·tx2-μ·ty+μ·ty2=μ·tx-ty-μ·tx+ty·tx-ty=μ·tx-ty·1-tx+ty.In accordance with the given conditions 1≤x≤y, 0<t<x/(2·μn), n=2 and μ∈(3.5699456,4], we have(19)0<ty≤tx≤12·μ2<12.Then we have (20)tx-ty≥0and (21)1-tx+ty>0.According to (18), (20), and (21), we deduce that(22)Ltx,2-Lty,2=μ·tx-ty·1-tx+ty≥0.Therefore, L(t/x,2)≥L(t/y,2) holds.
(3) We assume that Lemma2 holds when n=k; then we have(23)Ltx,k≥Lty,k.
Whenn=k+1, according to (1), we have(24)Ltx,k+1=μ·Ltx,k·1-Ltx,kand (25)Lty,k+1=μ·Lty,k·1-Lty,k.After applying subtraction between L(t/x,k+1) and L(t/y,k+1), we have(26)Ltx,k+1-Lty,k+1=μ·Ltx,k-Lty,k·1-Ltx,k-Lty,k.According to Lemma 1, we have 0<L(t/x,k+1) < 1/2 and 0<L(t/y,k+1) < 1/2; then we deduce(27)0<1-Ltx,k-Lty,k<1.According to (7), (23), and (27) and the given condition μ∈(3.5699456,4], then we have(28)Ltx,k+1-Lty,k+1≥0.Therefore, L(t/x,k+1)≥L(t/y,k+1) holds.
According to the above mathematical induction proofs, we have that Lemma2 holds.Definition 3.
For a given data itemxi>1, L(t/xi,n) is denoted as the correspondingcomparable code of xi, where L(∗) is the logistic map function as (1).Lemma 4.
For a given data setX={x1,x2,…,xm}, where xi>1 and i∈1,2,…,m, we can get the corresponding comparable codes set Y={y1,y2,…,ym}, where yi=L(t/xi,n). Then we have(29)xi≤xj⟷yi≥yj,where xi∈X and xj∈X.Proof.
To prove Lemma4, we have to prove the sufficiency and necessity of Lemma 4, respectively, i.e., xi≤xj→yi≥yj and yi≥yj→xi≤xj.
(Sufficiency) According to Lemma2, we can easily deduce yi ≥ yj when xi ≤ xj, where yi =L(t/xi,n) and yj=L(t/xj,n). The sufficiency of Lemma 4 is proved.
(Necessity) We prove the necessity of Lemma4 by contradiction. Assuming that xi > xj holds when yi ≥ yj, where yi =L(t/xi,n) and yj =L(t/xj,n); then we haveL(t/xi,n) <L(t/xj,n) according to Lemma 2, i.e., yi < yj. It is obvious that the derivation is inconsistent with the given hypothesis yi ≥ yj. Therefore, if we have yi ≥ yj, where yi=L(t/xi,n) and yj=L(t/xj,n), then xi ≤ xj holds.
In accordance with the sufficiency and necessity proofs, we have that Lemma4 holds.According to Lemma4, the computation of comparable is order-preserving reversely with the increasing of input data. For any two real numbers both larger than 1, we can achieve the comparison by comparing their corresponding comparable codes. Obviously, such comparison does not need to know the real values of them. If the given real numbers are less than 1, they are still comparable by using our proposed secure comparison model based on the logistic map. For example, if they are less than -1, the corresponding absolute values will be bigger than 1. And if they are between -1 and 1, by adding the constant number 2, then the result data will be also bigger than 1. Therefore, any two real numbers can be compared. As a result, we have that the proposed secure comparison model based on the logistic map is capable of performing data comparison without knowing their corresponding values. In order to describe conveniently, we focus on the data larger than 1 in the subsequent chapters.On the basis of secure comparison model, the privacy-preserving sorting mechanism is proposed in the next sections, including the data preprocessing algorithm and privacy-preserving sorting algorithm. The brief flowchart of our proposed work is shown in Figure1.Figure 1
The brief flowchart of privacy-preserving sorting for clouds.


## 5.2. Data Preprocessing Algorithm

DO preprocesses its outsourced data with encryption and logistic map in order to protect private data from CS and support privacy-preserving sorting in CS. We use a symmetric encryption algorithm such as DES and AES to preserve data privacy and the logistic map is utilized to generate comparable codes for secure comparison.We assume that the outsourced data of DO are{d1,d2,…,dm}. After data preprocessing, a data pair gi = (e,c) will be generated for di, where gi.e and gi.c are the corresponding encrypted data and comparable code of di. In addition, we assume that k is a private key, while μ and n are bifurcation parameter and number of iterations of the logistic map function, respectively. And k, μ, and n are all owned by DO privately. The data preprocessing algorithm based on the logistic map (DP-LM) is shown in Algorithm 1.Algorithm 1: DP-LM(d1,d2,…,dm).
Begin (1) t=rand(0,min({d1,d2,…,dm})/(2⋅μn)); (2) FOR  di∈d1,d2,…,dm  DO (3)  Create a data pair gi for di; (4)  gi.e=Enc(di,k);  //generate encrypted data (5)  gi.c=L(t/di,n);  //generate comparable code (6) END FOR (7) Upload and outsource g1,g2,…,gm to CS; ENDIn Algorithm1, rand(0,x) is to randomly pick a float number between 0 and x, min(S) is to get the minimum of the set S, Enc(di,k) is to encrypt di with private key k by a symmetric encryption, and L(∗) is a logistic map function as (1). After finishing data preprocess, the generated data pairs will be uploaded and outsourced to CS.


## 5.3. Privacy-Preserving Sorting Algorithm

Privacy-preserving sorting is performed in CS after receiving the outsourced data from DO. Obviously, traditional sorting algorithms (e.g., merge sort, quicksort, and heap sort) cannot solve the problem of sorting encrypted data items, but by introducing the proposed secure comparison model, the encrypted data will be sorted by using the corresponding comparable codes.We give the privacy-preserving quick sorting algorithm based on the logistic map (PQS-LM) for sorting over encrypted data in CS. The specific implementation of PQS-LM is shown in Algorithm2.Algorithm 2: PQS-LM(g1,g2,…,gm, start, end).
Begin (1) IF  start < endTHEN (2)i = start, j = end +1; (3)WHILE TRUE DO (4)WHILE  i<end∧gstart.c<gi.c  DO (5)i++; (6)END WHILE (7)WHILE  j>start∧gj.c<gstart.c  DO (8)j--; (9)END WHILE (10)IF  i<j  THEN (11)Swap(gi,gj); (12)ELSE (13)Finish the current loop and start the next loop; (14)END IF (15)END WHILE (16)Swap(gj,gstart); (17)PQS-LM({g1,g2,…,gm}, start, j-1); (18)PQS-LM({g1,g2,…,gm}, j+1, end); (19) END IF ENDIn Algorithms2, Swap(x,y) is to swap the positions of elements x and y. The comparable codes are compared during sorting procedures, and the number of comparisons determines the efficiency of sorting. The complexity of the comparison based on our proposed model is equivalent to the comparison of plaintext. Therefore, the time complexity of PQS-LM is O(m·log2⁡m).Other classic sorting algorithms, such as merge sorting and heap sorting, can also be improved to be the corresponding privacy-preserving sorting algorithms as Algorithm2 on the basis of the proposed secure comparison model. We denote the privacy-preserving merge sorting and heap sorting as PMS-LM and PHS-LM, respectively. Because the implementation ideas are similar to PQS-LM, we omit the details of those algorithms. The analysis and performance evaluations of our proposed privacy-preserving sorting algorithms will be given in the latter sections.


## 6. Security Analysis

There are two types of data outsourced in CS. One is the encrypted data generated by a symmetric encryption, and the other is the comparable code generated by the logistic map. The former is to protect data privacy, while the latter is to support secure comparisons. For encrypted data, it has an identical security level with the adopted symmetric encryption. For comparable codes generated by the logistic map, we conduct security analysis as follows.(1) Space of initial parameters: the data preprocessing algorithm in this paper is based on a logistic chaotic system. The corresponding parameters are initialized before preprocessing, including the number of iterationsn, the constraint factor t, and the bifurcation parameter μ. We assume that the attacker uses an exhaustive attack against the initial parameters. The precision of t and μ is assumed to be 10-p and 10-q, respectively. The space of initial parameters is 10p+q•n. For example, if we take p=32, q=32 and randomly pick n from the interval [1,1000], then the space of initial parameters is 1067. It is computation infeasible to commit successful attacks by using exhaustive search in such a large space.(2) Sensitivity of initial parameters: since the sequence generated by the logistic map is extremely sensitive to initial parameters, any small modification of them leads to completely different results. For example, we take the sameμ and n, where μ = 3.95362 and n=3, while we take two different constraint factors which are very close to each other, such as t1=1 × 10−8 and t2=2 × 10−8. For the real number 11, we will get two completely different comparable codes L(t1/11,3) = 5.62 × 10−8 and L(t2/11,3) = 1.12 × 10−7.(3) Antistatistic ability: the logistic map has good cryptographic properties such as sensitivity to initial parameters, driven by white noise, unpredictability, etc. [31]. Even if an attacker obtains some statistic information about the input data and the corresponding comparable codes, he or she still cannot get configurations of initial parameters. Lots of simulation cases show that the data generated by the logistic map with different initial parameters are in equi-distribution [29, 32] which can prevent statistical attacks. In addition, we will give the correlation coefficient evaluation in the next section to analyze the antistatistic ability quantitatively.As a result, we have that our proposed algorithms can support sorting over encrypted data while preserving data privacy.


## 7. Experiments

In this section, we give the correctness, correlation coefficient, and performance evaluations of our proposed method. The experimental datasets are generated by a random number generator. The software environment of the experiment is Windows 10 and NetBeans 8, and the hardware environment is Core i5 5200U and 8 GB DDR3 RAM.


### 7.1. Correctness Evaluation on Secure Comparison Model

We proposed the secure comparison model which is on the basis of the logistic map. It is the foundation of achieving the privacy-preserving sorting algorithms. Theoretical proofs are given to prove the correctness of the secure comparison model in the above sections, such as the proofs in Lemmas1, 2, and 4. Additionally, we give the correctness evaluation on the proposed model by quantitative experiments.In this evaluation, almost 100 thousand random numbers are generated as the input, and the corresponding comparable codes are calculated by the logistic map function with the initial parameter configuration asμ=3.67435, n=100, and t=0.423124/(2×μn). The diagram of the input data and the corresponding comparable codes are shown in Figure 2.Figure 2
Values of comparable codes versus input data.Figure2 shows that the values of comparable codes decrease along with the increasing of the input data values. It indicates that the comparable codes computation is with the order-preserving property which is consistent with the proposed conclusions of our proposed secure comparison model. Therefore, the experimental result has verified the correctness of the security comparison model quantitatively.


### 7.2. Correlation Coefficient Evaluation on Secure Comparison Model

We use the Pearson correlation coefficient formula [33] to analyze the correlation between the input data and the corresponding comparable codes generated in secure comparison model. The correlation coefficient formula is shown as(30)C=n·∑xi∈DSxi·Lt/xi,n-∑xi∈DSxi·∑xi∈DSLt/xi,nn·∑xi∈DSxi2-∑xi∈DSxi2·n·∑xi∈DSLt/xi,n2-∑xi∈DSLt/xi,n2,where xi andL(t/xi,n) are the input data and corresponding comparable codes, respectively, C is the correlation coefficient factor, and DS is the evaluated dataset. We calculate correlation coefficients on the basis of five datasets which are generated by a random number generator, and the results are shown in Table 2.Table 2
Correlation coefficients of random datasets.
Dataset ID Dataset scale Average correlation coefficient 1 1000 -0.156 2 5000 -0.110 3 9000 -0.087 4 13000 -0.066 5 17000 -0.068According to the result of Table2, we can see that the average correlation coefficient decreases with the increasing of dataset scales. And the average correlation coefficient is very small which indicates that the correlation between the input data and corresponding comparable codes is negligible. Therefore, our proposed secure comparison model is with the antistatistic ability.


### 7.3. Performance Evaluation on Algorithms

We implement our proposed logistic map-based data preprocessing and privacy-preserving sorting algorithms. To make comparisons with related works, we adopt the classic Boldyreva’s order-preserving symmetric encryption (OPE) [12] to implement privacy-preserving sorting, which is more secure than [11] and more efficient than [13, 14]. We denote the OPE based data preprocessing as DP-OPE and denote the OPE based privacy-preserving quick sorting, merge sorting, and heap sorting algorithms as PQS-OPE, PMS-OPE, and PHS-OPE, respectively. Then we evaluate and compare the time cost performance of those algorithms.It is noticeable that there are fully homomorphic encryption (FHE) based privacy-preserving sorting schemes proposed in [18, 19]. But they are too slow because of the complexity of FHE. The experiments of them show that thousands of seconds are consumed even sorting only 40 encrypted data items. Thus, we do not choose them to implement performance comparisons.


#### 7.3.1. Evaluation on Time Cost of Data Preprocessing

The time cost of DP-OPE and DP-LM is evaluated on the basis of five given datasets. The experimental result is shown in Table3.Table 3
The time cost of data preprocessing (ms).
Dataset scale DP-OPE DP-LM 1000 1194.39 4.35 5000 4036.15 14.36 9000 6930.81 20.05 13000 10411.12 35.91 17000 14178.67 58.01Table3 shows that the time costs of DP-LM and DP-OPE are both increasing along with the expansion of datasets, but DP-LM is obviously much faster than DP-OPE. The reason is given as follows. DP-OPE needs to execute order-preserving encryption for plaintext by mapping amount of consecutive integers in a domain to integers in a much larger range. Each integer is assigned a pseudorandom value in its subrange. The OPE algorithm recursively bisects the range and samples from the domain at each recursion until it hits the input plaintext value. Thus, the calculation load of OPE is higher relatively which makes DP-OPE much slower than DP-LM.


#### 7.3.2. Evaluation on Time Cost of Data Sorting

We also use the same datasets to evaluate the privacy-preserving sorting algorithms based on the logistic map and OPE. The result is shown in Table4.Table 4
The time cost of privacy-preserving algorithms (ms).
Dataset scale Privacy-preserving Privacy-preserving Privacy-preserving quick sorting merge sorting heap sorting PQS-LM PQS-OPE PMS-LM PMS-OPE PHS-LM PHS-OPE 1000 0.63 0.65 0.76 0.81 0.74 0.75 5000 1.02 1.55 5.45 6.31 2.35 3.31 9000 3.15 4.23 7.23 7.85 3.19 4.12 13000 3.91 4.41 8.03 9.47 3.92 4.65 17000 4.65 5.01 11.75 12.31 5.31 5.45The experimental result in Table4 shows that the performance of our proposed privacy-preserving sorting algorithms is better than those sorting algorithms based on OPE, respectively. The reason is that the output data of OPE, which is used for privacy-preserving sorting, is more complex than the comparable codes generated by the logistic map.


## 7.1. Correctness Evaluation on Secure Comparison Model

We proposed the secure comparison model which is on the basis of the logistic map. It is the foundation of achieving the privacy-preserving sorting algorithms. Theoretical proofs are given to prove the correctness of the secure comparison model in the above sections, such as the proofs in Lemmas1, 2, and 4. Additionally, we give the correctness evaluation on the proposed model by quantitative experiments.In this evaluation, almost 100 thousand random numbers are generated as the input, and the corresponding comparable codes are calculated by the logistic map function with the initial parameter configuration asμ=3.67435, n=100, and t=0.423124/(2×μn). The diagram of the input data and the corresponding comparable codes are shown in Figure 2.Figure 2
Values of comparable codes versus input data.Figure2 shows that the values of comparable codes decrease along with the increasing of the input data values. It indicates that the comparable codes computation is with the order-preserving property which is consistent with the proposed conclusions of our proposed secure comparison model. Therefore, the experimental result has verified the correctness of the security comparison model quantitatively.


## 7.2. Correlation Coefficient Evaluation on Secure Comparison Model

We use the Pearson correlation coefficient formula [33] to analyze the correlation between the input data and the corresponding comparable codes generated in secure comparison model. The correlation coefficient formula is shown as(30)C=n·∑xi∈DSxi·Lt/xi,n-∑xi∈DSxi·∑xi∈DSLt/xi,nn·∑xi∈DSxi2-∑xi∈DSxi2·n·∑xi∈DSLt/xi,n2-∑xi∈DSLt/xi,n2,where xi andL(t/xi,n) are the input data and corresponding comparable codes, respectively, C is the correlation coefficient factor, and DS is the evaluated dataset. We calculate correlation coefficients on the basis of five datasets which are generated by a random number generator, and the results are shown in Table 2.Table 2
Correlation coefficients of random datasets.
Dataset ID Dataset scale Average correlation coefficient 1 1000 -0.156 2 5000 -0.110 3 9000 -0.087 4 13000 -0.066 5 17000 -0.068According to the result of Table2, we can see that the average correlation coefficient decreases with the increasing of dataset scales. And the average correlation coefficient is very small which indicates that the correlation between the input data and corresponding comparable codes is negligible. Therefore, our proposed secure comparison model is with the antistatistic ability.


## 7.3. Performance Evaluation on Algorithms

We implement our proposed logistic map-based data preprocessing and privacy-preserving sorting algorithms. To make comparisons with related works, we adopt the classic Boldyreva’s order-preserving symmetric encryption (OPE) [12] to implement privacy-preserving sorting, which is more secure than [11] and more efficient than [13, 14]. We denote the OPE based data preprocessing as DP-OPE and denote the OPE based privacy-preserving quick sorting, merge sorting, and heap sorting algorithms as PQS-OPE, PMS-OPE, and PHS-OPE, respectively. Then we evaluate and compare the time cost performance of those algorithms.It is noticeable that there are fully homomorphic encryption (FHE) based privacy-preserving sorting schemes proposed in [18, 19]. But they are too slow because of the complexity of FHE. The experiments of them show that thousands of seconds are consumed even sorting only 40 encrypted data items. Thus, we do not choose them to implement performance comparisons.


### 7.3.1. Evaluation on Time Cost of Data Preprocessing

The time cost of DP-OPE and DP-LM is evaluated on the basis of five given datasets. The experimental result is shown in Table3.Table 3
The time cost of data preprocessing (ms).
Dataset scale DP-OPE DP-LM 1000 1194.39 4.35 5000 4036.15 14.36 9000 6930.81 20.05 13000 10411.12 35.91 17000 14178.67 58.01Table3 shows that the time costs of DP-LM and DP-OPE are both increasing along with the expansion of datasets, but DP-LM is obviously much faster than DP-OPE. The reason is given as follows. DP-OPE needs to execute order-preserving encryption for plaintext by mapping amount of consecutive integers in a domain to integers in a much larger range. Each integer is assigned a pseudorandom value in its subrange. The OPE algorithm recursively bisects the range and samples from the domain at each recursion until it hits the input plaintext value. Thus, the calculation load of OPE is higher relatively which makes DP-OPE much slower than DP-LM.


### 7.3.2. Evaluation on Time Cost of Data Sorting

We also use the same datasets to evaluate the privacy-preserving sorting algorithms based on the logistic map and OPE. The result is shown in Table4.Table 4
The time cost of privacy-preserving algorithms (ms).
Dataset scale Privacy-preserving Privacy-preserving Privacy-preserving quick sorting merge sorting heap sorting PQS-LM PQS-OPE PMS-LM PMS-OPE PHS-LM PHS-OPE 1000 0.63 0.65 0.76 0.81 0.74 0.75 5000 1.02 1.55 5.45 6.31 2.35 3.31 9000 3.15 4.23 7.23 7.85 3.19 4.12 13000 3.91 4.41 8.03 9.47 3.92 4.65 17000 4.65 5.01 11.75 12.31 5.31 5.45The experimental result in Table4 shows that the performance of our proposed privacy-preserving sorting algorithms is better than those sorting algorithms based on OPE, respectively. The reason is that the output data of OPE, which is used for privacy-preserving sorting, is more complex than the comparable codes generated by the logistic map.


## 7.3.1. Evaluation on Time Cost of Data Preprocessing

The time cost of DP-OPE and DP-LM is evaluated on the basis of five given datasets. The experimental result is shown in Table3.Table 3
The time cost of data preprocessing (ms).
Dataset scale DP-OPE DP-LM 1000 1194.39 4.35 5000 4036.15 14.36 9000 6930.81 20.05 13000 10411.12 35.91 17000 14178.67 58.01Table3 shows that the time costs of DP-LM and DP-OPE are both increasing along with the expansion of datasets, but DP-LM is obviously much faster than DP-OPE. The reason is given as follows. DP-OPE needs to execute order-preserving encryption for plaintext by mapping amount of consecutive integers in a domain to integers in a much larger range. Each integer is assigned a pseudorandom value in its subrange. The OPE algorithm recursively bisects the range and samples from the domain at each recursion until it hits the input plaintext value. Thus, the calculation load of OPE is higher relatively which makes DP-OPE much slower than DP-LM.


## 7.3.2. Evaluation on Time Cost of Data Sorting

We also use the same datasets to evaluate the privacy-preserving sorting algorithms based on the logistic map and OPE. The result is shown in Table4.Table 4
The time cost of privacy-preserving algorithms (ms).
Dataset scale Privacy-preserving Privacy-preserving Privacy-preserving quick sorting merge sorting heap sorting PQS-LM PQS-OPE PMS-LM PMS-OPE PHS-LM PHS-OPE 1000 0.63 0.65 0.76 0.81 0.74 0.75 5000 1.02 1.55 5.45 6.31 2.35 3.31 9000 3.15 4.23 7.23 7.85 3.19 4.12 13000 3.91 4.41 8.03 9.47 3.92 4.65 17000 4.65 5.01 11.75 12.31 5.31 5.45The experimental result in Table4 shows that the performance of our proposed privacy-preserving sorting algorithms is better than those sorting algorithms based on OPE, respectively. The reason is that the output data of OPE, which is used for privacy-preserving sorting, is more complex than the comparable codes generated by the logistic map.


## 8. Conclusions

When the clouds provide outsourcing services, the privacy of outsourced data, such as national defence data and human health data, can be protected by common encryption. However, those encrypted data are useless for data sorting which is a common operation in many areas, such as machine learning, service recommending, and data query. It is a challenge to achieve privacy-preserving sorting in clouds. In this paper, we introduce a secure comparison model based on the logistic map and propose privacy-preserving sorting algorithms. The security analysis and experimental result show that the proposed algorithms can protect data privacy while providing efficient sorting on encrypted data.



---

*Source: 2373545-2018-09-04.xml*