# A Novel Secure Scheme for Supporting Complex SQL Queries over Encrypted Databases in Cloud Computing

Authors: Guoxiu Liu; Geng Yang; Huaqun Wang; Yang Xiang; Hua Dai
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the advance of database-as-a-service (DaaS) and cloud computing, increasingly more data owners are motivated to outsource their data to cloud database for great convenience and economic savings. Many encryption schemes have been proposed to process SQL queries over encrypted data in the database. In order to obtain the desired data, the SQL queries contain some statements to describe the requirement, e.g., arithmetic and comparison operators (+, -, ×, <, >, and =). However, to support different operators (+, -, ×, <, >, and =) in SQL queries over encrypted data, multiple encryption schemes need to be combined and adjusted to work together. Moreover, repeated encryptions will reduce the efficiency of execution. This paper presents a practical and secure homomorphic order-preserving encryption (FHOPE) scheme, which allows cloud server to perform complex SQL queries that contain different operators (such as addition, multiplication, order comparison, and equality checks) over encrypted data without repeated encryption. These operators are data interoperable, so they can be combined to formulate complex SQL queries. We conduct security analysis and efficiency evaluation of the proposed scheme FHOPE. The experiment results show that, compared with the existing approaches, the FHOPE scheme incurs less overhead on computation and communication. It is suitable for large batch complex SQL queries over encrypted data in cloud environment.


---

## Body

## 1. Introduction

With the advance of cloud storage and computing, the business opportunity to offer a database as an outsourced service is gaining momentum. Today numerous enterprises and end users may outsource their data to those cloud service providers for lower cost and better performance [1, 2]. Outsourced databases can be applied to many scenarios. For example, one outsourced database application scenario is shown in Figure 1, and, in this example, the data owners, such as hospitals, may want to outsource the medical records to the cloud databases. Patients’ medical records contain sensitive information (e.g., blood pressure, body mass index). Based on the assumption that service provider is honest-but-curious [3, 4], sensitive information needs to be encrypted before being uploaded to the cloud database. The data owners can query their data from cloud database. Then, the cloud database should execute SQL queries over the encrypted data. However, the encrypted data may also bring significant difficulty in executing standard SQL and computing over these data. For example, the encrypted data may lose the original order, without the set of primitive operators, such as equality checks, order comparisons, addition, multiplication, aggregates (sums), and joins.Figure 1
Data owners outsource their data (e.g., credit card details and patient’s medical records) to the cloud database. The sensitive data need to be encrypted. The cloud server provides storage and query service.To date, many fully homomorphic encryption (FHE) and order-preserving encryption (OPE) schemes were proposed [5–10]. The FHE schemes are not practical for either cloud database providers or users, because of high computational overhead [11, 12], and these schemes only support homomorphic addition and homomorphic multiplication over encrypted data. The OPE schemes reveal the order and expose some private information to the cloud service provider, which support SQL range queries. On the contrary, CryptDB uses onions to protect private data and support efficient SQL queries over encrypted data. The onion encryption is a multilayered encryption scheme, and for processing different types of computations multiple onions are needed in practice, because the computations are supported by different encryption schemes. For example, the CryptDB can perform range queries while a column is encrypted with order-preserving encryption, and if it performs aggregate queries, such column is encrypted with homomorphic encryption. Furthermore, the functionalities of CryptDB lack some useful features (e.g., there is no support for queries containing multiplication, and there are also some other limitations). As a result, a query like SELECT ∗ FROM T1 WHERE A=100 AND A+C×D>E cannot be executed by CryptDB. How to design a practical encrypted scheme that supports different operators (+,−,×,<,>,=) in complex SQL queries over encrypted data without privacy breaches remains a challenging and open problem.Motivated by the aforementioned problem, we design a full homomorphic algorithm with the order-preserving feature to support complex SQL queries that contain different operators (such as addition, multiplication, order comparison, and equality checks) over encrypted data. Our proposed FHOPE scheme makes up for FHE’s shortcoming, which supports order comparison, enables range queries to be executed in database operations, and reduces computational costs to increase efficiency. Because it has order-preserving function, the order of the plaintext values is inevitably revealed. The ideal security goal for an order-preserving scheme, IND-OCPA [13], is to reveal no additional information about the plaintext values besides their order. Our proposed scheme is an ideal security homomorphic order-preserving encryption scheme where the ciphertexts reveal nothing except for the order of the plaintext values. Regarding efficiency, we can see that security and efficiency are contradictory; the higher security, the lower efficiency. Practicality and efficiency are very important for database applications. The FHOPE is efficient and practical, satisfies the need of database applications, and solves the complex queries problems that need to be solved in the database. FHOPE can resist the homomorphic order-preserving chosen-plaintext attack. Here, we summarize our contributions as follows:(i)
In the cloud database environment, data is frequently queried by users. It is critical to determine whether an encryption scheme can provide complex SQL queries like the predicates containing different operators over encrypted data. We combine homomorphism with order-preserving and design a novel FHOPE scheme to support addition, multiplication, order comparison, and equality checks. These operators are data interoperable, so they can be combined to formulate complex SQL queries. Then, the FHOPE scheme enables a wide range of SQL queries over the encrypted data to be expressed. As a result, it does not require downloading the encrypted data to client. Therefore, it can improve the efficiency in dealing with data query and processing.(ii)
Furthermore, we optimize the FHOPE scheme by adding some random noise with a certain probabilityP and by specifying any sub-ciphertext with order-preserving property. Besides, we apply the FHOPE scheme to the cloud database application.(iii)
We evaluate the proposed FHOPE scheme in terms of security, efficiency, and complexity. The concrete FHOPE scheme is provably secure according to the formal security proof. The experiment results show that the FHOPE scheme incurs less overhead in computation and communication than the existing approaches. It is suitable for large batch of SQL queries over encrypted data in cloud environment.The remainder of this paper is organized as follows. Section2 discusses some related work. In Section 3 we describe the system model and attack model. Section 4 gives the basic idea of FHOPE scheme and its construction. Section 5 presents the correctness of FHOPE scheme. Section 6 describes the FHOPE’s application in a cloud database. In Section 7 we give security analysis. Section 8 describes the evaluations. Section 9 concludes the paper.


## 2. Related Work

The security of data and processing of the encrypted data in a cloud database environment have caused much research concern recently [14, 15]. Many schemes have been designed with various techniques: fully homomorphic scheme (FHE) and order-preserving encryption (OPE). Gentry had described a FHE [7, 8] in 2009; the FHE supports various computations over ciphertexts. Since Gentry’s result of research breakthrough, a great many improvements [12, 16–21] have been made; the performance was enhanced. However, since the current FHE schemes have low efficiency, they are not suitable for practical applications. Another encryption scheme is OPE; it is primarily used in databases for supporting order comparison on ciphertexts. OPE [5] solves the encrypted query problems in database systems, which was first proposed in 2004. Although a large number of researchers have made great efforts on the OPE schemes [9, 13, 22, 23], these schemes have failed to achieve ideal security. Until now, Popa et al. proposed the mutable order-preserving encoding (mOPE) scheme [24], which is an ideal security OPE scheme; it builds a balanced search tree, which contains the plaintext values encrypted by the application. mOPE is an ideal security scheme, but it has the low efficiency due to the interaction and tree balancing. Moreover, their works only process order comparison on ciphertexts.Some solutions were proposed for querying data over the encrypted database [25–27]. One of the most important fundamental schemes for processing queries on an encrypted database is proposed by H. Hacigu¨mu¨ṣ et al. in [25]. It encrypts the data at a tuple level, and then a predefined set of attributes can be used in queries. Following H. Hacigu¨mu¨ṣ’s idea, some improvements were proposed [28, 29]. The scheme [28] stores redundant data for querying data over the encrypted database, and B. Hore et al. [29] extended the model of H. Hacigu¨mu¨ṣ et al. and added range queries over the encrypted database. To achieve the various computations over encrypted data, some Paillier-based improvements [8, 30–34] were presented. The schemes in [30, 31] can support homomorphic addition, homomorphic multiplication, and order comparison, but the order comparison is realized by converting to subtraction operation; they have high computation overhead. Yan et al. [33] can only support the addition and cannot support other computation operations. Peter et al. [34] proposed an efficient outsourcing multiparty computation framework under multiple keys, but the scheme only supports addition and multiplication and cannot support other operations.CryptDB [35] and SDB [36] are well-known systems for processing queries over encrypted database. CryptDB uses onions to support SQL queries over encrypted databases, where range queries and equality condition queries rely on order-preserving encryption [24] and deterministic encryption, respectively. It performs specific operations with homomorphic encryption, to support aggregate queries; it implemented the Paillier cryptosystem [29], but it cannot support homomorphic multiplication. The CryptDB has the following limitations: (1) its queries are processed on the lowest-security level of data; (2) the same data needs to be reencrypted according to different types of computation. For example, it can perform range queries while a column is encrypted with order-preserving encryption, and if it performs aggregate queries, such column is encrypted with homomorphic encryption. SDB [36] can process queries that contain different kinds of operations; nevertheless, it requires massive computation resources and communication cost.Thus, it is always necessary to establish an efficient scheme to process database queries without involving multiple incompatible encryption schemes.


## 3. System Model and Attack Model

In this section, we describe the system model and the attack model and give formal definition of the scheme. The prototype will be built based on the system model. The security of the proposed scheme will be analyzed in Section7.


### 3.1. System Model

Figure2 shows the overall architecture. The client receives queries from users, generates the private key and encrypts the sensitive data, sends the SQL queries to the cloud server, receives queries results, decrypts the results using the corresponding keys, and sends the decrypted result to the users.Figure 2
System model for outsourced databases.A FHOPE scheme in this paper involves two different entities which are described below.Client (CL). The client is data owner. For protecting data privacy, it uses the private key to encrypt the sensitive data and then outsources the encrypted data to a cloud server. The CL can also send the SQL queries to a CS and decrypt the queries results from the CS.Cloud Server (CS). A CS is hosted by the service provider that stores the databases in cloud. It stores and manages the data of users. A CS also stores the encrypted intermediate and final results. Furthermore, a CS is able to perform homomorphic addition, homomorphic multiplication, order comparison, and equality checks over encrypted data and then process complex SQL queries on encrypted data.To describe our scheme, we give the formal definition of FHOPE.Definition 1 (FHOPE).
A FHOPE scheme consists of four phases (key generation, encryption, decryption, and computation). The detailed phases are described below.(1)
Key generation:sk←KeyGen(1k). KeyGen runs at the CL, takes as input the security k, and outputs a private key sk. The CS cannot get access to the private key.(2)
Encryption:c←Enc(sk,v). Enc runs at the CL. The inputs to the CL are sk and the sensitive data v in the SQL queries, and the CL obtains a ciphertext c and then sends the SQL queries to a CS.(3)
Decryption:v←Dec(sk,c). The CL runs Dec on the private key and a ciphertext c and obtains a plaintext v.(4)
Computation:res←HAMOE(c1,…,cl). HAMOE runs at the server, takes as input ciphertext c1,…,cl, and can perform addition, multiplication, order comparison, and equality checks over the ciphertext and then output the result of the computation.To describe the correctness of our scheme, we define what it means for the scheme to be correct. Intuitively, the scheme should decrypt the correct values and correctly support homomorphic addition, homomorphic multiplication, and order comparison on the ciphertext. Suppose that we have a secret key vectorK(n) and that m integers vi∈V(1≤i≤m) are encrypted into m vectors C1,C2,…,Cm, where Ci=(ci1,…,cin).Definition 2 (correctness).
A FHOPE scheme for plaintext domain Z is correct if, for all security parameters k, for allK(n)←KeyGen(1k),(1)
for allv∈Z and for every C outcome of FHOPE(v,K(n)), Dec(K(n),C)=v;(2)
for allvi∈Z and for every Ci outcome of FHOPE(vi,K(n)), Dec(K(n),∑i=1mCi)=∑i=1mvi;(3)
for allvi∈Z and for every Ci outcome of FHOPE(vi,K(n)), Dec(K(n),Ci×Cj)=vi×vj;(4)
for all sequencesse={v1,…,vm}∈Zm, for all pairs vi,vj∈se, for all Ci,Cj obtained as above, we have vi<vj⇔Ci<Cj;(5)
for allvi∈Z and for every Ci outcome of FHOPE(vi,K(n)), we have vi+vj×vk>vl⇔Ci+Cj×Ck>Cl.


