# Order-Revealing Encryption Scheme with Comparison Token for Cloud Computing

Authors: Jingjing Guo; Jiacong Sun
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Order-preserving encryption (OPE) is a basic paradigm for the outsourced database where the order of plaintexts is kept in ciphertexts. OPE enables efficient order comparison execution while providing privacy protection. Unfortunately, almost all the previous OPE schemes either require numerous rounds of interactions or reveal more information about the encrypted database (e.g., the most significant bit). Order-revealing encryption (ORE) as a generalization is an encryption scheme where the order of plaintexts can be evaluated by running a comparison algorithm. Therefore, it is desirable to design an efficient ORE scheme which addresses above efficiency and security issues. In this paper, we propose a noninteractive ORE scheme from prefix encoding and Bloom filter techniques. The proposed scheme is an encryption scheme where a cloud service provider cannot evaluate the order of plaintexts until a comparison token is provided. The security analysis illustrates that our scheme achieves ideal security with frequency hiding. Furthermore, we illustrate a secure range query scheme through designing an encrypted tree structure named PORE tree from the above ORE scheme. The PORE tree reveals the order between different nodes and leaves encrypted data items in the same node incomparable even after query execution. Finally, the experimental evaluation shows the high efficiency of the proposed ORE scheme and range query scheme.


---

## Body

## 1. Introduction

The rapid development of cloud computing enables resource-constrained data owners to outsource their data storage and computational tasks to a cloud service provider. The outsourced data could be attacked by outside attackers and the cloud service provider, for example, Verizon cloud leak and Equifax data breach. Thus, sensitive data should be encrypted before outsource, such as CryptDB, CipherCloud, and PRS server. Encryption is a promising approach for protecting sensitive data. However, traditional encryption breaks correlation of plaintexts and brings many difficulties in ordinary services, such as keyword search, numeric operations, and range query. Although some advanced cryptography primitives such as fully homomorphic encryption [1–3] and functional encryption [4–6] are introduced, the existing schemes are somewhat inefficient.One method to enable efficient query services while meeting privacy requirement is to introduce an encryption scheme that allows only limited services. Searchable encryption [7–9] has been introduced to handle the keyword search in an encrypted database (EDB) [10, 11]. To execute range queries [12, 13], order-preserving encryption (OPE) [14–17] and its generalization order-revealing encryption (ORE) [18–20] have been proposed and developed.OPE provides a property that the order of ciphertexts retains that of plaintexts. It has many applications in real-world scenarios, such as in SQL queries [16, 21–23], Web applications [24], CRM software [25], and others. The concept of OPE is firstly proposed by Agrawal et al. [14] while without security analysis. As an improvement, Boldyreva et al. [15] introduced a provable OPE scheme called BCLO that provides security models and rigorous analysis from cryptography point. The ideal security of OPE requires that ciphertexts reveal nothing except the order of plaintexts. The BCLO scheme also points out that ideal security is unachievable if an OPE scheme is immutable and stateless. Therefore, the BCLO scheme is later shown to leak half of plaintext bits. To enhance security, Popa et al. [16] introduced a mutable OPE scheme named MOPE by leveraging binary tree. The OPE scheme achieves ideal security especially indistinguishability under an order chosen-plaintext attack (IND-OCPA). Unfortunately, the ideally secure scheme [16] requires Ologn-round of interactions.Different from previous OPE schemes, Boneh et al. [18] proposed a generalization definition of the order-revealing encryption scheme which reveals the order of plaintexts. Due to the heavy computation burden of multilinear maps, the scheme [18] is impractical and remains a theoretical result for most applications. Chenette et al. [26] introduced a practical ORE scheme called CLWW that sacrifices the index of first different bit. Lewi and Wu [27] designed an ORE scheme named Lewi-Wu ORE that makes a trade-off between efficiency and security. But, the scheme [27] scales linearly with the size of domain space and reveals the index of first different block. As security improvement, Cash et al. [19] proposed a parameter-hiding order-revealing encryption by using asymmetric bilinear map to construct property-preserving hash (PPH) as the heart of the scheme. Unfortunately, the parameter-hiding ORE has a heavy computation burden and is vulnerable to frequency attacks.


### 1.1. Our Contributions

In this work, we focus on the construction of the order-revealing encryption scheme over the encrypted database system in cloud computing. The main contributions are as follows:(i)
We introduce a noninteractive ORE scheme over the encrypted database by leveraging Bloom filter and prefix encoding technologies. The security analysis demonstrates that our ORE scheme achieves ideal security and also hides frequency information of data items.(ii)
The introduced ORE scheme leaves encrypted data items incomparable until a comparison provided. Since the encrypted data items are incomparable, our ORE scheme can resist file-injection attacks [28].(iii)
We further present its application in secure range query on an encrypted database. Specifically, data items are stored in a tree structure (e.g., B-tree) to enhance search efficiency. We apply the introduced ORE scheme to encrypt the data items in the tree node and thus construct an encrypted tree, which is referred as PORE tree.(iv)
The presented PORE tree reveals order relation between different tree nodes and leaves encrypted data items in same node incomparable even after query execution.This paper is an extended and enhanced version of the conference paper presented at ISPEC 2018 [17]. Compared with the conference version, we design a new ORE scheme which achieves ideal security with frequency hiding as an enhanced security of conference version with leakage function. The detailed description is depicted in Section 4. Furthermore, we modify the stored contents of PORE tree in Section 5. The proposed PORE tree achieves better security and efficiency. Moreover, formal security definition is presented in Section 3.2, and revised analysis according to the improved ORE scheme is introduced in Section 6. Finally, we add the experimental evaluation to evaluate the performance of MOPE [16], Lewi-Wu ORE [27], and our ORE scheme in Section 7.


### 1.2. Related Work

Order comparison [29] is one of the most popular operation in database-as-a-service (DaaS). In order to protect sensitive data, encryption is introduced as a prevailing consensus method. Numerous researchers have studied the problem of designing a secure and efficient encryption scheme which allows untrusted cloud servers to perform order comparison operation over ciphertexts. Due to heavy computation time and ciphertext size, fully homomorphic encryption and functional encryption are still impractical to handle order comparison [1, 2, 30]. Therefore, practical OPE schemes have proposed in the past few years [14–16, 31].Agrawal et al. [14] formalized the definition of order-preserving encryption and designed an OPE scheme. It transforms plaintexts into ciphertexts which retain the order and follow a target distribution provided by the client. In [14], the authors gave no security analysis and their scheme only applies for the static system. As an improvement, Boldyreva et al. [15] proposed the ideal security definition and further proved that an OPE scheme with immutable and stateless is impossible to achieve ideal security. The illustrated BCLO scheme in [15] is indistinguishable from a ROPF and later shows that it leaks more than half of plaintext bits [32, 33]. Moving a step forward, Dyer et al. [34] introduced an OPE scheme by using approximate integer common divisor problem. However, Dyer et al.’s scheme achieves window one-wayness security. There exist other OPE schemes [21–23, 33] with weaker security guarantee by making some impractical assumptions.Popa et al. [16] firstly introduced an ideally secure order-preserving encoding scheme named MOPE by using a balanced search tree and mutable ciphertexts. Mutable ciphertexts mean that encodings for several plaintext change with a deletion and insertion operation. The security on MOPE shows it is, in principle, possible to reveal no additional information besides orders. Kerschbaum [35] indicated each (deterministic) OPE scheme suffers a simple frequency attack from ciphertexts. For this reason, he provided a stronger security definition and indistinguishability under frequency analysis ordered chosen-plaintext attack (IND-FAOCPA). Based on random ciphertexts, the scheme [35] hides frequency information and achieves IND-FAOCPA security. Enlightened by a buffer tree [36], Roche et al. [37] constructed an order-preserving tree and further proposed a partial order-preserving encoding (POPE) scheme which supports the insert-heavy database and leaks partial orders. Unfortunately, all above schemes limit by multiple round of interactions between clients and cloud servers.Boneh et al. [18] provided a generalization definition of ORE. Different from traditional OPE, ORE reveals the order of plaintexts. They designed an ORE scheme by using multilinear maps. Because of the heavy computation burden of multilinear maps, the scheme [18] is impractical in most applications. The CLWW scheme [26] is the first practical ORE scheme by using PRFs. For each bit of data items, a keyed PRF takes this bit concatenated with all more significant bits as input. Thus, the ciphertexts include n elements which are the numerically sum of the keyed PRF and the next less significant bit. But, the CLWW scheme leaks the index of first different bit of two plaintexts. In order to balance security and efficiency, Lewi and Wu [27] introduced a generalization of the ORE scheme by using the left/right framework. The scheme of the small domain in [27] scales linearly with the size of message space and large domain reveals the first differing block. Based on bilinear map techniques, Cash et al. [19] proposed a more secure ORE scheme which leaks the equality pattern of the most significant bit.Several related works about multiclient have been introduced. Xiao et al. [33] gave a method to extend the OPE scheme to multiclient scenario which only supports the OPE system not ORE. As an improvement, two multiclient order-revealing encryption (MC-ORE) schemes [38] have been proposed by using the design principle of the CLWW scheme. Obviously, MC-ORE schemes are proven secure with different leakage functions. Li et al. [20] introduced and designed the delegatable order-revealing encryption (DORE) scheme for the multiclient system. The DORE scheme reveals the index of the first different bit between two plaintexts. Latest, some attack schemes have been introduced, such as inference attack [39], file-injection attack [28], and multicolumn attack [40]. However, most of these attack schemes require auxiliary information which limits the application in practical.


