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

1. IntroductionWith 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.

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 x D > E cannot be executed by CryptDB. How to design a practical encrypted scheme that supports different operators (+, -, x, <, >, =) 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, INDOCPA [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)

(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 probability P 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. Section 2 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. Hacigwmws 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. Hacigwmws'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. Hacigwmws 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 Section 7.

3.1. System Model. Figure 2 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.

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 [left arrow] 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 [left arrow] 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 [left arrow] Dec(sk, c). The CL runs Dec on the private key and a ciphertext c and obtains a plaintext V.

(4) Computation: res [left arrow] HAMOE([c.sub.1], ..., [c.sub.l]). HAMOE runs at the server, takes as input ciphertext [C.sub.1], ..., [c.sub.l], 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 vector K(n) and that m integers [v.sub.i] [member of] V(1 [less than or equal to] i [less than or equal to] m) are encrypted into m vectors [C.sub.1], [C.sub.2], ..., [C.sub.m], where [C.sub.i] = ([C.sub.i1], ..., [C.sub.im]).

Definition 2 (correctness). A FHOPE scheme for plaintext domain Z is correct if, for all security parameters k, for all K(n) [left arrow] KeyGen([1.sup.k]),

(1) for all v [member of] Z and for every C outcome of FHOPE(v, K(n)), Dec(K(n), C) = v;

(2) for all [v.sub.i] [member of] Z and for every C; outcome of FHOPE([v.sub.i], K(n)), Dec(K(n), [[summation].sup.m.sub.i=1] [C.sub.i]) = [[summation].sup.m.sub.i=1] [v.sub.i];

(3) for all [v.sub.i] [member of] Z and for every C; outcome of FHOPE([v.sub.i], K(n)), Dec(K(n), [C.sub.i] x [C.sub.j]) = [v.sub.i] x [v.sub.j];

(4) for all sequences se = {[v.sub.1], ..., [v.sub.m]} [member of] [Z.sup.m], for all pairs [v.sub.i], [v.sub.j] [member of] se, for all [C.sub.i], [C.sub.j] obtained as above, we have [v.sub.i] < [v.sub.j] [??] [C.sub.i] < [C.sub.j];

(5) for all [v.sub.i] [member of] Z and for every [C.sub.i] outcome of FHOPE([v.sub.i], K(n)), we have [v.sub.i] + [v.sub.j] x [v.sub.k] > [v.sub.l] [??] [C.sub.j] + [C.sub.j] x [C.sub.k] > [C.sub.l].

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) adversary A has only a negligible advantage [Adv.sup.IND-HOCPA.sub.FHOPE,A] 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 challenger CH runs the key generation algorithm KeyGen and generates sk [left arrow] KeyGen([1.sup.k]).

(2) The challenger CH and the adversary A engage in a polynomial number of rounds of interaction. For round i,

(1) the adversary A chooses two equal-length messages [v.sup.0.sub.i], [v.sup.1.sub.i] [member of] Z and sends them to the challenger CH;

(2) the challenger CH picks b [member of] {0,1} at random and leads the interaction for the Enc algorithm on inputs sk and [v.sup.b.sub.i] with the server CS, with the adversary A observing all the ciphertexts at CS.

(3) The adversary A outputs b', its guess for b.