### 3.2. Attack Model

In this section, we present the potential threats and the security requirements for database outsourcing in the cloud. In our scheme, we assume the same security model commonly adopted in related literatures in this field (e.g., [35]), where the CL is the data owner. Thus, the CL is trusted; the CS is honest-but-curious; that is, the computation provided by the CS is able to be executed correctly, and it does not change the data or query results, but the CS tries its best to obtain the privacy information of the processed data. Order-preserving encryption is primarily used in databases for supporting order comparison on ciphertexts, it exposes the order of data, and then the cloud can learn the statistical properties (like order) through repeated query requests. Therefore, we introduce an adversary A in our model, which aims to decrypt the ciphertexts of a challenge sent to applications with the following capabilities:(1)
A may try to obtain the private key and guess the plaintext values from ciphertexts outsourced from a CL.(2)
A may compromise the CS by guessing the plaintext values of the computation results received from the CS.(3)
A may compromise the CS to guess the plaintext values of the queries results based on statistical properties (like order).For satisfying the security requirements of the FHOPE scheme, we formalize the security definition of a FHOPE scheme for IND-HOCPA (indistinguishability under a homomorphic order-preserving chosen-plaintext attack), which intuitively says that the scheme must not leak anything besides order. The homomorphic order-preserving chosen-plaintext attack is a restricted chosen-plaintext attack. We remark that the restricted chosen-plaintext attack is used in literature [10]. We adapt the security definition of literature [13] to the syntax of our proposed scheme.Definition 3 (IND-HOCPA security).
A FHOPE scheme is IND-HOCPA secure, if any probabilistic polynomial time (PPT) adversaryA has only a negligible advantage AdvFHOPE,AIND-HOCPA to win in the following game. The FHOPE game between the adversary A and the challenger CH is given below: (1)
For the secure parameter k, the challengerCH runs the key generation algorithm KeyGen and generates sk←KeyGen(1k).(2)
The challengerCH and the adversary A engage in a polynomial number of rounds of interaction. For round i,
(1)
the adversaryA chooses two equal-length messages vi0,vi1∈Z and sends them to the challenger CH;(2)
the challengerCH picks b∈{0,1} at random and leads the interaction for the Enc algorithm on inputs sk and vib with the server CS, with the adversary A observing all the ciphertexts at CS.(3)
The adversaryA outputs b′, its guess for b.We say that the adversaryA wins the game if (1) its guess is correct (b=b′) and (2) the sequences {vi0}i and {vi1}i have the same order relations (namely, for all i, j,vi0<vj0⇔vi1<vj1). That is, A wins the above game if AdvFHOPE,AIND-HOCPA(k) is nonnegligible, where the adversary’s advantage AdvFHOPE,AIND-HOCPA(k) in the above game is defined as(1)AdvFHOPE,AIND-HOCPAk=PrwinA,k-12,where winA,k is the random variable indicating the success of the adversary in the above game.


## 3.1. System Model

Figure2 shows the overall architecture. The client receives queries from users, generates the private key and encrypts the sensitive data, sends the SQL queries to the cloud server, receives queries results, decrypts the results using the corresponding keys, and sends the decrypted result to the users.Figure 2
System model for outsourced databases.A FHOPE scheme in this paper involves two different entities which are described below.Client (CL). The client is data owner. For protecting data privacy, it uses the private key to encrypt the sensitive data and then outsources the encrypted data to a cloud server. The CL can also send the SQL queries to a CS and decrypt the queries results from the CS.Cloud Server (CS). A CS is hosted by the service provider that stores the databases in cloud. It stores and manages the data of users. A CS also stores the encrypted intermediate and final results. Furthermore, a CS is able to perform homomorphic addition, homomorphic multiplication, order comparison, and equality checks over encrypted data and then process complex SQL queries on encrypted data.To describe our scheme, we give the formal definition of FHOPE.Definition 1 (FHOPE).
A FHOPE scheme consists of four phases (key generation, encryption, decryption, and computation). The detailed phases are described below.(1)
Key generation:sk←KeyGen(1k). KeyGen runs at the CL, takes as input the security k, and outputs a private key sk. The CS cannot get access to the private key.(2)
Encryption:c←Enc(sk,v). Enc runs at the CL. The inputs to the CL are sk and the sensitive data v in the SQL queries, and the CL obtains a ciphertext c and then sends the SQL queries to a CS.(3)
Decryption:v←Dec(sk,c). The CL runs Dec on the private key and a ciphertext c and obtains a plaintext v.(4)
Computation:res←HAMOE(c1,…,cl). HAMOE runs at the server, takes as input ciphertext c1,…,cl, and can perform addition, multiplication, order comparison, and equality checks over the ciphertext and then output the result of the computation.To describe the correctness of our scheme, we define what it means for the scheme to be correct. Intuitively, the scheme should decrypt the correct values and correctly support homomorphic addition, homomorphic multiplication, and order comparison on the ciphertext. Suppose that we have a secret key vectorK(n) and that m integers vi∈V(1≤i≤m) are encrypted into m vectors C1,C2,…,Cm, where Ci=(ci1,…,cin).Definition 2 (correctness).
A FHOPE scheme for plaintext domain Z is correct if, for all security parameters k, for allK(n)←KeyGen(1k),(1)
for allv∈Z and for every C outcome of FHOPE(v,K(n)), Dec(K(n),C)=v;(2)
for allvi∈Z and for every Ci outcome of FHOPE(vi,K(n)), Dec(K(n),∑i=1mCi)=∑i=1mvi;(3)
for allvi∈Z and for every Ci outcome of FHOPE(vi,K(n)), Dec(K(n),Ci×Cj)=vi×vj;(4)
for all sequencesse={v1,…,vm}∈Zm, for all pairs vi,vj∈se, for all Ci,Cj obtained as above, we have vi<vj⇔Ci<Cj;(5)
for allvi∈Z and for every Ci outcome of FHOPE(vi,K(n)), we have vi+vj×vk>vl⇔Ci+Cj×Ck>Cl.


## 3.2. Attack Model

In this section, we present the potential threats and the security requirements for database outsourcing in the cloud. In our scheme, we assume the same security model commonly adopted in related literatures in this field (e.g., [35]), where the CL is the data owner. Thus, the CL is trusted; the CS is honest-but-curious; that is, the computation provided by the CS is able to be executed correctly, and it does not change the data or query results, but the CS tries its best to obtain the privacy information of the processed data. Order-preserving encryption is primarily used in databases for supporting order comparison on ciphertexts, it exposes the order of data, and then the cloud can learn the statistical properties (like order) through repeated query requests. Therefore, we introduce an adversary A in our model, which aims to decrypt the ciphertexts of a challenge sent to applications with the following capabilities:(1)
A may try to obtain the private key and guess the plaintext values from ciphertexts outsourced from a CL.(2)
A may compromise the CS by guessing the plaintext values of the computation results received from the CS.(3)
A may compromise the CS to guess the plaintext values of the queries results based on statistical properties (like order).For satisfying the security requirements of the FHOPE scheme, we formalize the security definition of a FHOPE scheme for IND-HOCPA (indistinguishability under a homomorphic order-preserving chosen-plaintext attack), which intuitively says that the scheme must not leak anything besides order. The homomorphic order-preserving chosen-plaintext attack is a restricted chosen-plaintext attack. We remark that the restricted chosen-plaintext attack is used in literature [10]. We adapt the security definition of literature [13] to the syntax of our proposed scheme.Definition 3 (IND-HOCPA security).
A FHOPE scheme is IND-HOCPA secure, if any probabilistic polynomial time (PPT) adversaryA has only a negligible advantage AdvFHOPE,AIND-HOCPA to win in the following game. The FHOPE game between the adversary A and the challenger CH is given below: (1)
For the secure parameter k, the challengerCH runs the key generation algorithm KeyGen and generates sk←KeyGen(1k).(2)
The challengerCH and the adversary A engage in a polynomial number of rounds of interaction. For round i,
(1)
the adversaryA chooses two equal-length messages vi0,vi1∈Z and sends them to the challenger CH;(2)
the challengerCH picks b∈{0,1} at random and leads the interaction for the Enc algorithm on inputs sk and vib with the server CS, with the adversary A observing all the ciphertexts at CS.(3)
The adversaryA outputs b′, its guess for b.We say that the adversaryA wins the game if (1) its guess is correct (b=b′) and (2) the sequences {vi0}i and {vi1}i have the same order relations (namely, for all i, j,vi0<vj0⇔vi1<vj1). That is, A wins the above game if AdvFHOPE,AIND-HOCPA(k) is nonnegligible, where the adversary’s advantage AdvFHOPE,AIND-HOCPA(k) in the above game is defined as(1)AdvFHOPE,AIND-HOCPAk=PrwinA,k-12,where winA,k is the random variable indicating the success of the adversary in the above game.


## 4. Fully Homomorphic Order-Preserving Encryption Scheme (FHOPE)

This section presents a novel fully homomorphic order-preserving encryption (FHOPE) scheme to realize various types of operations over encrypted data, such as addition, multiplication, order comparison, and equality checks. Firstly, we describe the notations employed in the remainder of the paper. Then, we construct the FHOPE scheme and prove the correctness of decryption. For clear description, Table1 summarizes the notations employed in the paper.Table 1
Notation.
Symbol Meaning V the set of all input plaintexts v a plaintext C a ciphertext is comprised of two or more sub-ciphertexts ci i-th sub-ciphertext k security parameter K(n) a secret key is comprised of a set of key components ki i-th key component Enc() a function for encryption Dec() a function for decryption Enci() a strictly increasing function overK(n) and v Noisei() a function overK(n) and R S the sensitivity of input valuesv