### 1.3. Organization

The rest of this paper is organized as follows. In Section2, we introduce some preliminaries. The system model and ORE definition are illustrated in Section 3. Then, in Section 4, we propose a PORE scheme by leveraging prefix encoding and Bloom filter techniques. We demonstrate its application on secure range query in Section 5. The security and efficiency analysis are illustrated in Section 6. In Section 7, we provide a performance evaluation of our scheme. Finally, the conclusions are presented in Section 8.


## 1.1. Our Contributions

In this work, we focus on the construction of the order-revealing encryption scheme over the encrypted database system in cloud computing. The main contributions are as follows:(i)
We introduce a noninteractive ORE scheme over the encrypted database by leveraging Bloom filter and prefix encoding technologies. The security analysis demonstrates that our ORE scheme achieves ideal security and also hides frequency information of data items.(ii)
The introduced ORE scheme leaves encrypted data items incomparable until a comparison provided. Since the encrypted data items are incomparable, our ORE scheme can resist file-injection attacks [28].(iii)
We further present its application in secure range query on an encrypted database. Specifically, data items are stored in a tree structure (e.g., B-tree) to enhance search efficiency. We apply the introduced ORE scheme to encrypt the data items in the tree node and thus construct an encrypted tree, which is referred as PORE tree.(iv)
The presented PORE tree reveals order relation between different tree nodes and leaves encrypted data items in same node incomparable even after query execution.This paper is an extended and enhanced version of the conference paper presented at ISPEC 2018 [17]. Compared with the conference version, we design a new ORE scheme which achieves ideal security with frequency hiding as an enhanced security of conference version with leakage function. The detailed description is depicted in Section 4. Furthermore, we modify the stored contents of PORE tree in Section 5. The proposed PORE tree achieves better security and efficiency. Moreover, formal security definition is presented in Section 3.2, and revised analysis according to the improved ORE scheme is introduced in Section 6. Finally, we add the experimental evaluation to evaluate the performance of MOPE [16], Lewi-Wu ORE [27], and our ORE scheme in Section 7.


## 1.2. Related Work

Order comparison [29] is one of the most popular operation in database-as-a-service (DaaS). In order to protect sensitive data, encryption is introduced as a prevailing consensus method. Numerous researchers have studied the problem of designing a secure and efficient encryption scheme which allows untrusted cloud servers to perform order comparison operation over ciphertexts. Due to heavy computation time and ciphertext size, fully homomorphic encryption and functional encryption are still impractical to handle order comparison [1, 2, 30]. Therefore, practical OPE schemes have proposed in the past few years [14–16, 31].Agrawal et al. [14] formalized the definition of order-preserving encryption and designed an OPE scheme. It transforms plaintexts into ciphertexts which retain the order and follow a target distribution provided by the client. In [14], the authors gave no security analysis and their scheme only applies for the static system. As an improvement, Boldyreva et al. [15] proposed the ideal security definition and further proved that an OPE scheme with immutable and stateless is impossible to achieve ideal security. The illustrated BCLO scheme in [15] is indistinguishable from a ROPF and later shows that it leaks more than half of plaintext bits [32, 33]. Moving a step forward, Dyer et al. [34] introduced an OPE scheme by using approximate integer common divisor problem. However, Dyer et al.’s scheme achieves window one-wayness security. There exist other OPE schemes [21–23, 33] with weaker security guarantee by making some impractical assumptions.Popa et al. [16] firstly introduced an ideally secure order-preserving encoding scheme named MOPE by using a balanced search tree and mutable ciphertexts. Mutable ciphertexts mean that encodings for several plaintext change with a deletion and insertion operation. The security on MOPE shows it is, in principle, possible to reveal no additional information besides orders. Kerschbaum [35] indicated each (deterministic) OPE scheme suffers a simple frequency attack from ciphertexts. For this reason, he provided a stronger security definition and indistinguishability under frequency analysis ordered chosen-plaintext attack (IND-FAOCPA). Based on random ciphertexts, the scheme [35] hides frequency information and achieves IND-FAOCPA security. Enlightened by a buffer tree [36], Roche et al. [37] constructed an order-preserving tree and further proposed a partial order-preserving encoding (POPE) scheme which supports the insert-heavy database and leaks partial orders. Unfortunately, all above schemes limit by multiple round of interactions between clients and cloud servers.Boneh et al. [18] provided a generalization definition of ORE. Different from traditional OPE, ORE reveals the order of plaintexts. They designed an ORE scheme by using multilinear maps. Because of the heavy computation burden of multilinear maps, the scheme [18] is impractical in most applications. The CLWW scheme [26] is the first practical ORE scheme by using PRFs. For each bit of data items, a keyed PRF takes this bit concatenated with all more significant bits as input. Thus, the ciphertexts include n elements which are the numerically sum of the keyed PRF and the next less significant bit. But, the CLWW scheme leaks the index of first different bit of two plaintexts. In order to balance security and efficiency, Lewi and Wu [27] introduced a generalization of the ORE scheme by using the left/right framework. The scheme of the small domain in [27] scales linearly with the size of message space and large domain reveals the first differing block. Based on bilinear map techniques, Cash et al. [19] proposed a more secure ORE scheme which leaks the equality pattern of the most significant bit.Several related works about multiclient have been introduced. Xiao et al. [33] gave a method to extend the OPE scheme to multiclient scenario which only supports the OPE system not ORE. As an improvement, two multiclient order-revealing encryption (MC-ORE) schemes [38] have been proposed by using the design principle of the CLWW scheme. Obviously, MC-ORE schemes are proven secure with different leakage functions. Li et al. [20] introduced and designed the delegatable order-revealing encryption (DORE) scheme for the multiclient system. The DORE scheme reveals the index of the first different bit between two plaintexts. Latest, some attack schemes have been introduced, such as inference attack [39], file-injection attack [28], and multicolumn attack [40]. However, most of these attack schemes require auxiliary information which limits the application in practical.


## 1.3. Organization

The rest of this paper is organized as follows. In Section2, we introduce some preliminaries. The system model and ORE definition are illustrated in Section 3. Then, in Section 4, we propose a PORE scheme by leveraging prefix encoding and Bloom filter techniques. We demonstrate its application on secure range query in Section 5. The security and efficiency analysis are illustrated in Section 6. In Section 7, we provide a performance evaluation of our scheme. Finally, the conclusions are presented in Section 8.


## 2. Preliminaries

In this section, we provide some preliminaries and definitions for the design of the ORE scheme and secure range query scheme.


### 2.1. Bloom Filter

As a space-efficient data structure, Bloom filter [41] is always used to test whether an element a is a member of a set S. The detailed description of Bloom filter is illustrated in the following.Bloom filter (BF) contains an array ofn cells which store 0 or 1 and k different hash functions H1,H2,…,Hk. The hash function Hi is defined as Hi:0,1∗⟶1,n, i=1,2,…,k. In the initial phase, we set all cells of the array to 0. When embedding an element w into the Bloom filter BF, we compute its hash functions H1w,H2w,…,Hkw and set all these chosen cells to 1. To test whether an element w belongs to a set S, we compute its hash functions and check whether the indicated cells of set S are all 1. If all these corresponding cells are 1, then w is an element of set S with allowable errors. Otherwise, w does not belong to the set S. The allowable error is called as false positive which satisfies Pf=1−e−km/nk. It reaches its minimum value 2−k when r=ln2∗n/m, where n is the size of the Bloom filter, k is the number of hash functions, and m denotes the number of elements in Bloom filter BF. An example of a Bloom filter is shown in Figure 1.Figure 1
An example of Bloom filter, wherew is added in the set andz does not belong to the set.