We say that the adversary A wins the game if (1) its guess is correct (b = b') and (2) the sequences [{[v.sup.0.sub.i]}.sub.i] and [{[v.sup.1.sub.i]}.sub.i] have the same order relations (namely, for all i, j, [v.sup.0.sub.i] < [v.sup.0.sub.j] [??] [v.sup.1.sub.i] < [v.sup.1.sub.j]). That is, A wins the above game if [Adv.sup.IND-HOCPA.sub.FHOPE,A](k) is nonnegligible, where the adversary's advantage (k) in the above game is defined as

[Adv.sup.IND-HOCPA.sub.FHOPE,A](K) = [absolute value of Pr [[win.sup.A,k]] - 1/2], (1)

where [win.sup.A,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, Table 1 summarizes the notations employed in the paper.

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) = ([k.sub.1], [k.sub.2], ..., [k.sub.n]) is chosen randomly from real number set R.

Encrypt. A message m e R is encrypted into C = Enc(v, K(n)) = ([c.sub.1], ..., [c.sub.n]); 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 = ([c.sub.1], ..., [c.sub.n]); compute and output a message m:

m = Dec (K (n), ([c.sub.1], ..., [c.sub.n])). (2)

Our proposed scheme differs from that of [37] in that we focus on designing an encryption scheme that supports complex expressions containing different operators (+, -, x, <, >, 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

[mathematical expression not reproducible], (3)

where ([a.sub.i], [b.sub.i])(1 [less than or equal to] i [less than or equal to] n) is a list of pairs of integers, which are large prime numbers, [a.sub.i] * [b.sub.i] > 0, n > 1, [a.sub.i] = 0 for 1 [less than or equal to] i [less than or equal to] n, [b.sub.1] + ... + [b.sub.n-1] [not equal to] 0, and [b.sub.n] [not equal to] 0. The number of key components in the key set is equal to the number of subciphertexts.

Encrypt (Enc). Encrypt the plaintext FHOPE(v, K(n)) = ([c.sub.1], ..., [c.sub.n]), 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 [Enc.sub.i](K(n), v), [Noise.sub.i](K(n), R), and [[xi].sub.i] to define each q, as shown below, where Enci is a strictly increasing function over K(n) and v, in particular linear to v. [Noise.sub.i] is a function over K(n) and R, which calculates a random number for randomizing [c.sub.i], [[xi].sub.i] denote the random noise, which is randomly sampled from the range [-[infinity], +[infinity]], and a set R of n pairs of numbers {([r.sub.1], [p.sub.1]), ..., ([r.sub.n], [p.sub.1])} is defined in a finite integer domain. We define the functions [Enc.sub.i]() and [Noise.sub.i]() by (5) and (6), respectively.

[c.sub.i] = [Enc.sub.i] (K (n), v) + [Noise.sub.i] (K (n), R) + [[xi].sub.i] (4)

[Enc.sub.i] ([a.sub.i], [b.sub.i], v) = [a.sub.i] * [b.sub.i] * v, (5)

[mathematical expression not reproducible] (6)

The noise defined in (6) should satisfy condition (7).

0 < [Noise.sub.i] (K (n), R)

< ([Enc.sub.i] (K (n), v + S) - [Enc.sub.i] (K (n), v)). (7)

Decrypt (Dec). Decrypt a ciphertext C = ([c.sub.1], ..., [c.sub.n]), and get the plaintext v.

Dec(K(n), ([c.sub.1], ..., [c.sub.n])) = v, (8)

where K(n) = [([a.sub.1], [b.sub.1]), ([a.sub.2], [b.sub.2]), ..., ([a.sub.1], [b.sub.1])] is a secret key; v is a plaintext.

Then, the decryption algorithm is defined as

[n.summation over (i=1)] [Dec.sub.i] ([a.sub.i], [b.sub.1]) * [c.sub.1] = v, (9)

[Dec.sub.i] ([a.sub.i], [b.sub.1]) = 1/[a.sub.i] x [[summation].sup.n.sub.i=1] [b.sub.i] (10)

where [Dec.sub.i] 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 [c.sub.i] in (4), (8) is rewritten into (9), which is equal to

[n.summation over (i=1)] [Dec.sub.i] (K(n))

* ([Enc.sub.i] (K (n), v) + [Noise.sub.i] (K (n), R) + [[xi].sub.i]) = v. (11)

In order to ensure the validity of decryption steps in (9), it has to satisfy the conditions

[n.summation over (i=1)] [Dec.sub.i] (K(n)) * ([Enc.sub.i] (K (n), R) + [[xi].sub.i]) = 0, (12)

[n.summation over (i=1)] [Dec.sub.i] (K(n)) * [Enc.sub.i] (K (n), v) = v. (13)

Proof of Correctness for Decryption

Proof. To prove correctness of decryption, suppose that any [v.sub.1] [member of] Z is encrypted into [C.sub.1] = ([c.sub.11], ..., [c.sub.1n]) with the key K(n), as shown below.

[c.sub.1i] = [Enc.sub.i] (K (n), [v.sub.1] + [Noise.sub.i] (K (n), [R.sup.1.sub.i] + [xi]. (14)

Suppose that the first sub-ciphertext ([c.sub.11]) has order-preserving property, and random noise [xi] is added to the first and second sub-ciphertext, respectively. Then, we have to prove

Dec(K (n), ([c.sub.11], ..., [c.sub.1n]) = [v.sub.1]. (15)

That is,

[n.summation over (i=1)] [Dec.sub.i] (K (n)) * ([Enc.sub.i] (K (n), [v.sub.1]) + [Noise.sub.i] (K (n), R) + [xi]) = [v.sub.1], (16)

where

[Dec.sub.i] ([a.sub.i], [b.sub.1]) = 1/[a.sub.i] * [[summation].sup.n.sub.i=1] [b.sub.i]. (17)

We have

[mathematical expression not reproducible]. (18)

Because [a.sub.2] = -[a.sub.1] and [xi] [not equal to] 0, then

[n.summation over (i=1)] [Dec.sub.i] (K (n)) * [xi]1/[a.sub.i] * [[summation].sup.n.sub.i=1] [b.sub.i] * [b.sub.i] = 0. (19)

Then

[mathematical expression not reproducible]. (20)

Therefore, the correctness of decryption is proved.

To verify the correctness of operations supported by our scheme, suppose that we have a secret key vector K(n) and that m integers [v.sub.i] [member of] V(1 [less than or equal to] i [less than or equal to] m) are encrypted into m vectors [C.sub.1], [C.sub.2], ..., [C.sub.m], where [C.sub.i] = ([c.sub.i1], ..., [c.sub.in]).

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 (x, +, -, =, >, 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 x 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 columns col_A and col_B of a table T, their values are integers. We use [v.sub.i] and [v.sub.j] to denote the values of col_A and col_B in a row t, respectively. Let [C.sub.i] and [C.sub.j] be the encrypted values of [v.sub.i] and [v.sub.j], respectively, where [C.sub.i] = ([c.sub.i1], ..., [c.sub.in]) and [C.sub.j] = ([c.sub.j1], ..., [c.sub.jn]); they share the same secret key vector K(n).

Given two sensitive columns col_A and col_B, if the application issues the query SELECT c 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 of col_A and col_B with the private key K(n); their ciphertexts are [C.sub.i] = ([c.sub.i1], ..., [c.sub.in]) and [C.sub.j] = ([c.sub.j1], ..., [c.sub.jn]), 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: [C.sub.i] + [C.sub.j] = ([c.sub.i1] + [c.sub.j1], ..., [c.sub.in] + [c.sub.jn]), where the homomorphic addition of [C.sub.i] and [C.sub.j] 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(([[summation].sup.m.sub.i=1] [c.sub.i1], ..., [[summation].sup.m.sub.i=1] [c.sub.in]), K(n)) = [[summation].sup.m.sub.i=1] [v.sub.i].

Proof.

[mathematical expression not reproducible]. (21)

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 "x". Given two sensitive columns col_A and col_B of a table T, let [v.sub.1] and [v.sub.2] denote the values of col_A and col_B in a row t, respectively. Let [C.sub.1] and [C.sub.2] be the encrypted values of [v.sub.1] and [v.sub.2], respectively, where [C.sub.1] = ([c.sub.1l], ..., [C.sub.1n]) and [C.sub.2] = ([c.sub.21], ..., [c.sub.2n]); they share the same secret key vector K(n).

If the application issues the query SELECT * FROM Table 1 WHERE col_C = col_A x 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 of col_A and col_B with the private key K(n), and their ciphertexts are [C.sub.1] = ([c.sub.1l], ..., [C.sub.1n]) and [C.sub.2] = ([c.sub.2l], ..., [c.sub.2n]), 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:

[mathematical expression not reproducible], (22)

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 means Dec(K(n), [C.sub.1] x [C.sub.2]) = [v.sub.1] x [v.sub.2].

Proof. To prove this theorem, we first need to show that

[mathematical expression not reproducible]. (23)

Then, we prove Dec(K (n), [c.sub.11], [c.sub.12], [c.sub.1n]) x [v.sub.2]) = [v.sub.1] x [v.sub.2].

The details are given below.

Step 1. Perform the following decryption for i, 1 [less than or equal to] i [less than or equal to] n. Because we have

[mathematical expression not reproducible], (24)

then it gives

[mathematical expression not reproducible]. (25)

Step 2. We have from Step 1:

[mathematical expression not reproducible]. (26)

Hence, Dec(K(n), [C.sub.1] x [C.sub.2]) = [v.sub.1] x [v.sub.2]. 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 [v.sub.1] and [v.sub.2] denote the values of col_A and col_B in a row t, respectively. Let [C.sub.1] and [C.sub.2] be the encrypted values of [v.sub.1] and [v.sub.2], respectively; they share the same secret key vector K(n). For privacy protection, we calculate [v.sub.1] > [v.sub.2] or [v.sub.1] < [v.sub.2], the plaintexts need to be encrypted, and we need to calculate [C.sub.1] > [C.sub.2] or [C.sub.1] < [C.sub.2]. 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 orderpreserving property.

Suppose that any two integers [v.sub.1] and [v.sub.2] are encrypted into [C.sub.1] = ([C.sub.11], ..., [c.sub.1n]) and [C.sub.2] = ([c.sub.21], ..., [c.sub.2n]) with the key K(n), as shown below.

[c.sub.1i] = [Enc.sub.i] (K (n), [v.sub.1] + [Noise.sub.i] (K (n), [R.sup.1.sub.i]) + [xi] (27)

[c.sub.2i] = [Enc.sub.i] (K (n), [v.sub.2] + [Noise.sub.i] (K (n), [R.sup.2.sub.i]) + [xi] (28)

Definition 6. Let V = {[v.sub.1], [v.sub.2], ..., [v.sub.n]} be the set of all input plaintext values. The sensitivity of V is the minimum element in the set {[absolute value of [v.sub.1] - [v.sub.2]] | [v.sub.1] [member of] V, [v.sub.2] [member of] V, [v.sub.1] [not equal to] [v.sub.2]}. That is, the sensitivity S is defined as [mathematical expression not reproducible].

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 sensitivity S of input value V, for all [v.sub.1] [member of] V, [v.sub.2] [member of] V, if [v.sub.1] > [v.sub.2], then [C.sub.1] > [C.sub.2].

Proof. We have [C.sub.1] > [C.sub.2] if [c.sub.1i] > [c.sub.2i], where [c.sub.1i] and [c.sub.2i] (1 [less than or equal to] i [less than or equal to] n) are the sub-ciphertext of [C.sub.1] and [C.sub.2], respectively. Suppose that the sub-ciphertexts [c.sub.1i] and [c.sub.2i] have the same random noise [xi]. To prove this theorem, we need to show [c.sub.1i] - [c.sub.2i] > 0; that is,

[mathematical expression not reproducible]. (29)

In other words, we have to prove

[mathematical expression not reproducible]. (30)

Because the linear expression [Enc.sub.i](K(n), v) is strictly increasing for any plaintext v, we have

min {[Enc.sub.i] (K (n), [v.sub.1]) - [Enc.sub.i] (K (n), [v.sub.2])}

= Enc.sub.i] (K (n), [v.sub.2] + S) - [Enc.sub.i] (K (n), [v.sub.2]). (31)

Since [v.sub.1] > [v.sub.2], then the minimum [v.sub.1] is [v.sub.2] + S, which is bigger than [v.sub.2]. Moreover, [Noise.sub.i] (K(n), [R.sub.i] > 0; then,

max {[Noise.sub.i] (K (n), [R.sup.2.sub.i]) - [Noise.sub.i] (K (n), [R.sup.1.sub.i])}

= [Noise.sub.i] (K (n), [R.sup.2.sub.i]). (32)

Hence, the theorem holds if

[Noise.sub.i] (K (n), [R.sup.2.sub.i]) < [Enc.sub.i] (K (n), [v.sub.2] + S)

- [Enc.sub.i] (K (n), [v.sub.2]). (33)

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 keyword score into a ciphertext C = ([c.sub.1],..., [c.sub.n]) under the key K(n); the random noise is [xi], which is stored in the CL. Then the CL computes the range of the sub-ciphertext [c.sub.i] (1 [less than or equal to] i [less than or equal to] n) as follows:

[c.sub.i] = [Enc.sub.i] (K (n), score) + [Noise.sub.i] (K (n), [R.sub.i] + [xi], (34)

and because

0 < [Noise.sub.i] (K (n), [R.sub.i])

< ([Enc.sub.i] (K (n), score + S) - [Enc.sub.i] (K (n), score)), (35)

we have

[Enc.sub.i] (K (n), score) + [xi] < [c.sub.i]

< [Enc.sub.i] (K (n), score + S) + [xi], (36)

and the range ([Enc.sub.i] (K(n), score)+ [xi], [Enc.sub.i](K(n), score+ S) + [xi]) of the sub-ciphertext [c.sub.i] to the CS is sent.

Step 2. The CS compares the range of the sub-ciphertext [c.sub.i] 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 [c.sub.i], 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 (x, +, -, =, >, and <) can be combined to formulate complex expressions in SQL queries (e.g., SELECT * FROM Table 1 WHERE col_C + col_A x 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., if [v.sub.1] + [v.sub.2] x [v.sub.3] > [v.sub.4], then [C.sub.1] + [C.sub.2] x [C.sub.3] > [C.sub.4].

Proof. To prove this theorem, we need to show FHOPE([v.sub.1] + [v.sub.2] x [v.sub.3], K(n)) > FHOPE([v.sub.4], K(n)). According to Theorems 4, 5, and 7, we have

[mathematical expression not reproducible] (37)

The correctness of data interoperability is proved.

5.6. Improving Efficiency. In encryption algorithm Enc, some random noise [[xi].sub.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 [v.sub.1] is encrypted into [C.sub.1] = ([c.sup.1.sub.1], ..., [c.sup.1.sub.n]) 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 ([c.sup.1.sub.i]) of the n subciphertexts has order-preserving property. Another approach is to add random noise [[xi].sub.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.

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 plaintext v is m and the plaintext v is encrypted into C. Let [t.sub.e], [t.sub.i], and [t.sub.u] 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:

T = [t.sub.e] + [t.sub.i] + n x [t.sub.u] x P, (38)

where n x [t.sub.u] x 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

k = 1,

T(1) = [t.sub.e] + [t.sub.i] + n x [t.sub.u] x P, (39)

k = 2,

T(2) = T (1) + [t.sub.e] + [t.sub.i] + (n + 1) x [t.sub.u] x P, (40)

k = 3,

T (3) = T (2) + [t.sub.e] + [t.sub.i] + (n + 2) x [t.sub.u] x P, (41)

... (42)

k = N,

T (k) = T (k - 1) + [t.sub.e] + [t.sub.i] + (n + k - 1) x [t.sub.u] x P. (43)

Then,

T(N) = N x ([t.sub.e] + [t.sub.i]) + (n x N + 0.5 x N x (N - 1))

x [t.sub.u] x P. (44)

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.

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 Section 5, 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 [col.sub.1] x [col.sub.2] + 1000 > 6800. [col.sub.1] 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 [col.sub.1] and [col.sub.2], 1000 and 6800, share the same private key and random noise [xi]. [col.sub.1] and [col.sub.2] are encrypted as [col.sub.1]c and [col.sub.2]c, respectively. It delivers the query "SELECT * FROM T WHERE [col.sub.1]c x [col.sub.2]c + 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 key K(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 [??] 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 Key K(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 [d.sub.i] = h*[q.sub.i]+[l.sub.i] of h, where h, [q.sub.i], and [l.sub.i] are

integers, the problem is to find the hidden common divisor h. Note that [q.sub.i] and [l.sub.i] change in each [d.sub.i]. In particular, if [l.sub.i] can be as large as h, it is impossible to reconstruct h from any number of approximate multiples [d.sub.i] [40].

As we know, [mathematical expression not reproducible] is a secret vector. In the following, we prove that it is hard to recover the secret component [??] in a key K(n) from any number of ciphertexts.

Theorem 9. Given any number of ciphertexts from the FHOPE encryption with K(n), it is difficult to recover [??] in a key K(n).

Proof. As shown in the FHOPE encryption, a ciphertext C = ([c.sub.1], ..., [c.sub.n]) is defined as

[mathematical expression not reproducible]. (45)

In the first ciphertext element [c.sub.1], [a.sub.1] 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 [c.sub.1] of any number of ciphertexts.

Let [N.sub.1] = [Noise.sub.1] (K(n), [R.sub.1]) + [[xi].sub.1]. Then, we have [c.sub.1] = [a.sub.1] * [b.sub.1] * v + [N.sub.1]. Since [b.sub.1]] * v is random number generated for each encryption, [N.sub.1] is a number that the adversary does not know, and it randomly changes for each encryption of the plaintext. Moreover, [a.sub.1] can be less than [N.sub.1]. Hence, it is difficult to recover [a.sub.1] from the first element [c.sub.1] of any number of ciphertexts according to the hardness of the AGCD problem. The proofs for other secret values [a.sub.i] and [b.sub.i] 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 as A and the challenger is denoted as CH. Consider any adversary A and any two sequences of values A ask for in the security game: [v.sup.0] = ([v.sup.0.sub.1], ..., [v.sup.0.sub.n]) and [v.sub.1] = ([v.sup.0.sub.1], ..., [v.sup.1.sub.n]).

(1) The key generation algorithm generates the key [mathematical expression not reproducible] is a list of pairs of integers, which are large prime numbers, [a.sub.i] * [b.sub.i] > 0, n > 1, [a.sub.i] [not equal to] 0 for 1 [less than or equal to] i [less than or equal to] n, [b.sub.1] + ... + bn-1 = 0, and [b.sub.n-1] [not equal to] 0,

(2) The adversary A chooses two equal-length sequences of values [v.sup.0] and [v.sub.1] and sends them to the challenger CH.

(3) The challenger CH randomly encrypts [v.sup.0.sub.i] and [v.sup.1.sub.i] with key K(n) and outputs the ciphertext [C.sub.0] = ([c.sub.01], ..., [c.sub.0n]) or [C.sub.1] = ([C.sub.11], ..., [C.sub.1n]), where [c.sub.01] = [a.sub.1] * [b.sub.1] * [v.sup.0.sub.i] + [Noise.sub.1]([a.sub.1], [r.sub.1], [p.sub.1]) + [[xi].sub.0], [C.sub.11] = [a.sub.1] * [b.sub.1] * [v.sub.1] + [Noise.sub.1] ([a.sub.1], [r.sub.1], [p.sub.1]) + [[xi].sub.1], and [[xi].sub.b] (b [member of] {0, 1}) [member of] [-[infinity], +[infinity]]. The ciphertext [C.sub.b] (b [member of] {0, 1}) is sent to the adversary A.

(4) If [v.sup.0.sub.i] [not equal to] 0 and [v.sup.1.sub.i] [not equal to] 0, then the expressions of [a.sub.1] * [b.sub.1] * [v.sup.0.sub.i] + [Noise.sub.1] ([a.sub.1], [r.sub.1], [p.sub.1]) + [[xi].sub.0] and [a.sub.1] * [b.sub.1] * [v.sup.1.sub.i] + [Noise.sub.1] ([a.sub.1], [r.sub.1], [p.sub.1]) + [[xi].sub.1] generate the same value from -[infinity] to +[infinity] with the same probability; since [[xi].sub.b] is randomly sampled from the range [-[infinity], +[infinity]], [v.sup.0] and [v.sub.1] have the same order relation. Hence, the advantage [Adv.sup.IND-HOCPA.sub.FHOPE,A](k) of distinguishing is negligible.

In the following, we discuss the case where [v.sup.0.sub.i] = 0 and [v.sup.1.sub.i] [not equal to] 0. The case where [v.sup.0.sub.i] [not equal to] 0 and [v.sup.1.sub.i] = 0 is similar.

If [v.sup.0.sub.i] = 0 and [v.sup.1.sub.i] [not equal to] 0, we have [c.sub.01] = [Noise.sub.1]([a.sub.1], [r.sub.1], [p.sub.1]) + [[xi].sub.0] or [C.sub.11] = [a.sub.1] * [b.sub.1] * [v.sub.1] + [Noise.sub.1] ([a.sub.1], [r.sub.1], [p.sub.1]) + [[xi] .sub.1]; depending on whether [v.sup.0.sub.i] or [v.sup.1.sub.i] is encrypted, [v.sup.0] and [v.sup.1] have the same order relation. Then, the advantage [Adv.sup.IND-HOCPA.sub.FHOPE,A](k) is negligible.

The proofs for other sub-ciphertexts [c.sub.0i] and [C.sub.1i] (2 [less than or equal to] i [less than or equal to] n) are carried out similarly; the advantage [Adv.sup.IND-HOCPA.sub.FHOPE,A](k) is negligible.

Therefore, the adversary A 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 [[xi].sub.i] denote the random noise, which is randomly sampled from the range [-[infinity], +[infinity]], and attu denote the column attribute of the database table. Then, the sub-ciphertext [c.sup.1.sub.i] (1 [less than or equal to] i [less than or equal to] n) of [v.sub.1] is expressed as [Enc.sub.i](K(n), [v.sub.1]) + [Noise.sub.i] (K(n), [R.sup.1.sub.i]) + [[xi].sub.1]; the range of noise is different for different input values. Suppose [xi] (default value is 0 if there are no sub-ciphertexts of attu stored on cloud server) denotes the latest noise. To store [c.sup.1.sub.i] 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 ([c.sup.m.sub.i]) of attu by [c.sup.m.sub.i] = [c.sup.m.sub.i] + [[xi].sub.1] - [xi].

Step 2. Add random noise [[xi].sub.1] in the new sub-ciphertexts by [c.sup.1.sub.i] = [c.sup.1.sub.i] + [[xi].sub.1].

Step 3. Update the value of [xi] by [xi] = [[xi].sub.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 SELECT [col.sub.1] FROM T WHERE [col.sub.1] > 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 [col.sub.1], 100, share the same private key and random noise [xi]. And col1 is encrypted as col1c. It delivers the query "SELECT col1c FROM T WHERE col1c > PHOPE(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 {[v.sub.1], [v.sub.2], ..., [v.sub.k]}, where {[v.sub.1], [v.sub.2], ..., [v.sub.k]} 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 simulator [Sim.sub.CS] against adversary [A.sub.CS] that corrupts CS.

Theorem 11. The AD can securely perform addition operation on ciphertext in the presence of semihonest adversary [A.sub.CS].

Proof. CL receives plaintexts v and v' as input and then generates ciphertexts C of v and C' of v'. Finally, C and C' are returned to [Sim.sub.CS].

[Sim.sub.CS] simulates [A.sub.CS] as follows: it receives C and C' as input and generates the sum of C and C' by performing addition operation. [Sim.sub.CS] sends the sum of C and C' to [A.sub.CS].

The [A.sub.CS]'s view contains encrypted data. In the real and ideal executions, the views of [A.sub.CS] 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 adversary [A.sub.CS]. We give only the theorems here.

Theorem 12. The MU can securely perform multiplication operation on ciphertext in the presence of semihonest adversary [A.sub.CS].

Theorem 13. The OC can securely perform order comparison on ciphertext in the presence of semihonest adversary [A.sub.CS].

Theorem 14. The EQ can securely perform equality checks on ciphertext in the presence of semihonest adversary [A.sub.CS].

Theorem 15. The DI can securely perform complex operation on ciphertext in the presence of semihonest adversary [A.sub.CS].

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 Figure 2. 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 [mathematical expression not reproducible]. 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 Figure 5, 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.

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 [[summation].sup.N.sub.i=1] [x.sup.i], where x is the encryption of a randomly generated integers and has eight digits.

Figure 6 shows the cost of testing [[summation].sup.N.sub.i=1] [x.sup.i] 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 [[summation].sup.N.sub.i=1] [x.sup.i] 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.

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 generate N (N e [500, 6000]) records and insert them into an encrypted database as shown in Figure 7.

From Figure 7, 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 table Tab. Our scheme is compared with CryptDB by executing three queries.

[Range]: select A from Tab where A < q.

[Sum]: select sum(A) from Tab where A < q.

[Avg]: select avg(B) from Tab where A < q.

Let q 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.

We 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 (+, -, x, <, >, 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 adjusting q) 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.

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 key K(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.

https://doi.org/10.1155/2018/7383514

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 61572263, Grant 61502251, Grant 61502243, and Grant 61602263, the Natural Science Foundation of Jiangsu Province under Grant BK20161516 and Grant BK20151511, the Natural Science Foundation of Anhui Province under Grant 1608085MF127, the Natural Science Foundation of Educational Commission of Anhui Province of China under Grant KJ2016B17, Grant KJ2015B19, and Grant KJ2017B15, China Postdoctoral Science Foundation under Grant 2016M601859 and Grant 2015M581794, Qing Lan Project of Jiangsu Province, 1311 Talent Plan Foundation of NuPT, NUPTSF, under Grant NY216001, and the Natural Science Foundation of the Jiangsu Higher Education Institutions of China under Grant 14KJB520031 and Grant 15KJB520027.

References

[1] H. Wang, D. He, J. Yu, and Z. Wang, "Incentive and Unconditionally Anonymous Identity-Based Public Provable Data Possession," IEEE Transactions on Services Computing, pp. 1-1.

[2] H. Wang, D. He, and J. Han, "VOD-ADAC: Anonymous Distributed Fine-Grained Access Control Protocol with Verifiable Outsourced Decryption in Public Cloud," IEEE Transactions on Services Computing, pp. 1-1.

[3] W. Li, K. Xue, Y. Xue, and J. Hong, "TMACS: A Robust and Verifiable Threshold Multi-Authority Access Control System in Public Cloud Storage," IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 5, pp. 1484-1496, 2016.

[4] K. Xue, Y. Xue, J. Hong et al., "RAAC: Robust and Auditable Access Control with Multiple Attribute Authorities for Public Cloud Storage," IEEE Transactions on Information Forensics and Security, vol. 12, no. 4, pp. 953-967, 2017

[5] R. Agrawal, J. Kiernan, R. Srikant, and Y. R. Xu, "Order preserving encryption for numeric data," in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD '04), pp. 563-574, ACM, Paris, France, June 2004.

[6] K. Li, W. Zhang, C. Yang, and N. Yu, "Security Analysis on One-to-Many Order Preserving Encryption-Based Cloud Data Search," IEEE Transactions on Information Forensics and Security, vol. 10, no. 9, pp. 1918-1926, 2015.

[7] C. Gentry, "Fully homomorphic encryption using ideal lattices," in Proceedings of the 41st annual ACM symposium on Theory of Computing (STOC '09), vol. 9, pp. 169-178, ACM, Bethesda, Md, USA, 2009.

[8] X. Liu, K. R. Choo, R. H. Deng, R. Lu, and J. Weng, "Efficient and Privacy-Preserving Outsourced Calculation of Rational Numbers," IEEE Transactions on Dependable and Secure Computing, vol. 99, 2016.

[9] D. Liu and S. Wang, "Nonlinear order preserving index for encrypted database query in service cloud environments," Concurrency and Computation: Practice and Experience, vol. 25, no. 13, pp. 1967-1984, 2013.

[10] Z. Liu, X. Chen, J. Yang, C. Jia, and I. You, "New order preserving encryption model for outsourced databases in cloud environments," Journal of Network and Computer Applications, vol. 59, pp. 198-207, 2016.

[11] C. Gentry, S. Halevi, and N. P. Smart, "Fully homomorphic encryption with polylog overhead," in Proceedings of the 31st Annual International Conference on the Theory and Applications ofCryptographic Techniques, pp. 465-482, 2012.

[12] W. Wang, Y. Hu, L. Chen, X. Huang, and B. Sunar, "Exploring the feasibility of fully homomorphic encryption," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 64, no. 3, pp. 698-706, 2015.

[13] A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill, "Order-preserving symmetric encryption," in Advances in Cryptology-EUROCRYPT 2009, vol. 5479, pp. 224-241, Springer, Berlin, Germany, 2009.

[14] H. Wang, D. He, and S. Tang, "Identity-Based Proxy-Oriented Data Uploading and Remote Data Integrity Checking in Public

Cloud," IEEE Transactions on Information Forensics and Security, vol. 11, no. 6, pp. 1165-1176, 2016.

[15] H. Wang, "Identity-based distributed provable data possession in multi-cloud storage," IEEE Transactions on Services Computing, vol. 8, no. 2, pp. 328-340, 2015.

[16] Z. Brakerski and V. Vaikuntanathan, "Efficient fully homomorphic encryption from (standard) LWE," Foundations of Computer Science IEEE, vol. 2011, pp. 97-106, 2011.

[17] N. Smart and F. Vercauteren, "Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes," in Proceedings of the International Conference on Practice and Theory in Public Key Cryptography Springer-Verlag, vol. 6056, pp. 420-443, 2010.

[18] Y. n. Doroz, Y. Hu, and B. Sunar, "Homomorphic AES evaluation using the modified LTV scheme," Designs, Codes and Cryptography. An International Journal, vol. 80, no. 2, pp. 333-358, 2016.

[19] J. H. Cheon, J.-S. Coron, J. Kim et al., "Batch fully homomorphic encryption over the integers," in Proceedings of the Advances in Cryptology-EUROCRYPT2013, vol. 7881, pp. 315-335, Springer, New York, NY, USA, 2013.

[20] X. Cao, C. Moore, M. O'Neill, E. O'Sullivan, and N. Hanley, "Optimised multiplication architectures for accelerating fully homomorphic encryption," Institute ofElectrical and Electronics Engineers. Transactions on Computers, vol. 65, no. 9, pp. 2794-2806, 2016.

[21] J. H. Cheon and D. Stehl'E, "Fully homomophic encryption over the integers revisited," in Advances in Cryptology-EUROCRYPT 2015, vol. 9056, pp. 513-536, Springer, New York, NY, USA, 2015.

[22] L. Xiao, I.-L. Yen, and D. T. Huynh, "A note for the ideal order-preserving encryption object and generalized order-preserving encryption," in IACR Cryptology Eprint Archive, 2012.

[23] A. Boldyreva, N. Chenette, and A. O'Neill, "Order-preserving encryption revisited: improved security analysis and alternative solutions," in Proceedings of the 31st annual conference on Advances in cryptology, vol. 6841, pp. 578-595, Springer-Verlag, 2011.

[24] R. A. Popa, F H. Li, and N. Zeldovich, "An ideal-security protocol for order-preserving encoding," in Proceedings of the 34th IEEE Symposium on Security and Privacy, SP 2013, pp. 463-477, May 2013.

[25] H. Hacigumus, B. Iyer, C. Li, and S. Mehrotra, "Executing SQL over encrypted data in the database-service-provider model," in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD '02),pp. 216-227, New York, NY, USA, June 2002.

[26] R. Popa, N. Zeldovich, and H. Balakrishnan, "CryptDB: A Practical Encrypted Relational DBMS," Tech. Rep. MIT-CSAILTR-2011-005, MIT, 2011.

[27] J. Li, Z. Liu, X. Chen, F. Xhafa, X. Tan, and D. S. Wong, "L-EncDB: A lightweight framework for privacy-preserving data queries in cloud computing," Knowledge-Based Systems, vol. 79, pp. 18-26, 2015.

[28] Z. Yang, S. Zhong, and R. Wright, "Privacy-preserving queries on encrypted data," in Proceedings of the Computer Security CESORICS, pp. 479-495, 2006.

[29] B. Hore, S. Mehrotra, and G. Tsudik, "Aprivacypreserving index for range queries," in Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB'04, vol. 30, pp. 720-731, 2004.

[30] K. Xue, S. Li, J. Hong, Y. Xue, N. Yu, and P. Hong, "Two-Cloud Secure Database for Numeric-Related SQL Range Queries with Privacy Preserving," IEEE Transactions on Information Forensics and Security, vol. 12, no. 7, pp. 1596-1608, 2017

[31] W. Ding, Z. Yan, and R. H. Deng, "Encrypted data processing with Homomorphic Re-Encryption," Information Sciences, vol. 409-410, pp. 35-55, 2017.

[32] X. Liu, R. H. Deng, W. DIng, R. Lu, and B. Qin, "Privacy-preserving outsourced calculation on floating point numbers," IEEE Transactions on Information Forensics and Security, vol. 11, no. 11, pp. 2513-2527, 2017.

[33] Z. Yan, W. Ding, V. Niemi, and A. V. Vasilakos, "Two schemes of privacy-preserving trust evaluation," Future Generation Computer Systems, vol. 62, pp. 175-189, 2015.

[34] A. Peter, E. Tews, and S. Katzenbeisser, "Efficiently outsourcing multiparty computation under multiple keys," IEEE Transactions on Information Forensics and Security, vol. 8, no. 12, pp. 2046-2058, 2013.

[35] R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan, "CryptDB: Protecting confidentiality with encrypted query processing," in Proceedings of the 23rd ACM Symposium on Operating Systems Principles, SOSP 2011, pp. 85-100, prt, October 2011.

[36] W. K. Wong, B. Kao, D. W. L. Cheung, R. Li, and S. M. Yiu, "Secure query processing with data interoperability in a cloud database environment," in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD 2014, pp. 1395-1406, June 2014.

[37] D. Liu, Homomorphic Encryption for Database Querying:Australian, WO/2013/188929, 2013.

[38] F. D. McSherry, "Privacy integrated queries: an extensible platform for privacy-preserving data analysis," in Proceedings of the 35th SIGMOD international conference on Management of data, SIGMOD'09, pp. 19-30, Providence, Rhode Island, USA, June 2009.

[39] J. H. Silverman, "Cryptography and lattices," in Lecture Notes in Computer Science, vol. 2146 of chapter Approximate Integer Common Divisors, pp. 51-66, 2001.

[40] H. Cohn and N. Heninger, "Approximate common divisors via lattices," in IACR Cryptology Eprint Archive, 2011.

Guoxiu Liu, (1,2) Geng Yang (iD), (1,3) Huaqun Wang, (1) Yang Xiang, (4) and Hua Dai (iD) (1,3)

(1) Nanjing University of Posts and Telecommunications, Nanjing 210003, China

(2) School of Computer and Information Engineering, Chuzhou University, Chuzhou 239000, China

(3) Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing 210003, China

(4) School of Information Technology, Deakin University, 221 Burwood Highway, Burwood, VIC 3125, Australia

Correspondence should be addressed to Geng Yang; yangg@njupt.edu.cn

Received 6 January 2018; Revised 5 May 2018; Accepted 30 May 2018; Published 3 July 2018

Academic Editor: Emanuele Maiorana

Caption: 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.

Caption: Figure 2: System model for outsourced databases.

Caption: Figure 3: The relationship between time cost and probability.

Caption: Figure 4: The relationship between time cost and numbers.

Caption: Figure 5: Performance of encryption and decryption.

Caption: Figure 6: Time for running [[summation].sup.N.sub.i=1] [x.sup.i] over encrypted x.

Caption: Figure 7: Comparison between FHOPE scheme and mOPE scheme.

Caption: Figure 8: Execution times of FHOPE and CryptDB for the three sample queries.

Caption: Figure 9: Execution times versus selectivity.

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 [c.sub.i] i-th sub-ciphertext k security parameter K(n) a secret key is comprised of a set ofkey components [k.sub.i] i-th key component Enc() a function for encryption Dec() a function for decryption [Enc.sub.i() a strictly increasing function over K(n) and v [Noise.sub.i() a function over K(n) and R S the sensitivity of input values v

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Liu, Guoxiu; Yang, Geng; Wang, Huaqun; Xiang, Yang; Dai, Hua |

Publication: | Security and Communication Networks |

Date: | Jan 1, 2018 |

Words: | 11761 |

Previous Article: | Street-Level Landmark Evaluation Based on Nearest Routers. |

Next Article: | Network Security and Management in SDN. |

Topics: |