### 4.1. Homomorphic Encryption Scheme

A practical homomorphic encryption scheme is presented by Liu in 2013 [37], which contains three steps and can be described as follows.KeyGen. The secret key K(n)=(k1,k2,…,kn) is chosen randomly from real number set R.Encrypt. A message m∈R is encrypted into C=Enc(v,K(n))=(c1,…,cn); the encryption result is a tuple of n components, corresponding to n sub-ciphertexts.Decrypt. Take as input the secret key K(n) and a ciphertext C=(c1,…,cn); compute and output a message m:(2)m=DecKn,c1,…,cn.Our proposed scheme differs from that of [37] in that we focus on designing an encryption scheme that supports complex expressions containing different operators (+, −, ×, <, >, and =) in SQL queries over encrypted data and data interoperable operators.


### 4.2. Construction of FHOPE Scheme

By using symmetric encryption, a full homomorphic order-preserving encryption is given as follows, which consists of three steps.KeyGen(KG). Generate the secret key(3)Kn=k1→,k2→,…,kn→=a1,b1,a2,b2,…,an,bn,where(ai,bi)(1≤i≤n) is a list of pairs of integers, which are large prime numbers, ai∗bi>0, n>1, ai≠0 for 1≤i≤n,b1+⋯+bn-1≠0, and bn≠0. The number of key components in the key set is equal to the number of sub-ciphertexts.Encrypt (Enc). Encrypt the plaintext FHOPE(v,K(n))=(c1,…,cn), where v is a plaintext; the encryption result is a tuple of n components, corresponding to n sub-ciphertexts. The encryption algorithm uses the components Enci(K(n),v), Noisei(K(n),R), and ξi to define each ci, as shown below, where Enci is a strictly increasing function over K(n) and v, in particular linear to v. Noisei is a function over K(n) and R, which calculates a random number for randomizing ci, ξi denote the random noise, which is randomly sampled from the range [-∞,+∞], and a set R of n pairs of numbers {(r1,p1),…,(rn,pn)} is defined in a finite integer domain. We define the functions Enci() and Noisei() by (5) and (6), respectively.(4)ci=EnciKn,v+NoiseiKn,R+ξi,(5)Enciai,bi,v=ai∗bi∗v,(6)Noiseiai,ri,pi=a1×p1a2-a1×rnan+r1-pni=1ai×piai+1-ai×ri-1ai-1+ri-pi-12≤i≤n-1an×pna1-an×rn-1an-1+rn-pn-1i=nThe noise defined in (6) should satisfy condition (7).(7)0<NoiseiKn,R<EnciKn,v+S-EnciKn,v.Decrypt (Dec). Decrypt a ciphertext C=(c1,…,cn), and get the plaintext v.(8)DecKn,c1,…,cn=v,whereK(n)=[(a1,b1),(a2,b2),…,(an,bn)] is a secret key; v is a plaintext.Then, the decryption algorithm is defined as(9)∑i=1nDeciai,bi∗ci=v,(10)Deciai,bi=1ai×∑i=1nbi,whereDeci is an i-th decryption function over the key vector, and it has a linear time complexity with respect to n. Based on the definition of ci in (4), (8) is rewritten into (9), which is equal to (11)∑i=1nDeciKn∗EnciKn,v+NoiseiKn,R+ξi=v.In order to ensure the validity of decryption steps in (9), it has to satisfy the conditions(12)∑i=1nDeciKn∗NoiseiKn,R+ξi=0,(13)∑i=1nDeciKn∗EnciKn,v=v.Proof of Correctness for DecryptionProof.
To prove correctness of decryption, suppose that anyv1∈Z is encrypted into C1=(c11,…,c1n) with the key K(n), as shown below. (14)c1i=EnciKn,v1+NoiseiKn,Ri1+ξ.Suppose that the first sub-ciphertext (c11) has order-preserving property, and random noise ξ is added to the first and second sub-ciphertext, respectively. Then, we have to prove (15)Dec(Kn,c11,…,c1n=v1.That is, (16)∑i=1nDeciKn∗EnciKn,v1+NoiseiKn,R+ξ=v1,where (17)Deciai,bi=1ai∗∑i=1nbi.We have (18)∑i=1nDeciKn∗NoiseiKn,R=1∑i=1nbi∗p1a2-rnan+r1a1+⋯-pn-1an=0.Because a2=-a1 and ξ≠0, then (19)∑i=1nDeciKn∗ξ=1ai∗∑i=1nbi∗ξ=0.Then (20)∑i=1nDeciKn∗EnciKn,v1=∑i=1n1ai∗∑i=1nbi∗ai∗bi∗v1=v1.Therefore, the correctness of decryption is proved.To verify the correctness of operations supported by our scheme, suppose that we have a secret key vectorK(n) and that m integers vi∈V(1≤i≤m) are encrypted into m vectors C1,C2,…,Cm, where Ci=(ci1,…,cin).


## 4.1. Homomorphic Encryption Scheme

A practical homomorphic encryption scheme is presented by Liu in 2013 [37], which contains three steps and can be described as follows.KeyGen. The secret key K(n)=(k1,k2,…,kn) is chosen randomly from real number set R.Encrypt. A message m∈R is encrypted into C=Enc(v,K(n))=(c1,…,cn); the encryption result is a tuple of n components, corresponding to n sub-ciphertexts.Decrypt. Take as input the secret key K(n) and a ciphertext C=(c1,…,cn); compute and output a message m:(2)m=DecKn,c1,…,cn.Our proposed scheme differs from that of [37] in that we focus on designing an encryption scheme that supports complex expressions containing different operators (+, −, ×, <, >, and =) in SQL queries over encrypted data and data interoperable operators.


## 4.2. Construction of FHOPE Scheme

By using symmetric encryption, a full homomorphic order-preserving encryption is given as follows, which consists of three steps.KeyGen(KG). Generate the secret key(3)Kn=k1→,k2→,…,kn→=a1,b1,a2,b2,…,an,bn,where(ai,bi)(1≤i≤n) is a list of pairs of integers, which are large prime numbers, ai∗bi>0, n>1, ai≠0 for 1≤i≤n,b1+⋯+bn-1≠0, and bn≠0. The number of key components in the key set is equal to the number of sub-ciphertexts.Encrypt (Enc). Encrypt the plaintext FHOPE(v,K(n))=(c1,…,cn), where v is a plaintext; the encryption result is a tuple of n components, corresponding to n sub-ciphertexts. The encryption algorithm uses the components Enci(K(n),v), Noisei(K(n),R), and ξi to define each ci, as shown below, where Enci is a strictly increasing function over K(n) and v, in particular linear to v. Noisei is a function over K(n) and R, which calculates a random number for randomizing ci, ξi denote the random noise, which is randomly sampled from the range [-∞,+∞], and a set R of n pairs of numbers {(r1,p1),…,(rn,pn)} is defined in a finite integer domain. We define the functions Enci() and Noisei() by (5) and (6), respectively.(4)ci=EnciKn,v+NoiseiKn,R+ξi,(5)Enciai,bi,v=ai∗bi∗v,(6)Noiseiai,ri,pi=a1×p1a2-a1×rnan+r1-pni=1ai×piai+1-ai×ri-1ai-1+ri-pi-12≤i≤n-1an×pna1-an×rn-1an-1+rn-pn-1i=nThe noise defined in (6) should satisfy condition (7).(7)0<NoiseiKn,R<EnciKn,v+S-EnciKn,v.Decrypt (Dec). Decrypt a ciphertext C=(c1,…,cn), and get the plaintext v.(8)DecKn,c1,…,cn=v,whereK(n)=[(a1,b1),(a2,b2),…,(an,bn)] is a secret key; v is a plaintext.Then, the decryption algorithm is defined as(9)∑i=1nDeciai,bi∗ci=v,(10)Deciai,bi=1ai×∑i=1nbi,whereDeci is an i-th decryption function over the key vector, and it has a linear time complexity with respect to n. Based on the definition of ci in (4), (8) is rewritten into (9), which is equal to (11)∑i=1nDeciKn∗EnciKn,v+NoiseiKn,R+ξi=v.In order to ensure the validity of decryption steps in (9), it has to satisfy the conditions(12)∑i=1nDeciKn∗NoiseiKn,R+ξi=0,(13)∑i=1nDeciKn∗EnciKn,v=v.Proof of Correctness for DecryptionProof.
To prove correctness of decryption, suppose that anyv1∈Z is encrypted into C1=(c11,…,c1n) with the key K(n), as shown below. (14)c1i=EnciKn,v1+NoiseiKn,Ri1+ξ.Suppose that the first sub-ciphertext (c11) has order-preserving property, and random noise ξ is added to the first and second sub-ciphertext, respectively. Then, we have to prove (15)Dec(Kn,c11,…,c1n=v1.That is, (16)∑i=1nDeciKn∗EnciKn,v1+NoiseiKn,R+ξ=v1,where (17)Deciai,bi=1ai∗∑i=1nbi.We have (18)∑i=1nDeciKn∗NoiseiKn,R=1∑i=1nbi∗p1a2-rnan+r1a1+⋯-pn-1an=0.Because a2=-a1 and ξ≠0, then (19)∑i=1nDeciKn∗ξ=1ai∗∑i=1nbi∗ξ=0.Then (20)∑i=1nDeciKn∗EnciKn,v1=∑i=1n1ai∗∑i=1nbi∗ai∗bi∗v1=v1.Therefore, the correctness of decryption is proved.To verify the correctness of operations supported by our scheme, suppose that we have a secret key vectorK(n) and that m integers vi∈V(1≤i≤m) are encrypted into m vectors C1,C2,…,Cm, where Ci=(ci1,…,cin).


## 5. Correctness of the FHOPE

A query operation can request arbitrary data with a statement to describe the desired data. In order to obtain the desired data, the query contains some statements to describe the requirement, e.g., arithmetic and comparison operators (×, +, −, =, >, and <). These operators are data interoperable, so they can be combined to formulate complex queries, and we are concerned with executing queries that contain multiple different operations, such as WHERE a+b×c<d. Our data model is column-based in a table. In this section, we prove the correctness of additive homomorphism, multiplicative homomorphism, order-preserving, and data interoperability and describe how these operators are implemented in our scheme.


### 5.1. Addition (AD)/Subtraction

Assuming two sensitive columnscol_A and col_B of a table T, their values are integers. We use vi and vj to denote the values of col_A and col_B in a row t, respectively. Let Ci and Cj be the encrypted values of vi and vj, respectively, where Ci=(ci1,…,cin) and Cj=(cj1,…,cjn); they share the same secret key vector K(n).Given two sensitive columnscol_A and col_B, if the application issues the query SELECT ∗ FROM Table 1 WHERE col_C=col_A+col_B, the SQL query processing is as follows.Step 1.
The CL receives the SQL query, it uses the encryption algorithm Enc to encrypt the values ofcol_A and col_B with the private key K(n); their ciphertexts are Ci=(ci1,…,cin) and Cj=(cj1,…,cjn), respectively.Step 2.
The CS executes the SQL query on the encrypted data just like on plaintext. Due to additive homomorphism, the CS can directly add encrypted data one by one as follows:Ci+Cj=(ci1+cj1,…,cin+cjn), where the homomorphic addition of Ci and Cj is defined as a vector addition.The FHOPE scheme guarantees homomorphic addition according to the following theorem.Theorem 4.
The FHOPE scheme supports additive homomorphism; i.e.,Dec((∑i=1mci1,…,∑i=1mcin),K(n))=∑i=1mvi.Proof.
(21) D e c ∑ i = 1 m c i 1 , … , ∑ i = 1 m c i n , K n = ∑ j = 1 n D e c j K n ∗ ∑ i = 1 m c i j = ∑ j = 1 n ∑ i = 1 m D e c j K n ∗ c j i = ∑ i = 1 m ∑ j = 1 n D e c j K n ∗ c j i = ∑ i = 1 m v i .The correctness of homomorphic addition is proved.Subtraction operation can be converted to addition operation for processing, so it is omitted.


### 5.2. Multiplication (MU)

We describe the FHOPE scheme for “×”. Given two sensitive columns col_A and col_B of a table T, let v1 and v2 denote the values of col_A and col_B in a row t, respectively. Let C1 and C2 be the encrypted values of v1 and v2, respectively, where C1=(c11,…,c1n) and C2=(c21,…,c2n); they share the same secret key vector K(n).If the application issues the query SELECT∗ FROM Table 1 WHERE col_C=col_A×col_B, the SQL query processing is as follows.Step 1.
The CL receives the SQL query, it uses the encryption algorithm Enc to encrypt the values ofcol_A and col_B with the private key K(n), and their ciphertexts are C1=(c11,…,c1n) and C2=(c21,…,c2n), respectively.Step 2.
The CS executes the SQL query on the encrypted data just like on plaintext. Due to multiplicative homomorphism, the CS can directly multiply encrypted data one by one as follows:(22)C1×C2=c11×c21…c11×c2n…c1n×c21…c1n×c2n,where the multiplication of two ciphertexts can be defined as an outer product.Our objective is to perform multiplication operations on the encrypted data just like on plaintext. The FHOPE scheme guarantees homomorphic multiplication according to the following theorem.Theorem 5.
The FHOPE scheme supports multiplicative homomorphism. That meansDec(K(n),C1×C2)=v1×v2.Proof.
To prove this theorem, we first need to show that(23)DecKn,C1×C2=c11…c1n×v2.
Then, we proveDec(K(n),(c11,c12,…,c1n)×v2)=v1×v2. The details are given below.
Step 1. Perform the following decryption for i, 1≤i≤n.
Because we have(24)DecKn,c1i×c21,…,c1i×c2n=∑i=1nDeciKn×c1i×c21,…,c1i×c2n=∑i=1nDeciKn×c1i×c21,…,c2n)=c1i×∑i=1nDeciKn×c21,…,c2n=c1i×v2,then it gives (25)DecKn,C1×C2=c11…c1n×v2.Step 2. We have from Step 1:(26)DecKn,c11×v2,…,c1n×v2=∑i=1nDeciKn×c11×v2,…,c1n×v2=∑i=1nDeciKn×v2×c11,…,c1n=v2×∑i=1nDeciKn×c11,…,c1n=v2×v1=v1×v2.Hence,Dec(K(n),C1×C2)=v1×v2. The correctness of multiplicative homomorphism is proved.


### 5.3. Order Comparison (OC)

We consider two comparison operators, namely, operator “>” and operator “<”. They are mostly used in select queries. Given two sensitive columns col_A and col_B of table T. Let v1 and v2 denote the values of col_A and col_B in a row t, respectively. Let C1 and C2 be the encrypted values of v1 and v2, respectively; they share the same secret key vector K(n). For privacy protection, we calculate v1>v2 or v1<v2, the plaintexts need to be encrypted, and we need to calculate C1>C2 or C1<C2. That is, the goal of FHOPE scheme is that the sort order of ciphertexts matches the sort order of the corresponding plaintexts. Here we prove that our scheme has order-preserving property.Suppose that any two integersv1 and v2 are encrypted into C1=(c11,…,c1n) and C2=(c21,…,c2n) with the key K(n), as shown below.(27)c1i=EnciKn,v1+NoiseiKn,Ri1+ξ,(28)c2i=EnciKn,v2+NoiseiKn,Ri2+ξ.Definition 6.
LetV={v1,v2,…,vn} be the set of all input plaintext values. The sensitivity of V is the minimum element in the set {v1-v2∣v1∈V,v2∈V,v1≠v2}. That is, the sensitivity S is defined as S=minv1,v2∈Vv1≠v2v1-v2.In fact, the sensitivity is the least gap, which was evaluated in different privacy protection [38]. And by its definition the sensitivity is always bigger than 0.Theorem 7.
Given the sensitivityS of input value V, for all v1∈V, v2∈V, if v1>v2, then C1>C2.Proof.
We haveC1>C2 if c1i>c2i, where c1i and c2i(1≤i≤n) are the sub-ciphertext of C1 and C2, respectively. Suppose that the sub-ciphertexts c1i and c2i have the same random noise ξ. To prove this theorem, we need to show c1i-c2i>0; that is,(29)EnciKn,v1+NoiseiKn,Ri1+ξ-EnciKn,v2+NoiseiKn,Ri2+ξ>0.
In other words, we have to prove(30)NoiseiKn,Ri2-NoiseiKn,Ri1<EnciKn,v1-EnciKn,v2.Because the linear expression Enci(K(n),v) is strictly increasing for any plaintext v, we have(31)min⁡EnciKn,v1-EnciKn,v2=EnciKn,v2+S-EnciKn,v2.Since v1>v2, then the minimum v1 is v2+S, which is bigger than v2. Moreover, Noisei(K(n),Ri)>0; then,(32)max⁡NoiseiKn,Ri2-NoiseiKn,Ri1=NoiseiKn,Ri2.
Hence, the theorem holds if(33)NoiseiKn,Ri2<EnciKn,v2+S-EnciKn,v2.Because the noise for each sub-ciphertext satisfies condition (7), the theorem is proved.Therefore, the correctness of order-preserving property is proved.


### 5.4. Equality (EQ)

Equality operator (=) is a common operator in SQL query, for example; a SQL operation is “SELECT name FROM table WHERE score = 90”, which requires equality checks on ciphertext. The existing solution is to support equality checks by using deterministic encryption. The FHOPE scheme can also support equality checks even though some noise has been added, and it does not need to use deterministic encryption. We can employ two methods to implement the equality checks. A simple solution is to remove the random noise of existing ciphertexts in database. But the problem is that this solution needs to modify the ciphertexts in the database to increase the cost of computation; moreover, it makes the ciphertexts in an unsafe state. Hence, we take the second solution. Given a search keyword score=100, to search a ciphertext whose plaintext value is 100 in encrypted database, the following steps need to be executed.Step 1.
The CL uses FHOPE to encrypt the search keywordscore into a ciphertext C=(c1,…,cn) under the key K(n); the random noise is ξ, which is stored in the CL. Then the CL computes the range of the sub-ciphertext ci(1≤i≤n) as follows:(34)ci=EnciKn,score+NoiseiKn,Ri+ξ,and because(35)0<NoiseiKn,Ri<EnciKn,score+S-EnciKn,score,
we have(36)EnciKn,score+ξ<ci<EnciKn,score+S+ξ,and the range (Enci(K(n),score)+ξ,Enci(K(n),score+S)+ξ) of the sub-ciphertext ci to the CS is sent.Step 2.
The CS compares the range of the sub-ciphertextci with the existing i-th sub-ciphertexts of ciphertexts in encrypted database, if an existing i-th sub-ciphertext falls within the range of the sub-ciphertext ci, it has the same plaintext value 100 as the search keyword score, and so they are equal. The CS sends the search result to the CL.Therefore, the second solution implements equality checks while ensuring the security. Because the equality check is based on the order comparison, the order comparison is correct; then the equality check is correct.


### 5.5. Data Interoperability (DI)

As that shown below, the proposed scheme can also provide efficient operators with data interoperability. The data interoperability has the following two characteristics:(1) different operators share the same encryption scheme; (2) the output of an operator can be taken as input of another. With the data interoperability, these operators (×, +, −, =, >, and <) can be combined to formulate complex expressions in SQL queries (e.g., SELECT ∗ FROM Table 1 WHERE col_C+col_A×col_B<10000). The FHOPE scheme guarantees data interoperability according to the following theorem.Theorem 8.
The FHOPE scheme has the property of the data interoperability; i.e., ifv1+v2×v3>v4, then C1+C2×C3>C4.Proof.
To prove this theorem, we need to showFHOPE(v1+v2×v3,K(n))>FHOPE(v4,K(n)). According to Theorems 4, 5, and 7, we have(37)FHOPEv1+v2×v3,Kn>FHOPEv4,Kn⟶FHOPEv1,Kn+FHOPEv2×v3,Kn>FHOPEv4,Kn⟶FHOPEv1,Kn+FHOPEv2,Kn×FHOPEv3,Kn>FHOPEv4,Kn⟶C1+C2×C3>C4.The correctness of data interoperability is proved.


### 5.6. Improving Efficiency

In encryption algorithm Enc, some random noiseξi has been added in each sub-ciphertext to augment the security of FHOPE scheme. However, this process reduces the efficiency of the scheme. Here, we use two measures to improve efficiency. One approach is that two sub-ciphertexts in a ciphertext have order-preserving function. For example, the plaintext v1 is encrypted into C1=(c11,…,cn1) under the key K(n), each sub-ciphertext is a ciphertext of the plaintext, and the sub-ciphertexts are independent of each other, so any sub-ciphertext of the n sub-ciphertexts has order-preserving property; it means that the ciphertext has order-preserving property. Then, we can specify that the first sub-ciphertext (ci1) of the n sub-ciphertexts has order-preserving property. Another approach is to add random noise ξi with a certain probability P. Figure 3 shows that, with the growth of probability P, the time cost increases while the length of the plaintext is fixed. We will analyze the relationship between probability P and the time cost of inserting a ciphertext.Figure 3
The relationship between time cost and probability.The cost of inserting a ciphertext includes encrypting the plaintext to be inserted, inserting the ciphertext, and updating random noise. Assume that the length of plaintextv is m and the plaintext v is encrypted into C. Let te, ti, and tu denote the time of encrypting, the time of inserting operation, and the time of updating random noise, respectively. For n ciphertexts of attu stored in the database, the probability of adding random noise in the ciphertext is P. Then, the time for inserting a ciphertext C is T:(38)T=te+ti+n×tu×P,where n×tu×P is generated by inserting the new random noise; it is the time of updating the existing random noise. When we insert N encrypted values into the database, we have (39)k=1,T1=te+ti+n×tu×P,(40)k=2,T2=T1+te+ti+n+1×tu×P,(41)k=3,T3=T2+te+ti+n+2×tu×P,(42)⋯(43)k=N,Tk=Tk-1+te+ti+n+k-1×tu×P.Then,(44)TN=N×te+ti+n×N+0.5×N×N-1×tu×P.According to (44), we can infer the approximate linear relationship between total time T(N) and probability P when N is fixed, and it is consistent with Figure 3. Figure 4 shows that the total time T(N) is exponentially related to N when probability P is fixed. For efficiency, we can conclude that security and efficiency are contradictory; the higher the security, the lower the efficiency.Figure 4
The relationship between time cost and numbers.


## 5.1. Addition (AD)/Subtraction

Assuming two sensitive columnscol_A and col_B of a table T, their values are integers. We use vi and vj to denote the values of col_A and col_B in a row t, respectively. Let Ci and Cj be the encrypted values of vi and vj, respectively, where Ci=(ci1,…,cin) and Cj=(cj1,…,cjn); they share the same secret key vector K(n).Given two sensitive columnscol_A and col_B, if the application issues the query SELECT ∗ FROM Table 1 WHERE col_C=col_A+col_B, the SQL query processing is as follows.Step 1.
The CL receives the SQL query, it uses the encryption algorithm Enc to encrypt the values ofcol_A and col_B with the private key K(n); their ciphertexts are Ci=(ci1,…,cin) and Cj=(cj1,…,cjn), respectively.Step 2.
The CS executes the SQL query on the encrypted data just like on plaintext. Due to additive homomorphism, the CS can directly add encrypted data one by one as follows:Ci+Cj=(ci1+cj1,…,cin+cjn), where the homomorphic addition of Ci and Cj is defined as a vector addition.The FHOPE scheme guarantees homomorphic addition according to the following theorem.Theorem 4.
The FHOPE scheme supports additive homomorphism; i.e.,Dec((∑i=1mci1,…,∑i=1mcin),K(n))=∑i=1mvi.Proof.
(21) D e c ∑ i = 1 m c i 1 , … , ∑ i = 1 m c i n , K n = ∑ j = 1 n D e c j K n ∗ ∑ i = 1 m c i j = ∑ j = 1 n ∑ i = 1 m D e c j K n ∗ c j i = ∑ i = 1 m ∑ j = 1 n D e c j K n ∗ c j i = ∑ i = 1 m v i .The correctness of homomorphic addition is proved.Subtraction operation can be converted to addition operation for processing, so it is omitted.


## 5.2. Multiplication (MU)

We describe the FHOPE scheme for “×”. Given two sensitive columns col_A and col_B of a table T, let v1 and v2 denote the values of col_A and col_B in a row t, respectively. Let C1 and C2 be the encrypted values of v1 and v2, respectively, where C1=(c11,…,c1n) and C2=(c21,…,c2n); they share the same secret key vector K(n).If the application issues the query SELECT∗ FROM Table 1 WHERE col_C=col_A×col_B, the SQL query processing is as follows.Step 1.
The CL receives the SQL query, it uses the encryption algorithm Enc to encrypt the values ofcol_A and col_B with the private key K(n), and their ciphertexts are C1=(c11,…,c1n) and C2=(c21,…,c2n), respectively.Step 2.
The CS executes the SQL query on the encrypted data just like on plaintext. Due to multiplicative homomorphism, the CS can directly multiply encrypted data one by one as follows:(22)C1×C2=c11×c21…c11×c2n…c1n×c21…c1n×c2n,where the multiplication of two ciphertexts can be defined as an outer product.Our objective is to perform multiplication operations on the encrypted data just like on plaintext. The FHOPE scheme guarantees homomorphic multiplication according to the following theorem.Theorem 5.
The FHOPE scheme supports multiplicative homomorphism. That meansDec(K(n),C1×C2)=v1×v2.Proof.
To prove this theorem, we first need to show that(23)DecKn,C1×C2=c11…c1n×v2.
Then, we proveDec(K(n),(c11,c12,…,c1n)×v2)=v1×v2. The details are given below.
Step 1. Perform the following decryption for i, 1≤i≤n.
Because we have(24)DecKn,c1i×c21,…,c1i×c2n=∑i=1nDeciKn×c1i×c21,…,c1i×c2n=∑i=1nDeciKn×c1i×c21,…,c2n)=c1i×∑i=1nDeciKn×c21,…,c2n=c1i×v2,then it gives (25)DecKn,C1×C2=c11…c1n×v2.Step 2. We have from Step 1:(26)DecKn,c11×v2,…,c1n×v2=∑i=1nDeciKn×c11×v2,…,c1n×v2=∑i=1nDeciKn×v2×c11,…,c1n=v2×∑i=1nDeciKn×c11,…,c1n=v2×v1=v1×v2.Hence,Dec(K(n),C1×C2)=v1×v2. The correctness of multiplicative homomorphism is proved.