### 2.2. Prefix Encoding Technique

Prefix encoding technique converts the testing of whether an elementd falls into a range a,b to the testing of whether two sets have common elements [42]. The details are demonstrated as follows.Given at-bit number d=d1d2,…,dt, we evaluate its prefix family as Fd=d1d2,…,dt,d1d2,…,∗,…,d1∗⋯∗,∗∗⋯∗. It is easy to see that the size of Fd is t+1. Given a range a,b, we compute the minimum cover set of prefixes such that the union of prefixes is a,b, denoted Sa,b. The number of prefixes in Sa,b is at most 2t−2. In this condition, the testing of whether an element d belongs to a range a,b can be translated to the testing Fx∩Sa,b=∅. The element d belongs to a range a,b if Fx∩Sa,b≠∅, otherwise not. As shown in Figure 2, the prefix family of 3 with 5-bit is F3=00011,0001∗,000∗∗,00∗∗∗,0∗∗∗∗,∗∗∗∗∗ and minimum cover set of [0, 6] is S0,6=000∗∗,0010∗,00110. Owing to that F3∩S0,6=000∗∗, it is easy to draw the conclusion that 3∈0,6.Figure 2
An example of prefix encoding technology.


## 2.1. Bloom Filter

As a space-efficient data structure, Bloom filter [41] is always used to test whether an element a is a member of a set S. The detailed description of Bloom filter is illustrated in the following.Bloom filter (BF) contains an array ofn cells which store 0 or 1 and k different hash functions H1,H2,…,Hk. The hash function Hi is defined as Hi:0,1∗⟶1,n, i=1,2,…,k. In the initial phase, we set all cells of the array to 0. When embedding an element w into the Bloom filter BF, we compute its hash functions H1w,H2w,…,Hkw and set all these chosen cells to 1. To test whether an element w belongs to a set S, we compute its hash functions and check whether the indicated cells of set S are all 1. If all these corresponding cells are 1, then w is an element of set S with allowable errors. Otherwise, w does not belong to the set S. The allowable error is called as false positive which satisfies Pf=1−e−km/nk. It reaches its minimum value 2−k when r=ln2∗n/m, where n is the size of the Bloom filter, k is the number of hash functions, and m denotes the number of elements in Bloom filter BF. An example of a Bloom filter is shown in Figure 1.Figure 1
An example of Bloom filter, wherew is added in the set andz does not belong to the set.


## 2.2. Prefix Encoding Technique

Prefix encoding technique converts the testing of whether an elementd falls into a range a,b to the testing of whether two sets have common elements [42]. The details are demonstrated as follows.Given at-bit number d=d1d2,…,dt, we evaluate its prefix family as Fd=d1d2,…,dt,d1d2,…,∗,…,d1∗⋯∗,∗∗⋯∗. It is easy to see that the size of Fd is t+1. Given a range a,b, we compute the minimum cover set of prefixes such that the union of prefixes is a,b, denoted Sa,b. The number of prefixes in Sa,b is at most 2t−2. In this condition, the testing of whether an element d belongs to a range a,b can be translated to the testing Fx∩Sa,b=∅. The element d belongs to a range a,b if Fx∩Sa,b≠∅, otherwise not. As shown in Figure 2, the prefix family of 3 with 5-bit is F3=00011,0001∗,000∗∗,00∗∗∗,0∗∗∗∗,∗∗∗∗∗ and minimum cover set of [0, 6] is S0,6=000∗∗,0010∗,00110. Owing to that F3∩S0,6=000∗∗, it is easy to draw the conclusion that 3∈0,6.Figure 2
An example of prefix encoding technology.


## 3. Problem Formulation

### 3.1. System Model

As shown in Figure3, the introduced ORE scheme consists of three main parties, data owner (DO), search user (SU), and cloud service provider (CSP).Figure 3
System model of the order-revealing encryption scheme.(i)
Data owner: the data owner is the entity who owns the database, encrypts the database, and delegates the encrypted database to a powerful cloud service provider. During the encryption phase, the data owner encrypts the data items from the symmetric encryption scheme to protect its privacy and generates the encrypted search indexes to facilitate data utilization.(ii)
Search user: search users receive system parameter and secret keys from the data owner and generate search requests according to their requirements. Then, search users send search requests with the corresponding trapdoor to the cloud service provider and receive the search results on ciphertext. Finally, they decrypt the ciphertexts and obtain the results.(iii)
Cloud service provider: the cloud service provider owns the powerful storage resources and unlimited computation resources. Thus, the cloud service provider always provides the storage, computation, and query services for the data owner and search user.To protect the private sensitive information, the data owner encrypts the database, generates the indexes, and sends them to the cloud service provider. Search users compute the search trapdoor according to their request and send search trapdoor to the cloud service provider. The cloud service provider stores the encrypted database and then searches the encrypted database for the search users. In our paper, we assume the data owner and search users are fully trusted and the cloud service provider is “honest-but-curious.” It means the cloud service provider follows protocol and returns answers faithfully but intends to learn additional information about the encrypted database. The assumption is very common in other work, such as [12, 13, 43].


### 3.2. Order-Revealing Encryption Scheme

An ORE scheme is defined by four probabilistic polynomial-time (PPT) algorithms ORE.KeyGen, ORE.Enc, ORE.TokenGen, and ORE.OrderComp. These algorithms are defined as follows:(i)
ORE.KeyGen (λ)⟶SK: DO runs this algorithm to output a secret key SK. The secret key will be secretly stored by the data owner. Furthermore, the data owner will send the secret key to search users through the access control technique.(ii)
ORE.Enc(SK,d) ⟶Cd: DO runs the data encryption algorithm to encrypt data item d. The data encryption algorithm takes as input a secret key SK and a data item d and outputs the ORE ciphertext as Cd.(iii)
ORE.TokenGen (SK,a) ⟶TKa: SU runs this algorithm to generate the comparison token. It takes as input a secret key SK and a data item a and outputs the comparison token TKa.(iv)
ORE.OrderComp(Cd,TKa)⟶ans: CSP runs the order comparison algorithm to output the order relation. The algorithm takes as input the ciphertext Cd of data item d and comparison token TKa for another data item. The order comparison algorithm outputs the order relation for data item d and a. If ans=1, it means a≥d; otherwise, ans=0 means a<d.In the following, the correctness and security definitions were introduced in the ORE scheme [27].Definition 1.
(Correctness). An ORE scheme over a well-domainD is correct if for SK← ORE.KeyGen(λ) such that, for any a,b∈D, if a<b, Ca←ORE.Enc(SK,a), TKb← ORE.TokenGen(SK,b) then 1← ORE.OrderComp(Ca, TKb).
Consider an experiment defined for the ORE scheme as follows. In the experiment, we introduce the random variablewinA,k as the success of adversary A.
The IND-OCPA indistinguishability experiment ExpA,OPE is as follows:(i)
The client runs the ORE.KeyGen(λ) algorithm to produce the secret key SK and chooses a random bit b;(ii)
The client and adversaryA engage in polynomial rounds of interaction. At round i,The adversaryA chooses vi0 and vi1 in adaptive and sends both of them to the client;After receivingvi0 and vi1, the client runs the encryption algorithm ORE.Enc(SK,) and returns Cvib to the adversary A;(iii)
The adversaryA outputs a bit b′, its guess for b. The output is defined as 1 if b′=b and 0 otherwise.Definition 2.
(Security). An ORE scheme is IND-OCPA secure, if for all PPT adversariesA and sequences vi0i and vi1i with the same order relations, there is a negligible function negl⋅ satisfying(1)PrwinA,k≤12+neglk.


## 3.1. System Model

As shown in Figure3, the introduced ORE scheme consists of three main parties, data owner (DO), search user (SU), and cloud service provider (CSP).Figure 3
System model of the order-revealing encryption scheme.(i)
Data owner: the data owner is the entity who owns the database, encrypts the database, and delegates the encrypted database to a powerful cloud service provider. During the encryption phase, the data owner encrypts the data items from the symmetric encryption scheme to protect its privacy and generates the encrypted search indexes to facilitate data utilization.(ii)
Search user: search users receive system parameter and secret keys from the data owner and generate search requests according to their requirements. Then, search users send search requests with the corresponding trapdoor to the cloud service provider and receive the search results on ciphertext. Finally, they decrypt the ciphertexts and obtain the results.(iii)
Cloud service provider: the cloud service provider owns the powerful storage resources and unlimited computation resources. Thus, the cloud service provider always provides the storage, computation, and query services for the data owner and search user.To protect the private sensitive information, the data owner encrypts the database, generates the indexes, and sends them to the cloud service provider. Search users compute the search trapdoor according to their request and send search trapdoor to the cloud service provider. The cloud service provider stores the encrypted database and then searches the encrypted database for the search users. In our paper, we assume the data owner and search users are fully trusted and the cloud service provider is “honest-but-curious.” It means the cloud service provider follows protocol and returns answers faithfully but intends to learn additional information about the encrypted database. The assumption is very common in other work, such as [12, 13, 43].