## 5.3. Order Comparison (OC)

We consider two comparison operators, namely, operator “>” and operator “<”. They are mostly used in select queries. Given two sensitive columns col_A and col_B of table T. Let v1 and v2 denote the values of col_A and col_B in a row t, respectively. Let C1 and C2 be the encrypted values of v1 and v2, respectively; they share the same secret key vector K(n). For privacy protection, we calculate v1>v2 or v1<v2, the plaintexts need to be encrypted, and we need to calculate C1>C2 or C1<C2. That is, the goal of FHOPE scheme is that the sort order of ciphertexts matches the sort order of the corresponding plaintexts. Here we prove that our scheme has order-preserving property.Suppose that any two integersv1 and v2 are encrypted into C1=(c11,…,c1n) and C2=(c21,…,c2n) with the key K(n), as shown below.(27)c1i=EnciKn,v1+NoiseiKn,Ri1+ξ,(28)c2i=EnciKn,v2+NoiseiKn,Ri2+ξ.Definition 6.
LetV={v1,v2,…,vn} be the set of all input plaintext values. The sensitivity of V is the minimum element in the set {v1-v2∣v1∈V,v2∈V,v1≠v2}. That is, the sensitivity S is defined as S=minv1,v2∈Vv1≠v2v1-v2.In fact, the sensitivity is the least gap, which was evaluated in different privacy protection [38]. And by its definition the sensitivity is always bigger than 0.Theorem 7.
Given the sensitivityS of input value V, for all v1∈V, v2∈V, if v1>v2, then C1>C2.Proof.
We haveC1>C2 if c1i>c2i, where c1i and c2i(1≤i≤n) are the sub-ciphertext of C1 and C2, respectively. Suppose that the sub-ciphertexts c1i and c2i have the same random noise ξ. To prove this theorem, we need to show c1i-c2i>0; that is,(29)EnciKn,v1+NoiseiKn,Ri1+ξ-EnciKn,v2+NoiseiKn,Ri2+ξ>0.
In other words, we have to prove(30)NoiseiKn,Ri2-NoiseiKn,Ri1<EnciKn,v1-EnciKn,v2.Because the linear expression Enci(K(n),v) is strictly increasing for any plaintext v, we have(31)min⁡EnciKn,v1-EnciKn,v2=EnciKn,v2+S-EnciKn,v2.Since v1>v2, then the minimum v1 is v2+S, which is bigger than v2. Moreover, Noisei(K(n),Ri)>0; then,(32)max⁡NoiseiKn,Ri2-NoiseiKn,Ri1=NoiseiKn,Ri2.
Hence, the theorem holds if(33)NoiseiKn,Ri2<EnciKn,v2+S-EnciKn,v2.Because the noise for each sub-ciphertext satisfies condition (7), the theorem is proved.Therefore, the correctness of order-preserving property is proved.