## 3.2. Order-Revealing Encryption Scheme

An ORE scheme is defined by four probabilistic polynomial-time (PPT) algorithms ORE.KeyGen, ORE.Enc, ORE.TokenGen, and ORE.OrderComp. These algorithms are defined as follows:(i)
ORE.KeyGen (λ)⟶SK: DO runs this algorithm to output a secret key SK. The secret key will be secretly stored by the data owner. Furthermore, the data owner will send the secret key to search users through the access control technique.(ii)
ORE.Enc(SK,d) ⟶Cd: DO runs the data encryption algorithm to encrypt data item d. The data encryption algorithm takes as input a secret key SK and a data item d and outputs the ORE ciphertext as Cd.(iii)
ORE.TokenGen (SK,a) ⟶TKa: SU runs this algorithm to generate the comparison token. It takes as input a secret key SK and a data item a and outputs the comparison token TKa.(iv)
ORE.OrderComp(Cd,TKa)⟶ans: CSP runs the order comparison algorithm to output the order relation. The algorithm takes as input the ciphertext Cd of data item d and comparison token TKa for another data item. The order comparison algorithm outputs the order relation for data item d and a. If ans=1, it means a≥d; otherwise, ans=0 means a<d.In the following, the correctness and security definitions were introduced in the ORE scheme [27].Definition 1.
(Correctness). An ORE scheme over a well-domainD is correct if for SK← ORE.KeyGen(λ) such that, for any a,b∈D, if a<b, Ca←ORE.Enc(SK,a), TKb← ORE.TokenGen(SK,b) then 1← ORE.OrderComp(Ca, TKb).
Consider an experiment defined for the ORE scheme as follows. In the experiment, we introduce the random variablewinA,k as the success of adversary A.
The IND-OCPA indistinguishability experiment ExpA,OPE is as follows:(i)
The client runs the ORE.KeyGen(λ) algorithm to produce the secret key SK and chooses a random bit b;(ii)
The client and adversaryA engage in polynomial rounds of interaction. At round i,The adversaryA chooses vi0 and vi1 in adaptive and sends both of them to the client;After receivingvi0 and vi1, the client runs the encryption algorithm ORE.Enc(SK,) and returns Cvib to the adversary A;(iii)
The adversaryA outputs a bit b′, its guess for b. The output is defined as 1 if b′=b and 0 otherwise.Definition 2.
(Security). An ORE scheme is IND-OCPA secure, if for all PPT adversariesA and sequences vi0i and vi1i with the same order relations, there is a negligible function negl⋅ satisfying(1)PrwinA,k≤12+neglk.


## 4. The Proposed ORE Scheme

### 4.1. High Description

Before describing the details of our ORE scheme, we introduce the construction principle in brief. Different from the existing works, we partition a ciphertextCd into two parts Ed and Id, where Ed = DET.Enc(sk1,d) refers to the ciphertext which is produced by the symmetric encryption scheme DET with the strongest security (e.g., AES a DES) and Id is an index which indicates the order of plaintexts. Comparison is only proceeded between the index Id of one plaintext and the search token TKa of another data item a. Thus, CSP proceeds the query request until a search token provided by SU.In the following, we focus on the construction of indexId. The order comparison between value d and a is equal to check whether a value d falls into a range0,a. By using prefix encoding technique which is proposed in [42], we compute the data prefix Fd and range prefix S0,a. Thus, the checking of whether a value d falls into a range 0,a converts to the checking of whether two sets Fd and S0,a have common elements. The basic method is to check whether an element of one set falls into another set. Trivially, the checking is done by leveraging Bloom filter technique in [41].Since frequency information leads some simple attacks which were pointed out by Naveed et al. [39], DO should also hide the frequency (i.e., hide equality) in the ciphertext Ed and the index Id. Owing to DET is an IND-CPA secure encryption scheme, the frequency is hidden in the ciphertext Ed. To hide the frequency in index, DO randomizes a data item d as d′=d01r1 to break the equality before constructing the index.


### 4.2. The Main Construction

In this section, we introduce the ORE scheme from four processes: key generation, data encryption, token generation, and order comparison.For the sake of clarity, we assume that all data items arew-bit and greater than 0, and DET = (DET.Key, DET.Enc, DET.Dec) is an IND-CPA secure encryption scheme. The details of our ORE scheme are illustrated as follows:(i)
ORE.KeyGen(λ): on input a security parameter λ, DO computes sk1← DET.Key(λ) as a secret key. It also chooses random numbers k1,k2,…,ks as secret keys to compute hash H⋅ for a Bloom filter BF. Thus, DO has the secret key SK=sk1,sk2.(ii)
ORE.Enc(SK,d): on input a secret key SK=sk1,k1,k2,…,ks and a data item d, DO firstly leverages privacy-preserving techniques to protect the privacy of data items. To keep the functionality of order comparison, DO illustrates an index for each data item. The following processes need to be performed:(1)
Data encryption: DO encrypts data items in the database asEd = DET.Enc(sk1,d).(2)
Index construction: to facilitate look-ups, DO constructs a secure Bloom filterBFd as index structure Id for each data item d. The secure Bloom filter BF algorithm is depicted in Algorithm 1.(iii)
ORE.TokenGen(SK,a): on input a secret key SK and a data item a, SU wants to compute the comparison token for it.(1)
Data randomization: for a data itema, SU uniformly samples a w-bit random number r and computes its randomization as a′=a11r.(2)
Token computation: the search user first computes range prefixS0,a11r=Pa1,Pa2,…,Pal with l prefixes. Next, SU computes hashes for each prefix P∈S0,a11r as Hk1∥P,Hk2∥P,…,Hks∥P.The comparison tokenTka for the data item a is a hash matrix:(2)Hk1∥Pa1,Hk2∥Pa1,…,Hks∥Pa1,…,Hk1∥Pal,Hk2∥Pal,…,Hks∥Pal.(iv)
ORE.OrderComp(Cd,TKa): after receiving the ciphertext Cd and comparison token TKa, the cloud service provider checks whether BFdTKa=1. The checking BFdTKa=1 is done by checking whether there exists a row i in TKa such that all the positions Hv⋅r∥Hk1∥Pai,Hv⋅r∥Hk2∥Pai,…,Hv⋅r∥Hks∥Pai of Bloom filter BFd are 1. That is, there exists prefix P in S0,a′ such that P∈BFd′. If BFdTKa=1, set ans = 1; otherwise, ans = 0.Algorithm 1:Secure BF.
Input:hash function:H⋅secret keys:k1,k2,…,ksdata item:dOutput:–Bloom filter:BFd(1)
In order to hide the frequency, DO adds a random fractional partr for the data item d as d′=d01r, where r has the same number of bits with the data item d and d′ is a 2w+2-bit number;(2)
DO computes prefix family ofd′ as Fd′=P1,P2,…,P2w+3;(3)
fori←1 to 2w+3do(4)
To remove the correlation among different nodes, DO chooses a random numberv⋅r which has the same size with secret keys k1,k2,…,ks;(5)
forj←1 to sdo(6)
DO first computes hash valueHkj∥Pi and then sets 1 on the position Hv⋅r∥Hkj∥Pi;(7)
end for(8)
end for(9)
After inserting the prefix family, we have a secure Bloom filterBFd.The ciphertext of data itemd is Cd=Ed,Id=ORE.EncSK,d.


## 4.1. High Description