## 5.4. Equality (EQ)

Equality operator (=) is a common operator in SQL query, for example; a SQL operation is “SELECT name FROM table WHERE score = 90”, which requires equality checks on ciphertext. The existing solution is to support equality checks by using deterministic encryption. The FHOPE scheme can also support equality checks even though some noise has been added, and it does not need to use deterministic encryption. We can employ two methods to implement the equality checks. A simple solution is to remove the random noise of existing ciphertexts in database. But the problem is that this solution needs to modify the ciphertexts in the database to increase the cost of computation; moreover, it makes the ciphertexts in an unsafe state. Hence, we take the second solution. Given a search keyword score=100, to search a ciphertext whose plaintext value is 100 in encrypted database, the following steps need to be executed.Step 1.
The CL uses FHOPE to encrypt the search keywordscore into a ciphertext C=(c1,…,cn) under the key K(n); the random noise is ξ, which is stored in the CL. Then the CL computes the range of the sub-ciphertext ci(1≤i≤n) as follows:(34)ci=EnciKn,score+NoiseiKn,Ri+ξ,and because(35)0<NoiseiKn,Ri<EnciKn,score+S-EnciKn,score,
we have(36)EnciKn,score+ξ<ci<EnciKn,score+S+ξ,and the range (Enci(K(n),score)+ξ,Enci(K(n),score+S)+ξ) of the sub-ciphertext ci to the CS is sent.Step 2.
The CS compares the range of the sub-ciphertextci with the existing i-th sub-ciphertexts of ciphertexts in encrypted database, if an existing i-th sub-ciphertext falls within the range of the sub-ciphertext ci, it has the same plaintext value 100 as the search keyword score, and so they are equal. The CS sends the search result to the CL.Therefore, the second solution implements equality checks while ensuring the security. Because the equality check is based on the order comparison, the order comparison is correct; then the equality check is correct.


## 5.5. Data Interoperability (DI)

As that shown below, the proposed scheme can also provide efficient operators with data interoperability. The data interoperability has the following two characteristics:(1) different operators share the same encryption scheme; (2) the output of an operator can be taken as input of another. With the data interoperability, these operators (×, +, −, =, >, and <) can be combined to formulate complex expressions in SQL queries (e.g., SELECT ∗ FROM Table 1 WHERE col_C+col_A×col_B<10000). The FHOPE scheme guarantees data interoperability according to the following theorem.Theorem 8.
The FHOPE scheme has the property of the data interoperability; i.e., ifv1+v2×v3>v4, then C1+C2×C3>C4.Proof.
To prove this theorem, we need to showFHOPE(v1+v2×v3,K(n))>FHOPE(v4,K(n)). According to Theorems 4, 5, and 7, we have(37)FHOPEv1+v2×v3,Kn>FHOPEv4,Kn⟶FHOPEv1,Kn+FHOPEv2×v3,Kn>FHOPEv4,Kn⟶FHOPEv1,Kn+FHOPEv2,Kn×FHOPEv3,Kn>FHOPEv4,Kn⟶C1+C2×C3>C4.The correctness of data interoperability is proved.


## 5.6. Improving Efficiency

In encryption algorithm Enc, some random noiseξi has been added in each sub-ciphertext to augment the security of FHOPE scheme. However, this process reduces the efficiency of the scheme. Here, we use two measures to improve efficiency. One approach is that two sub-ciphertexts in a ciphertext have order-preserving function. For example, the plaintext v1 is encrypted into C1=(c11,…,cn1) under the key K(n), each sub-ciphertext is a ciphertext of the plaintext, and the sub-ciphertexts are independent of each other, so any sub-ciphertext of the n sub-ciphertexts has order-preserving property; it means that the ciphertext has order-preserving property. Then, we can specify that the first sub-ciphertext (ci1) of the n sub-ciphertexts has order-preserving property. Another approach is to add random noise ξi with a certain probability P. Figure 3 shows that, with the growth of probability P, the time cost increases while the length of the plaintext is fixed. We will analyze the relationship between probability P and the time cost of inserting a ciphertext.Figure 3
The relationship between time cost and probability.The cost of inserting a ciphertext includes encrypting the plaintext to be inserted, inserting the ciphertext, and updating random noise. Assume that the length of plaintextv is m and the plaintext v is encrypted into C. Let te, ti, and tu denote the time of encrypting, the time of inserting operation, and the time of updating random noise, respectively. For n ciphertexts of attu stored in the database, the probability of adding random noise in the ciphertext is P. Then, the time for inserting a ciphertext C is T:(38)T=te+ti+n×tu×P,where n×tu×P is generated by inserting the new random noise; it is the time of updating the existing random noise. When we insert N encrypted values into the database, we have (39)k=1,T1=te+ti+n×tu×P,(40)k=2,T2=T1+te+ti+n+1×tu×P,(41)k=3,T3=T2+te+ti+n+2×tu×P,(42)⋯(43)k=N,Tk=Tk-1+te+ti+n+k-1×tu×P.Then,(44)TN=N×te+ti+n×N+0.5×N×N-1×tu×P.According to (44), we can infer the approximate linear relationship between total time T(N) and probability P when N is fixed, and it is consistent with Figure 3. Figure 4 shows that the total time T(N) is exponentially related to N when probability P is fixed. For efficiency, we can conclude that security and efficiency are contradictory; the higher the security, the lower the efficiency.Figure 4
The relationship between time cost and numbers.


## 6. Using FHOPE in a Database Application

The FHOPE is mainly used in the database; in this section, we describe how to use FHOPE in a database. As mentioned in Section5, FHOPE allows efficient addition, multiplication, order comparison, and equality checks computations on an encrypted database in the same way as on unencrypted database, and the database server software does not need to be modified.Setup. Using FHOPE in a database requires the following setup:(i)
A CL uses the FHOPE to encrypt the sensitive data, and the encrypted data is outsourced to be stored in a cloud database. The CL stores the private keys.(ii)
User-defined functions (UDFs) in the database server implement FHOPE’s computation function.Insert Queries. To understand how values in a query are encrypted, consider an application that wants to execute the query INSERT INTO student VALUES (10). The CL encrypts 10 using the FHOPE and issues the query INSERT INTO student VALUES (FHOPE(10)), where FHOPE() is a user-defined function that implements the encryption of the FHOPE scheme.Select Queries. Consider a query: SELECT ∗ FROM T WHERE col1×col2+1000>6800. col1 and col2 denote the sensitive columns in a table T; their values are encrypted and stored in a cloud database. The CL encrypts 1000 and 6800 using the FHOPE, and the values of col1 and col2, 1000 and 6800, share the same private key and random noise ξ. col1 and col2 are encrypted as col1c and col2c, respectively. It delivers the query “SELECT ∗ FROM T WHERE col1c×col2c+FHOPE(1000)>FHOPE(6800)” to a CS. The CS executes the query on encrypted data as if the data were not encrypted and returns the query results to CL. The CL decrypts the query results and returns them to the applications.


## 7. Security Analysis

The security analysis of the FHOPE scheme focuses on the security of the keyK(n), IND-HOCPA (indistinguishability under a homomorphic order-preserving chosen-plaintext attack) security and the security of FHOPE scheme. Assume that a CL sends the SQL query to a CS via a secure channel. First, we will prove that it is difficult to recover the secret component ki→ in a key K(n) from ciphertexts. Then, based on the difficulty of the key K(n) recovery problem, we prove the IND-HOCPA security of the scheme. We present the privacy protection in queries. Finally, we demonstrate that the security of FHOPE’s properties is guaranteed by the security of key K(n) and IND-HOCPA security of FHOPE.


### 7.1. Security of the KeyK(n)

The hardness of the key search problem is based on the approximate greatest common divisors (AGCD) problem. The AGCD problem was proposed by Howgrave-Graham [39]. Given any number of the approximate multiples di=h∗qi+li of h, where h, qi, and li are integers, the problem is to find the hidden common divisor h. Note that qi and li change in each di. In particular, if li can be as large as h, it is impossible to reconstruct h from any number of approximate multiples di [40].As we know,K(n)=[k1→,k2→,…,kn→], where ki→=(ai,bi) is a secret vector. In the following, we prove that it is hard to recover the secret component ki→ in a key K(n) from any number of ciphertexts.Theorem 9.
Given any number of ciphertexts from the FHOPE encryption withK(n), it is difficult to recover ki→ in a key K(n).Proof.
As shown in the FHOPE encryption, a ciphertextC=(c1,…,cn) is defined as (45)c1=a1∗b1∗v+Noise1Kn,R1+ξ1,…cn=an∗bn∗v+NoisenKn,Rn.
In the first ciphertext elementc1, a1 is the common divisor to be recovered. We are going to prove that it is difficult to find the secret value a1 from the first element c1 of any number of ciphertexts.
LetN1=Noise1(K(n),R1)+ξ1. Then, we have c1=a1∗b1∗v+N1. Since b1∗v is random number generated for each encryption, N1 is a number that the adversary does not know, and it randomly changes for each encryption of the plaintext. Moreover, a1 can be less than N1. Hence, it is difficult to recover a1 from the first element c1 of any number of ciphertexts according to the hardness of the AGCD problem. The proofs for other secret values ai and bi in K(n) are carried out similarly.


### 7.2. IND-HOCPA Security

We analyze the semantic security of the FHOPE scheme by proving the indistinguishability of ciphertexts under a homomorphic order-preserving chosen-plaintext attack.Theorem 10.
A FHOPE encryption scheme is IND-HOCPA secure.Proof.
In the following game, the PPT adversary is denoted asA and the challenger is denoted as CH. Consider any adversary A and any two sequences of values A ask for in the security game: v0=(v10,…,vn0) and v1=(v11,…,vn1).(1)
The key generation algorithm generates the keyK(n)=[k1→,k2→,…,kn→]=[(a1,b1),(a2,b1),…,(an,bn)], where (ai,bi)(1≤i≤n) is a list of pairs of integers, which are large prime numbers, ai∗bi>0, n>1, ai≠0 for 1≤i≤n,b1+⋯+bn-1≠0, and bn≠0.(2)
The adversaryA chooses two equal-length sequences of values v0 and v1 and sends them to the challenger CH.(3)
The challengerCH randomly encrypts vi0 and vi1 with key K(n) and outputs the ciphertext C0=(c01,…,c0n) or C1=(c11,…,c1n), where c01=a1∗b1∗vi0+Noise1(a1,r1,p1)+ξ0, c11=a1∗b1∗vi1+Noise1(a1,r1,p1)+ξ1, and ξb(b ∈0,1)∈[-∞,+∞]. The ciphertext Cb (b ∈0,1) is sent to the adversary A.(4)
Ifvi0≠0 and vi1≠0, then the expressions of a1∗b1∗vi0+Noise1(a1,r1,p1)+ξ0 and a1∗b1∗vi1+Noise1(a1,r1,p1)+ξ1 generate the same value from -∞ to +∞ with the same probability; since ξb is randomly sampled from the range [-∞,+∞], v0 and v1 have the same order relation. Hence, the advantage AdvFHOPE,AIND-HOCPA(k) of distinguishing is negligible.
In the following, we discuss the case wherevi0=0 and vi1≠0. The case where vi0≠0 and vi1=0 is similar.
Ifvi0=0 and vi1≠0, we have c01=Noise1(a1,r1,p1)+ξ0 or c11=a1∗b1∗vi1+Noise1(a1,r1,p1)+ξ1; depending on whether vi0 or vi1 is encrypted, v0 and v1 have the same order relation. Then, the advantage AdvFHOPE,AIND-HOCPA(k) is negligible.
The proofs for other sub-ciphertextsc0i and c1i(2≤i≤n) are carried out similarly; the advantage AdvFHOPE,AIND-HOCPA(k) is negligible.Therefore, the adversaryA cannot win the above game, and hence a FHOPE is IND-HOCPA secure.


### 7.3. Privacy Protection in Queries

The adversary can collect some useful statistical information after receiving query requests; it tries to guess the plaintext corresponding to the ciphertext based on statistical information. However, we will describe that the FHOPE scheme can reduce the privacy leakage greatly in this scenario.To solve the mentioned problem, we add some random noise in each sub-ciphertext. Letξi denote the random noise, which is randomly sampled from the range [-∞,+∞], and attu denote the column attribute of the database table. Then, the sub-ciphertext ci1(1≤i≤n) of v1 is expressed as Enci(K(n),v1)+Noisei(K(n),Ri1)+ξ1; the range of noise is different for different input values. Suppose ξ (default value is 0 if there are no sub-ciphertexts of attu stored on cloud server) denotes the latest noise. To store ci1 in the cloud server, the following steps need to be executed (if no sub-ciphertexts of attu are stored, jump to Step 2).Step 1.
Update all the stored sub-ciphertexts (cim) of attu by cim=cim+ξ1-ξ.Step 2.
Add random noiseξ1 in the new sub-ciphertexts by ci1=ci1+ξ1.Step 3.
Update the value ofξ by ξ=ξ1.Therefore, due to adding random noise, the ciphertext value is random. The same plaintexts are mapped to different ciphertexts. The random noise of the same attribute is continuously updated with the insertion of new data in the cloud database, and the adversary cannot guess the random noise.Consider a query SELECTcol1 FROM T WHERE col1>100. The col1 denotes the sensitive column in a table T; their values are encrypted and stored in a cloud database. The CL encrypts 100 using the FHOPE, and the values of col1, 100, share the same private key and random noise ξ. And col1 is encrypted as col1c. It delivers the query “SELECT col1c FROM T WHERE col1c>FHOPE(100)” to a CS. Since the data is in the encrypted form and the random noise of each ciphertext is different, the adversary cannot get any knowledge of the order information. The random noise of the same attribute is continuously updated with the insertion of new data in the cloud database (that is, the random noise of the same attribute is the same), and then the order of plaintexts remains in the ciphertexts in the cloud database. Then, the CS executes the query on encrypted data as if the data were not encrypted, and the adversary obtains the query results. Since the random noise is dynamically updated, the order of query results loses freshness. In other words, the repeated query is issued again, and the returned ciphertexts are different. Moreover, we used the restrictions of literature [10] for chosen-plaintext attack, even if the adversary can get the ciphertext of {v1,v2,…,vk}, where {v1,v2,…,vk} is a dense one, but the ciphertexts are disordered because they are obtained at different time. Therefore, previous query requests will not help the adversary to learn the privacy information, and the adversary cannot gradually find out the order information and get some useful statistical information after many query requests.