Before describing the details of our ORE scheme, we introduce the construction principle in brief. Different from the existing works, we partition a ciphertextCd into two parts Ed and Id, where Ed = DET.Enc(sk1,d) refers to the ciphertext which is produced by the symmetric encryption scheme DET with the strongest security (e.g., AES a DES) and Id is an index which indicates the order of plaintexts. Comparison is only proceeded between the index Id of one plaintext and the search token TKa of another data item a. Thus, CSP proceeds the query request until a search token provided by SU.In the following, we focus on the construction of indexId. The order comparison between value d and a is equal to check whether a value d falls into a range0,a. By using prefix encoding technique which is proposed in [42], we compute the data prefix Fd and range prefix S0,a. Thus, the checking of whether a value d falls into a range 0,a converts to the checking of whether two sets Fd and S0,a have common elements. The basic method is to check whether an element of one set falls into another set. Trivially, the checking is done by leveraging Bloom filter technique in [41].Since frequency information leads some simple attacks which were pointed out by Naveed et al. [39], DO should also hide the frequency (i.e., hide equality) in the ciphertext Ed and the index Id. Owing to DET is an IND-CPA secure encryption scheme, the frequency is hidden in the ciphertext Ed. To hide the frequency in index, DO randomizes a data item d as d′=d01r1 to break the equality before constructing the index.


## 4.2. The Main Construction

In this section, we introduce the ORE scheme from four processes: key generation, data encryption, token generation, and order comparison.For the sake of clarity, we assume that all data items arew-bit and greater than 0, and DET = (DET.Key, DET.Enc, DET.Dec) is an IND-CPA secure encryption scheme. The details of our ORE scheme are illustrated as follows:(i)
ORE.KeyGen(λ): on input a security parameter λ, DO computes sk1← DET.Key(λ) as a secret key. It also chooses random numbers k1,k2,…,ks as secret keys to compute hash H⋅ for a Bloom filter BF. Thus, DO has the secret key SK=sk1,sk2.(ii)
ORE.Enc(SK,d): on input a secret key SK=sk1,k1,k2,…,ks and a data item d, DO firstly leverages privacy-preserving techniques to protect the privacy of data items. To keep the functionality of order comparison, DO illustrates an index for each data item. The following processes need to be performed:(1)
Data encryption: DO encrypts data items in the database asEd = DET.Enc(sk1,d).(2)
Index construction: to facilitate look-ups, DO constructs a secure Bloom filterBFd as index structure Id for each data item d. The secure Bloom filter BF algorithm is depicted in Algorithm 1.(iii)
ORE.TokenGen(SK,a): on input a secret key SK and a data item a, SU wants to compute the comparison token for it.(1)
Data randomization: for a data itema, SU uniformly samples a w-bit random number r and computes its randomization as a′=a11r.(2)
Token computation: the search user first computes range prefixS0,a11r=Pa1,Pa2,…,Pal with l prefixes. Next, SU computes hashes for each prefix P∈S0,a11r as Hk1∥P,Hk2∥P,…,Hks∥P.The comparison tokenTka for the data item a is a hash matrix:(2)Hk1∥Pa1,Hk2∥Pa1,…,Hks∥Pa1,…,Hk1∥Pal,Hk2∥Pal,…,Hks∥Pal.(iv)
ORE.OrderComp(Cd,TKa): after receiving the ciphertext Cd and comparison token TKa, the cloud service provider checks whether BFdTKa=1. The checking BFdTKa=1 is done by checking whether there exists a row i in TKa such that all the positions Hv⋅r∥Hk1∥Pai,Hv⋅r∥Hk2∥Pai,…,Hv⋅r∥Hks∥Pai of Bloom filter BFd are 1. That is, there exists prefix P in S0,a′ such that P∈BFd′. If BFdTKa=1, set ans = 1; otherwise, ans = 0.Algorithm 1:Secure BF.
Input:hash function:H⋅secret keys:k1,k2,…,ksdata item:dOutput:–Bloom filter:BFd(1)
In order to hide the frequency, DO adds a random fractional partr for the data item d as d′=d01r, where r has the same number of bits with the data item d and d′ is a 2w+2-bit number;(2)
DO computes prefix family ofd′ as Fd′=P1,P2,…,P2w+3;(3)
fori←1 to 2w+3do(4)
To remove the correlation among different nodes, DO chooses a random numberv⋅r which has the same size with secret keys k1,k2,…,ks;(5)
forj←1 to sdo(6)
DO first computes hash valueHkj∥Pi and then sets 1 on the position Hv⋅r∥Hkj∥Pi;(7)
end for(8)
end for(9)
After inserting the prefix family, we have a secure Bloom filterBFd.The ciphertext of data itemd is Cd=Ed,Id=ORE.EncSK,d.


## 5. Encrypted Range Queries

In this section, we describe the application of the introduced ORE in range queries over the encrypted database. In our model, the resource-constraint data owner outsources the storage and computation tasks to the cloud service provider. Subsequently, search users submit the range query requests and obtain the query results. In outsourcing scenario, the cloud service provider needs to learn the order information for the range query. In this work, the above ORE scheme is introduced to help it in the operation of order comparison. To enhance the efficiency, the data owner stores data items in tree structure, such as B-tree. We describe the secure range query scheme with the proposed ORE scheme in the following algorithms(i)
RQ.Setup(λ): takes as input a security parameter, it outputs the secret key SK = {sk1, sk2}, where secret key SK is the same with that in the ORE scheme.(ii)
RQ.TreeBuild(D): takes as input a database D, the data owner stores the data items D in a B-tree data structure and obtains tree:(3)Γ=d1,d2,…,dn,P,whered1,d2,…,dn are data items in database D and P is a set of pointers to cover the parent-child relations of Γ tree.(iii)
RQ.TreeEnc(SK,Γ): takes as input the secret key SK and the tree Γ, the data owner runs the ORE.Enc algorithm in the ORE scheme to encrypt Γ tree as(4)Γ∗=Cd1,Cd2,…,Cdn,P,whereCdi=Edi,Idi = ORE.Enc(SKdi). Since Γ∗ tree reveals order of data items in different nodes and leaves data items in same node incomparable, the encrypted Γ∗ tree is named as PORE tree.(iv)
RQ.RangeQuery(SK, Γ∗, a,b): the range query algorithm consists of two phases. In the first phase, search users compute and send the encrypted ranges to CSP. In the second phase, CSP proceeds the search process over the encrypted tree structure Γ∗.(1)
Token generation: SU partitions the rangea,b into 0,a and 0,b two parts and uniformly samples two random numbers r1 and r2 to randomize the ranges 0,a and 0,b as 0,a00r1and0,b11r2. Next, search users proceed the token computation algorithm in ORE.TokenGen to generate search token TK0,a and TK0,b. Finally, search users send the search token TK0,a and TK0,b to CSP.(2)
After receiving search token, CSP searches the tree from root to the leaf and finds the leftmost and the rightmost leaf node intersecting with the range. The details of the search algorithm are illustrated in Algorithm2.(v)
RQ.Update(SK,Γ∗,d): to update the outsourced database, the data owner generates the ciphertext Ed, index Id, and token TKd and submits (Ed, Id, TKd) to the cloud service provider CSP. After receiving the update request, CSP updates the database by leveraging (Ed, Id, TKd). In the following, we introduce the insertion, deletion, and modification algorithms in detail:(1)
Suppose that DO wants to insert a datad into the encrypted database. DO firstly computes and sends the ciphertext Ed, index Id, and comparison token TKd to CSP. Upon receiving the insertion token, CSP takes this new data as a split point and inserts it into the parent node v¯. For a data item (Edi, Idi) in the leaf node v, CSP checks whether data item di satisfying BFdiTK0,d=1. CSP stores (Edi, Idi) into the left node v1 if BFdiTK0,d=1. Otherwise, CSP stores it into the right node v2.(2)
Suppose that DO wants to delete a datad from the encrypted database. The deletion algorithm finds data items in the range d,d, which is similar to the range query algorithm and deletes these data items.(3)
Suppose that DO wants to modify a data itemd to d¯ in the encrypted database. The modification is converted to deletion and insertion operation. Thus, it can be done using above two steps.(vi)
RQ.Dec(SK, Res∗): on input the secret key SK and encrypted results Res∗, DO firstly runs DET.Dec to decrypt Res∗ and then removes random numbers to obtain final results.Algorithm 2: Tree search.
(i)
Input:(ii)
encrypted PORE tree:Γ∗(iii)
search token:TKa,b = (TK0,aTK0,b)(iv)
Output:(v)
encrypted results:Res∗(1)
CSP proceeds the search algorithm twice, once forTK0,a to find the leftmost leaf node and once for TK0,b to find the rightmost leaf node;(2)
forv←roottoleafnodedo(3)
CSP checks whetherBFdTK0,a=1 by checking whether there exists a row i in matrix TK0,a such that the positions Hv⋅r∥Hk1∥Pai,Hv⋅r∥Hk2∥Pai,…,Hv⋅r∥Hks∥Pai of BFd are equal to 1;(4)
Afterwards, CSP finds the largest valued satisfying BFdTK0,a=1 and updates its corresponding child as the new value for v;(5)
end for(6)
CSP obtains the leftmost leaf node and the rightmost leaf node;(7)
Finally, CSP returns resultsRes∗ which include data items in leaf nodes between the two leaf nodes, in the leftmost leaf node satisfying BFdTK0,a=0 and in the rightmost leaf node satisfying BFdTK0,a=1.