### 7.4. The Security of FHOPE Properties

Our security model securely realizes ideal properties in the presence of noncolluding semihonest adversary. For the sake of simplicity, we do it for the specific scenario of our properties, which involves CL and CS. We need to construct simulatorSimCS against adversary ACS that corrupts CS.Theorem 11.
The AD can securely perform addition operation on ciphertext in the presence of semihonest adversaryACS.Proof.
CL receives plaintextsv and v′ as input and then generates ciphertexts C of v and C′ of v′. Finally, C and C′ are returned to SimCS.
S i m C S simulates ACS as follows: it receives C and C′ as input and generates the sum of C and C′ by performing addition operation. SimCS sends the sum of C and C′ to ACS.
TheACS’s view contains encrypted data. In the real and ideal executions, the views of ACS are indistinguishable, because CL is trusted and the FHOPE is IND-HOCPA secure.The security proofs of MU, OC, EQ, and DI are similar to that of AD under the semihonest adversaryACS. We give only the theorems here.Theorem 12.
The MU can securely perform multiplication operation on ciphertext in the presence of semihonest adversaryACS.Theorem 13.
The OC can securely perform order comparison on ciphertext in the presence of semihonest adversaryACS.Theorem 14.
The EQ can securely perform equality checks on ciphertext in the presence of semihonest adversaryACS.Theorem 15.
The DI can securely perform complex operation on ciphertext in the presence of semihonest adversaryACS.


## 7.1. Security of the KeyK(n)

The hardness of the key search problem is based on the approximate greatest common divisors (AGCD) problem. The AGCD problem was proposed by Howgrave-Graham [39]. Given any number of the approximate multiples di=h∗qi+li of h, where h, qi, and li are integers, the problem is to find the hidden common divisor h. Note that qi and li change in each di. In particular, if li can be as large as h, it is impossible to reconstruct h from any number of approximate multiples di [40].As we know,K(n)=[k1→,k2→,…,kn→], where ki→=(ai,bi) is a secret vector. In the following, we prove that it is hard to recover the secret component ki→ in a key K(n) from any number of ciphertexts.Theorem 9.
Given any number of ciphertexts from the FHOPE encryption withK(n), it is difficult to recover ki→ in a key K(n).Proof.
As shown in the FHOPE encryption, a ciphertextC=(c1,…,cn) is defined as (45)c1=a1∗b1∗v+Noise1Kn,R1+ξ1,…cn=an∗bn∗v+NoisenKn,Rn.
In the first ciphertext elementc1, a1 is the common divisor to be recovered. We are going to prove that it is difficult to find the secret value a1 from the first element c1 of any number of ciphertexts.
LetN1=Noise1(K(n),R1)+ξ1. Then, we have c1=a1∗b1∗v+N1. Since b1∗v is random number generated for each encryption, N1 is a number that the adversary does not know, and it randomly changes for each encryption of the plaintext. Moreover, a1 can be less than N1. Hence, it is difficult to recover a1 from the first element c1 of any number of ciphertexts according to the hardness of the AGCD problem. The proofs for other secret values ai and bi in K(n) are carried out similarly.


## 7.2. IND-HOCPA Security

We analyze the semantic security of the FHOPE scheme by proving the indistinguishability of ciphertexts under a homomorphic order-preserving chosen-plaintext attack.Theorem 10.
A FHOPE encryption scheme is IND-HOCPA secure.Proof.
In the following game, the PPT adversary is denoted asA and the challenger is denoted as CH. Consider any adversary A and any two sequences of values A ask for in the security game: v0=(v10,…,vn0) and v1=(v11,…,vn1).(1)
The key generation algorithm generates the keyK(n)=[k1→,k2→,…,kn→]=[(a1,b1),(a2,b1),…,(an,bn)], where (ai,bi)(1≤i≤n) is a list of pairs of integers, which are large prime numbers, ai∗bi>0, n>1, ai≠0 for 1≤i≤n,b1+⋯+bn-1≠0, and bn≠0.(2)
The adversaryA chooses two equal-length sequences of values v0 and v1 and sends them to the challenger CH.(3)
The challengerCH randomly encrypts vi0 and vi1 with key K(n) and outputs the ciphertext C0=(c01,…,c0n) or C1=(c11,…,c1n), where c01=a1∗b1∗vi0+Noise1(a1,r1,p1)+ξ0, c11=a1∗b1∗vi1+Noise1(a1,r1,p1)+ξ1, and ξb(b ∈0,1)∈[-∞,+∞]. The ciphertext Cb (b ∈0,1) is sent to the adversary A.(4)
Ifvi0≠0 and vi1≠0, then the expressions of a1∗b1∗vi0+Noise1(a1,r1,p1)+ξ0 and a1∗b1∗vi1+Noise1(a1,r1,p1)+ξ1 generate the same value from -∞ to +∞ with the same probability; since ξb is randomly sampled from the range [-∞,+∞], v0 and v1 have the same order relation. Hence, the advantage AdvFHOPE,AIND-HOCPA(k) of distinguishing is negligible.
In the following, we discuss the case wherevi0=0 and vi1≠0. The case where vi0≠0 and vi1=0 is similar.
Ifvi0=0 and vi1≠0, we have c01=Noise1(a1,r1,p1)+ξ0 or c11=a1∗b1∗vi1+Noise1(a1,r1,p1)+ξ1; depending on whether vi0 or vi1 is encrypted, v0 and v1 have the same order relation. Then, the advantage AdvFHOPE,AIND-HOCPA(k) is negligible.
The proofs for other sub-ciphertextsc0i and c1i(2≤i≤n) are carried out similarly; the advantage AdvFHOPE,AIND-HOCPA(k) is negligible.Therefore, the adversaryA cannot win the above game, and hence a FHOPE is IND-HOCPA secure.


## 7.3. Privacy Protection in Queries

The adversary can collect some useful statistical information after receiving query requests; it tries to guess the plaintext corresponding to the ciphertext based on statistical information. However, we will describe that the FHOPE scheme can reduce the privacy leakage greatly in this scenario.To solve the mentioned problem, we add some random noise in each sub-ciphertext. Letξi denote the random noise, which is randomly sampled from the range [-∞,+∞], and attu denote the column attribute of the database table. Then, the sub-ciphertext ci1(1≤i≤n) of v1 is expressed as Enci(K(n),v1)+Noisei(K(n),Ri1)+ξ1; the range of noise is different for different input values. Suppose ξ (default value is 0 if there are no sub-ciphertexts of attu stored on cloud server) denotes the latest noise. To store ci1 in the cloud server, the following steps need to be executed (if no sub-ciphertexts of attu are stored, jump to Step 2).Step 1.
Update all the stored sub-ciphertexts (cim) of attu by cim=cim+ξ1-ξ.Step 2.
Add random noiseξ1 in the new sub-ciphertexts by ci1=ci1+ξ1.Step 3.
Update the value ofξ by ξ=ξ1.Therefore, due to adding random noise, the ciphertext value is random. The same plaintexts are mapped to different ciphertexts. The random noise of the same attribute is continuously updated with the insertion of new data in the cloud database, and the adversary cannot guess the random noise.Consider a query SELECTcol1 FROM T WHERE col1>100. The col1 denotes the sensitive column in a table T; their values are encrypted and stored in a cloud database. The CL encrypts 100 using the FHOPE, and the values of col1, 100, share the same private key and random noise ξ. And col1 is encrypted as col1c. It delivers the query “SELECT col1c FROM T WHERE col1c>FHOPE(100)” to a CS. Since the data is in the encrypted form and the random noise of each ciphertext is different, the adversary cannot get any knowledge of the order information. The random noise of the same attribute is continuously updated with the insertion of new data in the cloud database (that is, the random noise of the same attribute is the same), and then the order of plaintexts remains in the ciphertexts in the cloud database. Then, the CS executes the query on encrypted data as if the data were not encrypted, and the adversary obtains the query results. Since the random noise is dynamically updated, the order of query results loses freshness. In other words, the repeated query is issued again, and the returned ciphertexts are different. Moreover, we used the restrictions of literature [10] for chosen-plaintext attack, even if the adversary can get the ciphertext of {v1,v2,…,vk}, where {v1,v2,…,vk} is a dense one, but the ciphertexts are disordered because they are obtained at different time. Therefore, previous query requests will not help the adversary to learn the privacy information, and the adversary cannot gradually find out the order information and get some useful statistical information after many query requests.


## 7.4. The Security of FHOPE Properties

Our security model securely realizes ideal properties in the presence of noncolluding semihonest adversary. For the sake of simplicity, we do it for the specific scenario of our properties, which involves CL and CS. We need to construct simulatorSimCS against adversary ACS that corrupts CS.Theorem 11.
The AD can securely perform addition operation on ciphertext in the presence of semihonest adversaryACS.Proof.
CL receives plaintextsv and v′ as input and then generates ciphertexts C of v and C′ of v′. Finally, C and C′ are returned to SimCS.
S i m C S simulates ACS as follows: it receives C and C′ as input and generates the sum of C and C′ by performing addition operation. SimCS sends the sum of C and C′ to ACS.
TheACS’s view contains encrypted data. In the real and ideal executions, the views of ACS are indistinguishable, because CL is trusted and the FHOPE is IND-HOCPA secure.The security proofs of MU, OC, EQ, and DI are similar to that of AD under the semihonest adversaryACS. We give only the theorems here.Theorem 12.
The MU can securely perform multiplication operation on ciphertext in the presence of semihonest adversaryACS.Theorem 13.
The OC can securely perform order comparison on ciphertext in the presence of semihonest adversaryACS.Theorem 14.
The EQ can securely perform equality checks on ciphertext in the presence of semihonest adversaryACS.Theorem 15.
The DI can securely perform complex operation on ciphertext in the presence of semihonest adversaryACS.


## 8. Evaluations

The section focuses on the testing of the FHOPE’s performance. We design four experiments to test its performance. Simultaneously, the correctness of FHOPE’s properties (such as additive homomorphism, multiplicative homomorphism, order-preserving, and data interoperability) is also checked in these experiments.The experiments configuration is under CentOS Linux with an Intel Xeon CPU E3-1226 Processor (3.3GHz) and the 16.0GB RAM, which has 4 processor cores. The prototype is built based on the architecture shown in Figure2. We implement the proposed prototype using Java language and MySQL 5.6. In our experiment, the secret key K(n) is configured to have n=6, with selection of a list of pairs of integers [(a1,b1), (a2,b2),(a3,b3), (a4,b4), (a5,b5), (a6,b6)], [(r1,p1), (r2,p2), (r3,p3), (r4,p4), (r5,p5), (r6,p6)], and ξi, where ai∗bi>0, ai≠0 for 1≤i≤6, b1+⋯+b5≠0, b6≠0, p1>-a2∗b1∗S, p6<a1∗b1∗S, r1<a1∗b1∗S, and r6<a6∗b1∗S. And a simple synthetic dataset is a table Tab with three sensitive columns A, B, and C, which has 1 million records. The values in each column are randomly generated integers.