## 6. Analysis

In this section, we demonstrate the security analysis and efficiency analysis.


### 6.1. Security Analysis

Theorem 1.
The proposed ORE scheme over a well-domainD is correct.Proof.
Suppose thatr1andr2 are two w-bit random numbers, Cd is the ciphertext for data itemd, and TKa is the comparison token for data item a. We prove the correctness through d≤a if and only if ans=1 without considering the false positive of Bloom filter.
First, we prove ifd≤a, then ans=1. If d≤a, we have the relationd′<a′. Owing to the fact that a data item d falls into a range a,b if and only if Fd∩Sa,b≠ϕ, we can compute and draw the conclusion that Fd′∩S0,a′≠ϕ. That means, BFdTKa=1, namely, ans=1.
Moreover, if we do not take false positive of Bloom filter into consideration, we can prove the correctness. That is, ifans=1, then BFdTKa=1. Since BFdTKa=1, we have the conclusion that there exists a rowi in TKa such that all the corresponding positions of Bloom filter BFd are equal to 1. Namely, Fd′∩S0,a′≠ϕ that means d′≤a′. Because d′ = d01r1 anda′=a11r2, we have the conclusion that d≤a (if d>a, then d′>a′).Theorem 2.
The proposed secure range query scheme over a well-domainD is correct.Proof.
Suppose that a data itemd∈D, a range a,b, and their randomization d′=d01r1, a′=a00r2andb′=b11r3, where r1,r2,andr3 are three w-bit random numbers. We proof the correctness through d∈a,b if and only if d∈Res.
First, we prove ifd∈a,b, then d∈Res. If d∈a,b, we have the relation a′<d′<b′. Owing to the fact that for a data item d and rangea,b,x∈a,b if and only ifFd∩Sa,b≠ϕ, we can compute BFd′M0,a′=0,BFd′M0,b′=1. That means, Cd∈Res∗, namely, d∈Res.
Moreover, if we do not take false positive of Bloom filter into consideration, we can prove the correctness. That is, ifd∈Res, then d∈a,b. If d∈Decsk,Res∗, we can draw the conclusion that(5)Cd∈Res∗,BFd′M0,a′=0,BFd′M0,b′=1.
That is,d′∉0,a′andd′∈0,b′, namely,(6)d01r1∉0,a00r2,d01r1∈0,b11r3.
After derandomization, we can draw the conclusion that(7)d∉0,a,d∈0,b.
That meansd∈a,b.Theorem 3.
The proposed ORE scheme is IND-OCPA secure in the random oracle model.Proof.
For the convenience of understanding, we first introduce the concept of computationally indistinguishable. LetX=Xkk and Y=Ykk be ensembles of distributions. X and Y are said to be computationally indistinguishable (written X≈CY), if for all PPT adversariesA,(8)PrXk=1−PrYk=1=neglk.
Next, we will prove the theorem in the following hybrid games:(i)
Hybrid 1: The IND-OCPA game for an adversaryA and the proposed scheme. Let H1Aλ be the random variable indicating the output of A in the IND-OCPA game, namely, A’s guess bit.(ii)
Hybrid 2: The IND-OCPA game for an adversaryA, where the proposed scheme is revised to instead the DET with a random oracle O (a random oracle refers to an oracle which outputs a random value r when given a value v for the first time, and the same value r returns when v is given again.). Let H2Aλ be the random variable indicating the output of A in the IND-OCPA game, namely, A’s guess bit.(iii)
Hybrid 3: The IND-OCPA game for adversaryA, where the scheme in Hybrid 2 is revised to instead hash function with a random oracle O. Let H3Aλ be the random variable indicating the output of A, namely, A’s guess bit.
Because DET is a pseudo-random function, it is obvious thatH1Aλ≈CH2Aλ. We give a proof by contradiction for this conclusion. If these two hybrids are distinguishable, then we construct a simulator D1 which distinguishes pseudo-random numbers from random numbers.
The distinguisherD1rk:(1)
AdversaryA is given a security parameter and outputs ({vk0} and {vk1}) with the same order relation;(2)
A uniform bitb←0,1 is chosen, and then a ciphertext {Ckb} = {rk} is computed and given to the adversary A;(3)
The adversaryA outputs a bit b′, its guess for b. The distinguisher D1 outputs 1 if b′=b (meaning pseudo-random sequence) and 0 (meaning random sequence) otherwise.
If adversaryA can distinguish these two hybrids, namely,(9)PrADET.Encsk1,vkb=1−PrArk=1>neglk,
then we conclude that(10)PrD1=1=12PrD1=1|b=0+12PrD1=1|b=1=12+12⋅PrADET.Encsk1,vkb=1−PrArk=1≥12+12⋅neglk.
Thus, we can draw the conclusion thatH1Aλ≈CH2Aλ. Since H· is a pseudo-random function, it draws the same conclusion thatH2Aλ≈CH3Aλ. Following, we prove the probability adversary A guesses correctly in Hybrid 3 is 1/2. That is, the winning advantage of A can be at most 1/2+neglk. The data owner stores Cd=Ed,Id in the cloud service provider for a data item d. Because Ed is replaced with a random oracle, the adversary A cannot distinguish the ciphertexts of vi0 and vi1, namely, Evi0≈CEvi1.
Moreover, recall that every valued is assigned a different random number v.r, and random oracle O uses v.r to compute hash functions for the secure Bloom filter BFd. Thus, given two different Bloom filters BFi and BFj, it is infeasible for any PPT adversary A to distinguish whether a same string or two different strings are mapped to them. From this, it is easy to draw the conclusion that(11)BFvi0≈CBFvi1.Namely,Ivi0≈CIvi1.
As a result, the adversaryA cannot distinguish with nonnegligible probability. That is,(12)PrwinA,kin Hybrid3≤12+neglk.
We complete the proof of Theorem3.


### 6.2. Efficiency Analysis

For the convenience of discussion, some marks are introduced in this section. We denote byE/D an encryption/decryption algorithm of the DET scheme with IND-CPA secure, F is a PRF, H is a hash function, r is the number of hashes in a Bloom filter, w is the bits of our data item, n is the size of the database, N is the size of message space, and t is the size of results. We omit other operations such as comparison of plaintexts and uniformly random permutation in Lewi-Wu ORE.We now describe the efficiency analysis among MOPE [16], Lewi-Wu ORE [27], and the proposed range query scheme with PORE tree, shorted for the PORE scheme. The security in Table 1 demonstrates that all schemes achieve IND-OCPA security which reveals nothing besides the order relation. Furthermore, the PORE scheme hides data frequency and data items in leaf nodes of our PORE scheme which remain incomparable. Stored information in MOPE [16] only consists of the ciphertexts, that is, produced by an IND-CPA secure DET scheme. Therefore, the order comparison is achieved by the interaction with a DO/SU. In this condition, there is about Ologn-round communication between DO/SU and CSP during the range query and update operation. Ciphertexts in Lewi-Wu ORE [27] consist of the left ciphertexts and the right ciphertexts. It is possible to proceed the comparison algorithm with the left of one ciphertext and the right of another ciphertext. To enhance the storage efficiency, CSP only stores the left ciphertexts (about logn bits long) in the sorted order instead of the complete ciphertexts (about nlog3+logn bits long). When proceeding a range query or an update operation, DO generates the right ciphertexts and sends them to the CSP.Table 1
Efficiency comparison among MOPE, Lewi-Wu ORE, and our proposed PORE.
EntityMOPELewi-Wu OREPORESecurityIND-OCPAIND-OCPAIND-OCPAInteractionlogn00Frequency hidingNoNoYesEncryptionDOnEnFnE+nrw+1HRange querySU2logn⋅D2NF+2NH4rw−1HCSP—2logn⋅H4rlognw−1HInsertionDOE+logn⋅DN+1F+NHE+2rw−1HCSP—logn⋅H2rlognw−1HDeletionDOlogn⋅DNF+NH4rw−1HCSP—logn⋅H4rlognw−1HDecryptionSUtDtFtDThe basic idea of our PORE is inspired by Lewi-Wu ORE. We split stored information into a ciphertext produced by DET and an indexId. The index Id is a Bloom filter storingFd with the size of w+1. Compared with the MOPE and Lewi-Wu ORE scheme, the cost of encryption in our PORE scheme is a little higher. While encryption is one-time in the initialization phase, the cost is acceptable. In range query and update phases, CSP obtains order comparison by communicating with the DO and SU in MOPE. SU decrypts ciphertexts and returns the order information. The cost in Lewi-Wu ORE [27] is linear with the message space for the DO/SU and logarithm with the database for CSP. MOPE and Lewi-Wu ORE have a better efficiency for CSP in both phases. Both schemes do not use the tremendous compute power of CSP violating the definition of cloud computing. Finally, we observe from decryption cost that all these schemes have a high efficiency.