### 8.1. Performance of Encryption and Decryption

The experiment shows the performance of encryption and decryption by comparing FHOPE scheme with the AES algorithm. In our experiment, we randomly generate 20000 integers, each of which has 6 digits. Then, we compare our scheme with the AES algorithm by testing the time cost of encryption and decryption. According to Figure5, the time cost of AES’s encryption and decryption exhibits exponential growth with respect to the number of integers; it costs 230 milliseconds to encrypt 20000 integers. And the FHOPE scheme costs 4 milliseconds to encrypt 20000 integers, which is about 57 times faster than AES algorithm for encryption. We can see that FHOPE scheme is also faster than AES for decryption. Thus our scheme is practically efficient and suitable for large batch of data encryption and decryption.Figure 5
Performance of encryption and decryption.


### 8.2. Performance of Homomorphic Operations

The FHOPE scheme has additive homomorphism, multiplicative homomorphism, and data interoperability. The polynomial evaluation can demonstrate these properties of the FHOPE scheme. Then, we test the performance of addition and multiplication with high-degree polynomials over ciphertexts. The polynomial is∑i=1Nxi, where x is the encryption of a randomly generated integers and has eight digits.Figure6 shows the cost of testing ∑i=1Nxi from N=1000 to N=9000. The experiment result shows the efficiency of FHOPE scheme for performing many addition and multiplication operations. For instance, the addition and multiplication operations for calculating ∑i=1Nxi take about 0.2 seconds while N=1000 and about 18.7 seconds while N=9000. The correctness of homomorphic addition, homomorphic multiplication, and data interoperability is also checked in the experiment.Figure 6
Time for running∑i=1Nxi over encrypted x.


### 8.3. Comparison with mOPE [24]

For evaluating the performance of the FHOPE’s order-preserving, we compare the FHOPE scheme with mOPE scheme using a simple synthetic dataset on which data insertion is executed. In order to test the performance of data insertion, we generateN (N∈[500,6000]) records and insert them into an encrypted database as shown in Figure 7.Figure 7
Comparison between FHOPE scheme and mOPE scheme.From Figure7, we can see that the mOPE scheme has the lowest performance. The FHOPE scheme is more efficient than the mOPE scheme. In mOPE scheme, the client and the server side need to interact with each other when encrypting a message, and the server needs to adjust the encoding tree to achieve balance when adding new nodes. Our scheme is constructed by some linear mathematical functions without any interaction, and it has a higher efficiency.


### 8.4. Comparison with CryptDB [35]

For testing, we select 10000 records randomly from tableTab. Our scheme is compared with CryptDB by executing three queries.[Range]: selectA from Tab where A<q.[Sum]: selectsum(A) from Tab where A<q.[Avg]: selectavg(B) from Tab where A<q.Letq control the queries’ selectivity, which is randomly sampled from the range [100,10000]. Figure 8 shows the time cost of FHOPE and CryptDB for performing the three queries, where the size of the table grows from 1K to 8K rows. The time cost is displayed as bar graph.Figure 8
Execution times of FHOPE and CryptDB for the three sample queries.
(a)
Range (b)
Sum (c)
AvgWe can get some observations from the experimental result.(1) CryptDB takes more time to execute the range queries than FHOPE, because the CryptDB uses mOPE to implement the comparison operations. The efficiency of mOPE is lower than FHOPE as shown in Figure 7. (2) For the sum and avg queries, the execution time of FHOPE is lower than CryptDB, because CryptDB employs Paillier’s homomorphic encryption scheme and UDFs (user-defined functions) to compute sum aggregates and averages. The low efficiency of Paillier’s homomorphic encryption scheme leads to the low efficiency of CryptDB. (3) To perform range, sum, and avg queries, CryptDB employs various encryption schemes. FHOPE makes up for CryptDB’s shortcoming, which can support homomorphic addition, homomorphic multiplication, order comparison, and equality checks.Moreover, CryptDB cannot support some operations, such as “A+B<q” and homomorphic multiplication. Therefore, CryptDB cannot support some complex SQL queries, for example, (1) query “select sum(A∗B) from Tab where A<q”, (2) query “select A from Tab where A∗B<1000”, (3) query “select B from Tab where A∗(A+B)>100”, and (4) query “select B from Tab where A∗B-100>10”. The FHOPE can support the above complex SQL queries. Since FHOPE can support addition, multiplication, order comparison, and equality checks and the FHOPE scheme has the property of the data interoperability, with the data interoperability, these operators (+, −, ×, <, >, and =) can be combined to formulate complex expressions (e.g., “A+B∗C<q”) in SQL queries. Then, the FHOPE can support complex SQL queries.The time cost of FHOPE and CryptDB for the range queries while we change the selectivity of the queries (by adjustingq) from 10% to 90% is shown in Figure 9. The queries time of FHOPE is less than that of CryptDB. From Figure 9, we can see that the queries overhead of FHOPE is approximate linear growth as the selectivity of the queries increases; it indicates that the FHOPE scheme has a good stability.Figure 9
Execution times versus selectivity.


## 8.1. Performance of Encryption and Decryption

The experiment shows the performance of encryption and decryption by comparing FHOPE scheme with the AES algorithm. In our experiment, we randomly generate 20000 integers, each of which has 6 digits. Then, we compare our scheme with the AES algorithm by testing the time cost of encryption and decryption. According to Figure5, the time cost of AES’s encryption and decryption exhibits exponential growth with respect to the number of integers; it costs 230 milliseconds to encrypt 20000 integers. And the FHOPE scheme costs 4 milliseconds to encrypt 20000 integers, which is about 57 times faster than AES algorithm for encryption. We can see that FHOPE scheme is also faster than AES for decryption. Thus our scheme is practically efficient and suitable for large batch of data encryption and decryption.Figure 5
Performance of encryption and decryption.


## 8.2. Performance of Homomorphic Operations

The FHOPE scheme has additive homomorphism, multiplicative homomorphism, and data interoperability. The polynomial evaluation can demonstrate these properties of the FHOPE scheme. Then, we test the performance of addition and multiplication with high-degree polynomials over ciphertexts. The polynomial is∑i=1Nxi, where x is the encryption of a randomly generated integers and has eight digits.Figure6 shows the cost of testing ∑i=1Nxi from N=1000 to N=9000. The experiment result shows the efficiency of FHOPE scheme for performing many addition and multiplication operations. For instance, the addition and multiplication operations for calculating ∑i=1Nxi take about 0.2 seconds while N=1000 and about 18.7 seconds while N=9000. The correctness of homomorphic addition, homomorphic multiplication, and data interoperability is also checked in the experiment.Figure 6
Time for running∑i=1Nxi over encrypted x.


## 8.3. Comparison with mOPE [24]

For evaluating the performance of the FHOPE’s order-preserving, we compare the FHOPE scheme with mOPE scheme using a simple synthetic dataset on which data insertion is executed. In order to test the performance of data insertion, we generateN (N∈[500,6000]) records and insert them into an encrypted database as shown in Figure 7.Figure 7
Comparison between FHOPE scheme and mOPE scheme.From Figure7, we can see that the mOPE scheme has the lowest performance. The FHOPE scheme is more efficient than the mOPE scheme. In mOPE scheme, the client and the server side need to interact with each other when encrypting a message, and the server needs to adjust the encoding tree to achieve balance when adding new nodes. Our scheme is constructed by some linear mathematical functions without any interaction, and it has a higher efficiency.


## 8.4. Comparison with CryptDB [35]

For testing, we select 10000 records randomly from tableTab. Our scheme is compared with CryptDB by executing three queries.[Range]: selectA from Tab where A<q.[Sum]: selectsum(A) from Tab where A<q.[Avg]: selectavg(B) from Tab where A<q.Letq control the queries’ selectivity, which is randomly sampled from the range [100,10000]. Figure 8 shows the time cost of FHOPE and CryptDB for performing the three queries, where the size of the table grows from 1K to 8K rows. The time cost is displayed as bar graph.Figure 8
Execution times of FHOPE and CryptDB for the three sample queries.
(a)
Range (b)
Sum (c)
AvgWe can get some observations from the experimental result.(1) CryptDB takes more time to execute the range queries than FHOPE, because the CryptDB uses mOPE to implement the comparison operations. The efficiency of mOPE is lower than FHOPE as shown in Figure 7. (2) For the sum and avg queries, the execution time of FHOPE is lower than CryptDB, because CryptDB employs Paillier’s homomorphic encryption scheme and UDFs (user-defined functions) to compute sum aggregates and averages. The low efficiency of Paillier’s homomorphic encryption scheme leads to the low efficiency of CryptDB. (3) To perform range, sum, and avg queries, CryptDB employs various encryption schemes. FHOPE makes up for CryptDB’s shortcoming, which can support homomorphic addition, homomorphic multiplication, order comparison, and equality checks.Moreover, CryptDB cannot support some operations, such as “A+B<q” and homomorphic multiplication. Therefore, CryptDB cannot support some complex SQL queries, for example, (1) query “select sum(A∗B) from Tab where A<q”, (2) query “select A from Tab where A∗B<1000”, (3) query “select B from Tab where A∗(A+B)>100”, and (4) query “select B from Tab where A∗B-100>10”. The FHOPE can support the above complex SQL queries. Since FHOPE can support addition, multiplication, order comparison, and equality checks and the FHOPE scheme has the property of the data interoperability, with the data interoperability, these operators (+, −, ×, <, >, and =) can be combined to formulate complex expressions (e.g., “A+B∗C<q”) in SQL queries. Then, the FHOPE can support complex SQL queries.The time cost of FHOPE and CryptDB for the range queries while we change the selectivity of the queries (by adjustingq) from 10% to 90% is shown in Figure 9. The queries time of FHOPE is less than that of CryptDB. From Figure 9, we can see that the queries overhead of FHOPE is approximate linear growth as the selectivity of the queries increases; it indicates that the FHOPE scheme has a good stability.Figure 9
Execution times versus selectivity.


## 9. Conclusion

In this paper, we have presented a novel FHOPE scheme that can support direct homomorphic addition, homomorphic multiplication, order comparison, and equality checks on the ciphertext. The FHOPE scheme can be applied in a cloud database environment, which still uses standard SQL statements and allows the cloud server to perform complex SQL queries over the encrypted data without repeated encryption. We have proved the security of our FHOPE scheme from four aspects: the security of the keyK(n), IND-HOCPA security, the privacy protection in queries, and the security of FHOPE properties. The security of the key K(n) is based on the AGCD problem. Moreover, we have implemented a prototype in Java and evaluated the performance of our scheme in terms of encryption, decryption, and homomorphic operations, and our scheme is compared with mOPE scheme and CryptDB. Through experiment, we prove that the FHOPE scheme incurs less overhead on computation. It is suitable for large batch of data encryption and decryption in cloud database systems.



---

*Source: 7383514-2018-07-03.xml*