## 6.1. Security Analysis

Theorem 1.
The proposed ORE scheme over a well-domainD is correct.Proof.
Suppose thatr1andr2 are two w-bit random numbers, Cd is the ciphertext for data itemd, and TKa is the comparison token for data item a. We prove the correctness through d≤a if and only if ans=1 without considering the false positive of Bloom filter.
First, we prove ifd≤a, then ans=1. If d≤a, we have the relationd′<a′. Owing to the fact that a data item d falls into a range a,b if and only if Fd∩Sa,b≠ϕ, we can compute and draw the conclusion that Fd′∩S0,a′≠ϕ. That means, BFdTKa=1, namely, ans=1.
Moreover, if we do not take false positive of Bloom filter into consideration, we can prove the correctness. That is, ifans=1, then BFdTKa=1. Since BFdTKa=1, we have the conclusion that there exists a rowi in TKa such that all the corresponding positions of Bloom filter BFd are equal to 1. Namely, Fd′∩S0,a′≠ϕ that means d′≤a′. Because d′ = d01r1 anda′=a11r2, we have the conclusion that d≤a (if d>a, then d′>a′).Theorem 2.
The proposed secure range query scheme over a well-domainD is correct.Proof.
Suppose that a data itemd∈D, a range a,b, and their randomization d′=d01r1, a′=a00r2andb′=b11r3, where r1,r2,andr3 are three w-bit random numbers. We proof the correctness through d∈a,b if and only if d∈Res.
First, we prove ifd∈a,b, then d∈Res. If d∈a,b, we have the relation a′<d′<b′. Owing to the fact that for a data item d and rangea,b,x∈a,b if and only ifFd∩Sa,b≠ϕ, we can compute BFd′M0,a′=0,BFd′M0,b′=1. That means, Cd∈Res∗, namely, d∈Res.
Moreover, if we do not take false positive of Bloom filter into consideration, we can prove the correctness. That is, ifd∈Res, then d∈a,b. If d∈Decsk,Res∗, we can draw the conclusion that(5)Cd∈Res∗,BFd′M0,a′=0,BFd′M0,b′=1.
That is,d′∉0,a′andd′∈0,b′, namely,(6)d01r1∉0,a00r2,d01r1∈0,b11r3.
After derandomization, we can draw the conclusion that(7)d∉0,a,d∈0,b.
That meansd∈a,b.Theorem 3.
The proposed ORE scheme is IND-OCPA secure in the random oracle model.Proof.
For the convenience of understanding, we first introduce the concept of computationally indistinguishable. LetX=Xkk and Y=Ykk be ensembles of distributions. X and Y are said to be computationally indistinguishable (written X≈CY), if for all PPT adversariesA,(8)PrXk=1−PrYk=1=neglk.
Next, we will prove the theorem in the following hybrid games:(i)
Hybrid 1: The IND-OCPA game for an adversaryA and the proposed scheme. Let H1Aλ be the random variable indicating the output of A in the IND-OCPA game, namely, A’s guess bit.(ii)
Hybrid 2: The IND-OCPA game for an adversaryA, where the proposed scheme is revised to instead the DET with a random oracle O (a random oracle refers to an oracle which outputs a random value r when given a value v for the first time, and the same value r returns when v is given again.). Let H2Aλ be the random variable indicating the output of A in the IND-OCPA game, namely, A’s guess bit.(iii)
Hybrid 3: The IND-OCPA game for adversaryA, where the scheme in Hybrid 2 is revised to instead hash function with a random oracle O. Let H3Aλ be the random variable indicating the output of A, namely, A’s guess bit.
Because DET is a pseudo-random function, it is obvious thatH1Aλ≈CH2Aλ. We give a proof by contradiction for this conclusion. If these two hybrids are distinguishable, then we construct a simulator D1 which distinguishes pseudo-random numbers from random numbers.
The distinguisherD1rk:(1)
AdversaryA is given a security parameter and outputs ({vk0} and {vk1}) with the same order relation;(2)
A uniform bitb←0,1 is chosen, and then a ciphertext {Ckb} = {rk} is computed and given to the adversary A;(3)
The adversaryA outputs a bit b′, its guess for b. The distinguisher D1 outputs 1 if b′=b (meaning pseudo-random sequence) and 0 (meaning random sequence) otherwise.
If adversaryA can distinguish these two hybrids, namely,(9)PrADET.Encsk1,vkb=1−PrArk=1>neglk,
then we conclude that(10)PrD1=1=12PrD1=1|b=0+12PrD1=1|b=1=12+12⋅PrADET.Encsk1,vkb=1−PrArk=1≥12+12⋅neglk.
Thus, we can draw the conclusion thatH1Aλ≈CH2Aλ. Since H· is a pseudo-random function, it draws the same conclusion thatH2Aλ≈CH3Aλ. Following, we prove the probability adversary A guesses correctly in Hybrid 3 is 1/2. That is, the winning advantage of A can be at most 1/2+neglk. The data owner stores Cd=Ed,Id in the cloud service provider for a data item d. Because Ed is replaced with a random oracle, the adversary A cannot distinguish the ciphertexts of vi0 and vi1, namely, Evi0≈CEvi1.
Moreover, recall that every valued is assigned a different random number v.r, and random oracle O uses v.r to compute hash functions for the secure Bloom filter BFd. Thus, given two different Bloom filters BFi and BFj, it is infeasible for any PPT adversary A to distinguish whether a same string or two different strings are mapped to them. From this, it is easy to draw the conclusion that(11)BFvi0≈CBFvi1.Namely,Ivi0≈CIvi1.
As a result, the adversaryA cannot distinguish with nonnegligible probability. That is,(12)PrwinA,kin Hybrid3≤12+neglk.
We complete the proof of Theorem3.


## 6.2. Efficiency Analysis

For the convenience of discussion, some marks are introduced in this section. We denote byE/D an encryption/decryption algorithm of the DET scheme with IND-CPA secure, F is a PRF, H is a hash function, r is the number of hashes in a Bloom filter, w is the bits of our data item, n is the size of the database, N is the size of message space, and t is the size of results. We omit other operations such as comparison of plaintexts and uniformly random permutation in Lewi-Wu ORE.We now describe the efficiency analysis among MOPE [16], Lewi-Wu ORE [27], and the proposed range query scheme with PORE tree, shorted for the PORE scheme. The security in Table 1 demonstrates that all schemes achieve IND-OCPA security which reveals nothing besides the order relation. Furthermore, the PORE scheme hides data frequency and data items in leaf nodes of our PORE scheme which remain incomparable. Stored information in MOPE [16] only consists of the ciphertexts, that is, produced by an IND-CPA secure DET scheme. Therefore, the order comparison is achieved by the interaction with a DO/SU. In this condition, there is about Ologn-round communication between DO/SU and CSP during the range query and update operation. Ciphertexts in Lewi-Wu ORE [27] consist of the left ciphertexts and the right ciphertexts. It is possible to proceed the comparison algorithm with the left of one ciphertext and the right of another ciphertext. To enhance the storage efficiency, CSP only stores the left ciphertexts (about logn bits long) in the sorted order instead of the complete ciphertexts (about nlog3+logn bits long). When proceeding a range query or an update operation, DO generates the right ciphertexts and sends them to the CSP.Table 1
Efficiency comparison among MOPE, Lewi-Wu ORE, and our proposed PORE.
EntityMOPELewi-Wu OREPORESecurityIND-OCPAIND-OCPAIND-OCPAInteractionlogn00Frequency hidingNoNoYesEncryptionDOnEnFnE+nrw+1HRange querySU2logn⋅D2NF+2NH4rw−1HCSP—2logn⋅H4rlognw−1HInsertionDOE+logn⋅DN+1F+NHE+2rw−1HCSP—logn⋅H2rlognw−1HDeletionDOlogn⋅DNF+NH4rw−1HCSP—logn⋅H4rlognw−1HDecryptionSUtDtFtDThe basic idea of our PORE is inspired by Lewi-Wu ORE. We split stored information into a ciphertext produced by DET and an indexId. The index Id is a Bloom filter storingFd with the size of w+1. Compared with the MOPE and Lewi-Wu ORE scheme, the cost of encryption in our PORE scheme is a little higher. While encryption is one-time in the initialization phase, the cost is acceptable. In range query and update phases, CSP obtains order comparison by communicating with the DO and SU in MOPE. SU decrypts ciphertexts and returns the order information. The cost in Lewi-Wu ORE [27] is linear with the message space for the DO/SU and logarithm with the database for CSP. MOPE and Lewi-Wu ORE have a better efficiency for CSP in both phases. Both schemes do not use the tremendous compute power of CSP violating the definition of cloud computing. Finally, we observe from decryption cost that all these schemes have a high efficiency.


## 7. Performance Evaluation

In this section, we introduce a formal experimental simulation among MOPE [16], Lewi-Wu ORE [27], and the proposed PORE scheme in order to test the practical utility. Specifically, the code is run with Python3 language on a machine with an Intel Xeon (R) CPU i7-8565U processor running at 16 GHz and 1 T memory. We instantiate the hash function with SHA-256 in the Lewi-Wu ORE scheme. The symmetric cipher used is AES-ECB-128 as provided by the PyCrypto library, and the scalable Bloom filer is provided in pybloom live library. Furthermore, we set error rate of Bloom filter as 0.001 and storage limitation L=4 of B-tree to store ciphertexts.


### 7.1. Database Size

In the following experiment, we use the Gowalla database which lists 6,442,890 check-in locations collected from 196,591 users. We sample 1,000,000 data items of 48 bit in the database to test the performance of the MOPE and PORE scheme. Figure4 demonstrates that Lewi-Wu ORE [27] is only suitable in the small domain. In this condition, we cut 12 bit from data items in the Gowalla database to simulate the performance of search and update.Figure 4
The average encryption time cost of the Lewi-Wu ORE scheme.


### 7.2. Network

For these experiments, we simulate all the data owner, search users, and cloud service provider on the same machine. Therefore, we test performance by measuring the theoretical communication cost instead of the realistic network with latency and bandwidth restrictions. In the theoretical experimental simulation, we assume that the network is slower than 5 ms of latency and 20 Mbps bandwidth.Figures5(a) and 5(b) show the time cost and storage cost on tree construction of MOPE, Lewi-Wu ORE, and our PORE scheme. We can easily see that time cost of MOPE is similar to that of Lewi-Wu ORE since the AES-ECB-128 is used to encrypt data items in MOPE and to instantiate the PRF in Lewi-Wu ORE. Furthermore, the time cost from 80s at 100,000 data items and 1082s at 1,000,000 data items of our PORE scheme is greater than that of the MOPE and Lewi-Wu ORE scheme. Meanwhile, the storage cost from 10.5 M to 105 M of the PORE scheme is a little greater than that of the MOPE and Lewi-Wu ORE scheme, from 8.2 M to 82M and 7.5 M to 75 M, respectively. The time cost and storage cost are acceptable of our PORE scheme because of one-time on tree construction.Figure 5
The time cost (a) and storage cost (b) of tree construction. Lower is better. The bit length of data item is 48 bit for MOPE and PORE and 12 bit for Lewi-Wu ORE.
(a)(b)In our main experiments, we test the performance of range query and update operation (insertion and deletion) with 1,000 operations in MOPE and our PORE scheme and that with 100 operations in the Lewi-Wu ORE scheme. The time cost of range query is shown in Figure6. It demonstrates that our PORE scheme is far less than MOPE-latency and the Lewi-Wu ORE scheme. Furthermore, our scheme achieves about 18 ms per-range query on the database with million data items vs. about 50 ms per-operation for MOPE-latency with communication latency.Figure 6
The time cost of range query. Lower is better. The number of range query is 1000 for MOPE, MOPE-latency, and PORE and 100 for Lewi-Wu ORE.Figures7(a) and 7(b) show the time cost on insertion and deletion operation. As these figures present, the cost is dominated by communication on range query and insertion and deletion of the MOPE-latency scheme with 5 ms latency. The runtime is linear with the round of communication. Moreover, the time cost of MOPE-latency and Lewi-Wu ORE is about 5x greater than our scheme on insertion and 2x on deletion operation. We can see that our scheme is well-suited for range query and update operation.Figure 7
The time cost of (a) insertion and (b) deletion. Lower is better. The number of insertion and deletion is 1000 for MOPE, MOPE-latency, and PORE and 100 for Lewi-Wu ORE.
(a)(b)


## 7.1. Database Size

In the following experiment, we use the Gowalla database which lists 6,442,890 check-in locations collected from 196,591 users. We sample 1,000,000 data items of 48 bit in the database to test the performance of the MOPE and PORE scheme. Figure4 demonstrates that Lewi-Wu ORE [27] is only suitable in the small domain. In this condition, we cut 12 bit from data items in the Gowalla database to simulate the performance of search and update.Figure 4
The average encryption time cost of the Lewi-Wu ORE scheme.


## 7.2. Network

For these experiments, we simulate all the data owner, search users, and cloud service provider on the same machine. Therefore, we test performance by measuring the theoretical communication cost instead of the realistic network with latency and bandwidth restrictions. In the theoretical experimental simulation, we assume that the network is slower than 5 ms of latency and 20 Mbps bandwidth.Figures5(a) and 5(b) show the time cost and storage cost on tree construction of MOPE, Lewi-Wu ORE, and our PORE scheme. We can easily see that time cost of MOPE is similar to that of Lewi-Wu ORE since the AES-ECB-128 is used to encrypt data items in MOPE and to instantiate the PRF in Lewi-Wu ORE. Furthermore, the time cost from 80s at 100,000 data items and 1082s at 1,000,000 data items of our PORE scheme is greater than that of the MOPE and Lewi-Wu ORE scheme. Meanwhile, the storage cost from 10.5 M to 105 M of the PORE scheme is a little greater than that of the MOPE and Lewi-Wu ORE scheme, from 8.2 M to 82M and 7.5 M to 75 M, respectively. The time cost and storage cost are acceptable of our PORE scheme because of one-time on tree construction.Figure 5
The time cost (a) and storage cost (b) of tree construction. Lower is better. The bit length of data item is 48 bit for MOPE and PORE and 12 bit for Lewi-Wu ORE.
(a)(b)In our main experiments, we test the performance of range query and update operation (insertion and deletion) with 1,000 operations in MOPE and our PORE scheme and that with 100 operations in the Lewi-Wu ORE scheme. The time cost of range query is shown in Figure6. It demonstrates that our PORE scheme is far less than MOPE-latency and the Lewi-Wu ORE scheme. Furthermore, our scheme achieves about 18 ms per-range query on the database with million data items vs. about 50 ms per-operation for MOPE-latency with communication latency.Figure 6
The time cost of range query. Lower is better. The number of range query is 1000 for MOPE, MOPE-latency, and PORE and 100 for Lewi-Wu ORE.Figures7(a) and 7(b) show the time cost on insertion and deletion operation. As these figures present, the cost is dominated by communication on range query and insertion and deletion of the MOPE-latency scheme with 5 ms latency. The runtime is linear with the round of communication. Moreover, the time cost of MOPE-latency and Lewi-Wu ORE is about 5x greater than our scheme on insertion and 2x on deletion operation. We can see that our scheme is well-suited for range query and update operation.Figure 7
The time cost of (a) insertion and (b) deletion. Lower is better. The number of insertion and deletion is 1000 for MOPE, MOPE-latency, and PORE and 100 for Lewi-Wu ORE.
(a)(b)


## 8. Conclusions

In this paper, we introduce a noninteractive order-revealing encryption scheme with comparison token to execute privacy-preserving order comparison in cloud computing. The introduced ORE scheme requires that the cloud service provider could not perform order comparison until a search token provided. The security analysis shows that our ORE scheme achieves IND-OCPA security. Furthermore, we design a secure range query over the encrypted database through designing PORE tree structure from the proposed ORE scheme. The designed PORE tree reveals partial order information of plaintexts and leaves results incomparable even after query execution. Finally, the experimental result shows the high efficiency of our PORE scheme based on the designing of the ORE scheme.



---

*Source: 8837904-2020-12-24.xml*