# A Quantum-Based Database Query Scheme for Privacy Preservation in Cloud Environment

Authors: Wenjie Liu; Peipei Gao; Zhihao Liu; Hanwu Chen; Maojun Zhang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Cloud computing is a powerful and popular information technology paradigm that enables data service outsourcing and provides higher-level services with minimal management effort. However, it is still a key challenge to protect data privacy when a user accesses the sensitive cloud data. Privacy-preserving database query allows the user to retrieve a data item from the cloud database without revealing the information of the queried data item, meanwhile limiting user’s ability to access other ones. In this study, in order to achieve the privacy preservation and reduce the communication complexity, a quantum-based database query scheme for privacy preservation in cloud environment is developed. Specifically, all the data items of the database are firstly encrypted by different keys for protecting server’s privacy, and in order to guarantee the clients’ privacy, the server is required to transmit all these encrypted data items to the client with the oblivious transfer strategy. Besides, two oracle operations, a modified Grover iteration, and a special offset encryption mechanism are combined together to ensure that the client can correctly query the desirable data item. Finally, performance evaluation is conducted to validate the correctness, privacy, and efficiency of our proposed scheme.


---

## Body

## 1. Introduction

Cloud computing is a powerful computing paradigm that enables ubiquitous access to shared infrastructure resources and higher-level services. It has shown the remarkable advantage in load balancing, data access control, and resources sharing, for database management [1]. Benefiting from the cloud paradigm, an increasing number of individuals and groups choose to put their massive data (including private part) into the cloud.In recent years, database outsourcing has become an important component of cloud computing [2], where data owners outsource data management to a service provider (i.e., cloud database), and this mode is also called Database-as-a-Service (DaaS) [3]. Cloud database provides users with capabilities to store and process their data in the cloud, which has the advantages of scalability and high availability that users can access data anytime, anywhere and anyway. However, all the data of data owner is stored in the cloud environment, and some sensitive data (e.g., health records, financial transactions, and personal information) is at risk of being compromised. So, security and privacy have become the major challenges which inhibit the cloud computing wide acceptance in practice [4].The privacy preservation is the main concern of cloud application, such as service recommendation [5–7], service quality prediction [8, 9], database query [10–16], etc. As an important research branch, the privacy-preserving database query (PPDQ) aims to protect database security and clients’ privacy, while ensuring the correctness of database query. To be specific, any user can query data items from the cloud database without revealing its information, but his/her access to other data items is not permitted. There are a variety of techniques or methods for guaranteeing the privacy preservation of database query, such as homomorphic encryption (HE) [10, 11], attribute-based encryption (ABE) [12–14], searchable encryption (SE) [15, 16], etc. Searchable encryption is a cryptographic system which offers secure search functions over encrypted data, which is considered to be a more effective technique to solve the problem of PPDQ. In 2000, Song et al. [15] proposed the first searchable encryption scheme based on symmetric key cryptography (SKC). Since then, other various SE schemes have been continuously proposed, such as public key cryptography- (PKC-) based searchable encryption [17], secure ranked search over encrypted cloud data [18], and so on.As we all know, the security of classic cryptography protocols, including most private query schemes (also named privacy-preserving database query schemes), is based on mathematical complexity, and its security is based on the fact that computing power is limited. However, with the prevalence of new distributed computing models (especially cloud computing), a normal user is given the super computing power far beyond a single computer. Therefore, these cryptography protocols based on computational complexity are facing serious challenges.On the other hand, quantum computing demonstrates the superior parallel computing power that the classical paradigm cannot match. For instance, Shor’s algorithm [19] solves the problem of integer factorization in polynomial time, and Grover’s algorithm [20] has a quadratic speedup to the problem of conducting a search through some unstructured database. Therefore, most classic cryptography protocols, including PPDQ schemes, are very vulnerable to the powerful quantum computer. Fortunately, quantum mechanics also provides a security mechanism against quantum attacks, and it holds the potential unconditional security based on some physical properties, such as noncloning theorem, uncertainty principle, quantum entanglement, etc. With the application of quantum mechanics in the field of information processing, some research findings have been proposed, including quantum key distribution [21, 22], quantum secret sharing [23, 24], quantum key agreement [25, 26], quantum direct communication [27, 28], quantum steganography [29], quantum teleportation and remote state preparation [30–32], quantum sealed-bid auction [33, 34], delegating quantum computation [35], and quantum machine learning [36, 37].With the above observations, the security of classic database query schemes is facing the dual challenge of cloud computing and quantum computing, while quantum mechanics has been proven to be an effective method for solving such problem. In this study, in order to implement the privacy-preserving database query in cloud environment, we utilize some physical properties of quantum mechanics to design a quantum-based database query scheme for privacy preservation (QBDQ) in cloud environment and conduct its performance evaluation to show our scheme is feasible, secure, and efficient. To be specific, our main contributions include the three following aspects.(1)
We present a systematic framework for privacy preservation cloud database query scheme in the cloud environment.(2)
A feasible QBDQ is designed through oblivious transfer, the offset encryption mechanism, oracle operation, and the modified Grover iteration to achieve the privacy preservation for the cloud database query and reduce its communication complexity.(3)
The performance evaluation is conducted to verify the performance of our proposed QBDQ scheme, such as correctness, security, and efficiency.The rest of this paper is organized as follows. In Section2, we introduce the basic knowledge of quantum computing, while the framework of the privacy-preserving database query in cloud environment is presented. In Section 3, the problem of privacy-preserving database query in cloud environment is defined, and then the proposed QBDQ is elaborated step by step. Section 4 conducts the performance evaluation from the aspects of correctness, security, and efficiency. After that, Section 5 summarizes the related work on cloud database queries, SE, and quantum private queries. Finally, the conclusion of the paper and the prospection for future work are presented in Section 6.


## 2. Preliminaries

In this section, the basic knowledge of quantum computing is introduced firstly. Then, we introduced the principle of oblivious transfer (OT). And finally, a cloud computing framework for privacy preservation is designed.


### 2.1. Quantum Computing

#### 2.1.1. Quantum Bit

The classic bit is the smallest unit in the classic computer, and its value is either 0 or 1. Unlike classical computers, the smallest unit of quantum computers is qubit (quantum bit), which is the quantum analog of the classic bit. A qubit is a unit vector in a two-dimensional complex Hilbert space, and its Dirac notation is represented as follows:(1)φ=α0+β1,where α and β are the probability amplitudes of the state φ and α2 + β2=1. Since the vectors 0 and 1 are basis states and can be represented as (2)0=101=01,the qubit φ can be expressed in vector form φ=αβ. In addition, the single qubit can be extended to multiple qubits; for example, an n-qubit system can exist in any superposed basis states(3)φ=α00+α11+⋯α2n-12n-1.Here, ∑i=02n-1αi2=1. Quantum states {0〉,1〉,…,2n-1〉} form a complete orthonormal basis in Hilbert space.


#### 2.1.2. Unitary Operator

In a closed quantum system, the evolution of the system is characterized by a series of unitary operators; that is,(4)φ′=Uφ,where UU†=U†U=I and U† is the transpose conjugate of U. Each unitary operator corresponds to a quantum gate. Similar to a logic gate in classical calculations, the quantum gate can be represented in matrix form, and the quantum gate over a qubit is represented by a 2×2 unitary matrix. For instance, Pauli-X, Pauli-Z, and the Hadamard gateH are important quantum operators over one qubit described in (5)X=0110Z=100-1H=12111-1.


#### 2.1.3. Quantum Measurement

The quantum state is in a superposition state, and it must be measured to collapse to a basis state to obtain a result. Assuming that the quantum state is|φ=1/N∑i=0N-1αi|i before measurement operator, quantum measurements are described by a collection {Mi} of measurement operators which satisfy the completeness equation(6)∑i=0N-1Mi†Mi=I,where i indicates the possible outcome of the measurement. The quantum state is measured by the measurement basis |i, then the probability that result i occurs is given by(7)pi=φMi†Miφ,and the postmeasurement state is (8)MiφφMi†Miφ.


### 2.2. Oblivious Transfer

In cryptography, an oblivious transfer (OT) strategy is a type of strategy in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred. The first form of oblivious transfer was introduced by Rabin [38]. In this form, the sender sends a message to the receiver with probability 1/2, while the sender remains oblivious as to whether or not the receiver received the message. OT is a basic strategy in the field of cryptography and has a wide range of applications. In general, the OT strategy involves two parties, the sender and the receiver, and satisfies the following characteristics:(i)
Whether the queried data can be obtained is entirely dependent on probability, rather than sender or receiver. That is, neither the sender nor receiver can affect the execution of the strategy.(ii)
After the execution of the strategy, the sender could not know whether the receiver got the data he wanted to query.k-out-of-n (OTnk) (k<n) is the general form of all OT strategies. That is, the sender has n secrets, and the receiver can only get k secrets. The OTnk strategy consists of two parties, the sender with n secret data (d0,d1,…,dn-1), and the receiver with k indices (i1,i2,…,ik). The strategy meets the following requirements:(i)
Correctness. After executing the strategy, the receiver can obtain all of the di correctly.(ii)
Receiver’s Security. When the receiver queries the data from the sender, the database cannot know the receiver’s query items.(iii)
Sender's Security. The receiver cannot get more data items from the sender except queried data items.


### 2.3. The Framework of Privacy-Preserving Database Query in Cloud Environment

We first consider the framework model of privacy-preserving cloud database query system, which consists of two main entities (clients and cloud server) as illustrated in Figure1.Figure 1
The framework of privacy-preserving database query in cloud environment.As shown in Figure1, there aren clients and a cloud database server, and every client sends a query request to the cloud server and gets the query result from the cloud server finally. In this framework, we suppose all the clients and server are semihonest: they are curious about cheating the privacy of other’s, but honest to carry out the operations in the scheme. Here, two kinds of entity can be defined as follows.Client is the entity that wants to query items from the database in the cloud server and can be the connected users or the individual user with mobile constrained devices such as smartphones, PDA, TPM chip, etc.Cloud server is the entity which provides data services and computational resources to the clients dynamically.In this paper, we take three parties as an example, i.e., the client Alice, client Bob, and the cloud server Charlie, to demonstrate the process of the privacy-preserving database query using quantum mechanics.


## 2.1. Quantum Computing

### 2.1.1. Quantum Bit

The classic bit is the smallest unit in the classic computer, and its value is either 0 or 1. Unlike classical computers, the smallest unit of quantum computers is qubit (quantum bit), which is the quantum analog of the classic bit. A qubit is a unit vector in a two-dimensional complex Hilbert space, and its Dirac notation is represented as follows:(1)φ=α0+β1,where α and β are the probability amplitudes of the state φ and α2 + β2=1. Since the vectors 0 and 1 are basis states and can be represented as (2)0=101=01,the qubit φ can be expressed in vector form φ=αβ. In addition, the single qubit can be extended to multiple qubits; for example, an n-qubit system can exist in any superposed basis states(3)φ=α00+α11+⋯α2n-12n-1.Here, ∑i=02n-1αi2=1. Quantum states {0〉,1〉,…,2n-1〉} form a complete orthonormal basis in Hilbert space.


### 2.1.2. Unitary Operator

In a closed quantum system, the evolution of the system is characterized by a series of unitary operators; that is,(4)φ′=Uφ,where UU†=U†U=I and U† is the transpose conjugate of U. Each unitary operator corresponds to a quantum gate. Similar to a logic gate in classical calculations, the quantum gate can be represented in matrix form, and the quantum gate over a qubit is represented by a 2×2 unitary matrix. For instance, Pauli-X, Pauli-Z, and the Hadamard gateH are important quantum operators over one qubit described in (5)X=0110Z=100-1H=12111-1.


### 2.1.3. Quantum Measurement

The quantum state is in a superposition state, and it must be measured to collapse to a basis state to obtain a result. Assuming that the quantum state is|φ=1/N∑i=0N-1αi|i before measurement operator, quantum measurements are described by a collection {Mi} of measurement operators which satisfy the completeness equation(6)∑i=0N-1Mi†Mi=I,where i indicates the possible outcome of the measurement. The quantum state is measured by the measurement basis |i, then the probability that result i occurs is given by(7)pi=φMi†Miφ,and the postmeasurement state is (8)MiφφMi†Miφ.


## 2.1.1. Quantum Bit

The classic bit is the smallest unit in the classic computer, and its value is either 0 or 1. Unlike classical computers, the smallest unit of quantum computers is qubit (quantum bit), which is the quantum analog of the classic bit. A qubit is a unit vector in a two-dimensional complex Hilbert space, and its Dirac notation is represented as follows:(1)φ=α0+β1,where α and β are the probability amplitudes of the state φ and α2 + β2=1. Since the vectors 0 and 1 are basis states and can be represented as (2)0=101=01,the qubit φ can be expressed in vector form φ=αβ. In addition, the single qubit can be extended to multiple qubits; for example, an n-qubit system can exist in any superposed basis states(3)φ=α00+α11+⋯α2n-12n-1.Here, ∑i=02n-1αi2=1. Quantum states {0〉,1〉,…,2n-1〉} form a complete orthonormal basis in Hilbert space.


## 2.1.2. Unitary Operator

In a closed quantum system, the evolution of the system is characterized by a series of unitary operators; that is,(4)φ′=Uφ,where UU†=U†U=I and U† is the transpose conjugate of U. Each unitary operator corresponds to a quantum gate. Similar to a logic gate in classical calculations, the quantum gate can be represented in matrix form, and the quantum gate over a qubit is represented by a 2×2 unitary matrix. For instance, Pauli-X, Pauli-Z, and the Hadamard gateH are important quantum operators over one qubit described in (5)X=0110Z=100-1H=12111-1.


## 2.1.3. Quantum Measurement

The quantum state is in a superposition state, and it must be measured to collapse to a basis state to obtain a result. Assuming that the quantum state is|φ=1/N∑i=0N-1αi|i before measurement operator, quantum measurements are described by a collection {Mi} of measurement operators which satisfy the completeness equation(6)∑i=0N-1Mi†Mi=I,where i indicates the possible outcome of the measurement. The quantum state is measured by the measurement basis |i, then the probability that result i occurs is given by(7)pi=φMi†Miφ,and the postmeasurement state is (8)MiφφMi†Miφ.


## 2.2. Oblivious Transfer

In cryptography, an oblivious transfer (OT) strategy is a type of strategy in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred. The first form of oblivious transfer was introduced by Rabin [38]. In this form, the sender sends a message to the receiver with probability 1/2, while the sender remains oblivious as to whether or not the receiver received the message. OT is a basic strategy in the field of cryptography and has a wide range of applications. In general, the OT strategy involves two parties, the sender and the receiver, and satisfies the following characteristics:(i)
Whether the queried data can be obtained is entirely dependent on probability, rather than sender or receiver. That is, neither the sender nor receiver can affect the execution of the strategy.(ii)
After the execution of the strategy, the sender could not know whether the receiver got the data he wanted to query.k-out-of-n (OTnk) (k<n) is the general form of all OT strategies. That is, the sender has n secrets, and the receiver can only get k secrets. The OTnk strategy consists of two parties, the sender with n secret data (d0,d1,…,dn-1), and the receiver with k indices (i1,i2,…,ik). The strategy meets the following requirements:(i)
Correctness. After executing the strategy, the receiver can obtain all of the di correctly.(ii)
Receiver’s Security. When the receiver queries the data from the sender, the database cannot know the receiver’s query items.(iii)
Sender's Security. The receiver cannot get more data items from the sender except queried data items.


## 2.3. The Framework of Privacy-Preserving Database Query in Cloud Environment

We first consider the framework model of privacy-preserving cloud database query system, which consists of two main entities (clients and cloud server) as illustrated in Figure1.Figure 1
The framework of privacy-preserving database query in cloud environment.As shown in Figure1, there aren clients and a cloud database server, and every client sends a query request to the cloud server and gets the query result from the cloud server finally. In this framework, we suppose all the clients and server are semihonest: they are curious about cheating the privacy of other’s, but honest to carry out the operations in the scheme. Here, two kinds of entity can be defined as follows.Client is the entity that wants to query items from the database in the cloud server and can be the connected users or the individual user with mobile constrained devices such as smartphones, PDA, TPM chip, etc.Cloud server is the entity which provides data services and computational resources to the clients dynamically.In this paper, we take three parties as an example, i.e., the client Alice, client Bob, and the cloud server Charlie, to demonstrate the process of the privacy-preserving database query using quantum mechanics.


## 3. A Quantum-Based Database Query Scheme for Privacy Preservation in Cloud Environment

In this section, we first define the privacy-preserving database query problem and quantum-based privacy-preserving database query problem in cloud environment. To address this issue, a QBDQ scheme is proposed in detail. Before we introduce the relevant content, the key notations and descriptions used in this section are listed in Table1.Table 1
Key notations and descriptions involved in proposed QBDQ scheme.
Notation Description N The number of items in cloud server’s database D The cloud server’s database,D={D0,D1,…,DN-1} D i Thei-th data in D n The number of index qubits used to encode index of data itemsn=log⁡N m The number of qubits used to encode dataDi p The index of client Alice’s query data D p The data item Alice wants to query fromD q The index of client Bob’s query data D q The data item Bob wants to query fromD ∆ s A The offset value of Alice ∆ s B The offset value of Bob K The encryption key sequence belongs to Charlie,K={K0,K1,…,KN-1}. O K The oracle operation to encode Charlie’s key sequenceK O D A The oracle operation to encode Alice’s query resultDp O D B The oracle operation to encode Bob’s query resultDq O s The oracle operation which conditionally changes the sign in the amplitudes of the query itemDp (Dq) O p The oracle operation which perform a conditional phase shift of -1 with every computational bass state except|0


### 3.1. Some Definitions

In order to clearly illustrate our scheme, we first define the problem to be solved.Definition 1 (database query problem for privacy preservation in cloud environment).
In the cloud environment, the cloud server has a collection of sensitive dataD={D0,D1,…,DN-1}, and each client wants to query a data item Di(0≤i≤N-1) from the cloud server without revealing which item is queried. During the retrieving process, the client cannot gain any other data item except Di.Definition 2 (database query scheme for privacy preservation in cloud environment).
Each client inputs the index of query itemi0≤i≤N-1, and cloud server inputs sensitive dataset D={D0,D1,…,DN-1}. After executing this scheme, the client outputs the queried data item Di. In addition, the scheme should satisfy the following:(i)
Correctness. The client successfully obtains the correct data item he(she) wants to query (i.e., Di).(ii)
Clients’ Privacy. During the retrieving process, the cloud server cannot get any private information about the query index of the client.(iii)
Cloud Server’s Privacy. Clients cannot get any other data items from the cloud server except Di.


### 3.2. A Quantum-Based Database Query Scheme for Privacy Preservation in Cloud Environment

For the sake of simplicity, we take three parties (one cloud server Charlie, and two clients Alice, Bob) as an example to describe our scheme. Suppose Charile has a private databaseD withN items {D0,D1,…,DN-1} and an encryption key sequence K={K0,K1,…,KN-1}, and Alice and Bob want to, respectively, query an item, thep-th itemDp, and theq-th item Dq (0≤p,q≤N-1), from server. The scheme consists of five steps as follows (also shown in Figure 2).Figure 2
The five-step procedures of the QBDQ scheme among two clients and cloud server. The thick (thin) line represents quantum (classic) channel.Step 1.
Charlie prepares an (n+m)-qubit state ϕK〉=1/N∑i=0N-1|i⊗|0⊗m, where n=log⁡N, m=log⁡(max⁡ki∣0≤i≤N-1+1). And then he applies an oracle operation OK (its schematic circuit is sketched in Figure 3) on ϕK〉 referring to the sequence K={K0,K1,…,KN-1}. Here, OK is defined as follows:(9)OK:1N∑i=0N-1i⊗0⊗m→1N∑i=0N-1i⊗Ki,where |i denotes the index of the data item and |Ki is the encryption key originally assigned to encrypt thei-th data item. After the above operation, we can get the state, namely, |ϕ′〉=1/N∑i=0N-1|i⊗|Ki, and then Charlie sends it to Alice with oblivious transfer strategy. Similar to Alice, Charlie also prepares another state ψ′〉=1/N∑i=0N-1|i⊗|Ki in the same way and sends it to Bob.Figure 3
Schematic circuit of the oracle operationOK.Step 2.
After receivingϕ′〉 from Charlie, Alice takes {0〉,1〉,…,N-1〉} as the computational basis and performs projective measurement on the index qubits of ϕ′〉. Suppose the measurement result is λA(λA∈{0,1,…,N-1}); the remaining m qubits will collapse into |KλA, which means Alice can obtain KλA (i.e., one of the encryption keys) through projective measurement. Since Alice’s retrieving index is p, she computes the offset ∆sA=(λA-p) and sends it to Charlie. As same as Alice, Bob also performs the same operations and announces the offset ∆sB=(λB-q) to Charlie, where λB is the measurement result, and q represents the index of the data item Bob wants to query.Step 3.
Having received the offsets∆sA and ∆sB, Charlie updates every encryption key as(10)KiA=Ki+ΔsAmodNKiB=Ki+ΔsBmodNand obtains the new key sequence KA and KB, (11)KA=KiA∣0≤i≤N-1KB=KiB∣0≤i≤N-1.Then, Charlie encrypts every data items respectively with its new corresponding keys KiA and KiB as follows:(12)DiA=Di⊕KiA,0≤i≤N-1DiB=Di⊕KiB,0≤i≤N-1.
After that, Charlie prepares two states|ϕD〉=1/N∑i=0N-1|i⊗|0⊗m, |ψD〉=1/N∑i=0N-1|i⊗|0⊗m and applies the oracle operation ODA, ODB as (13)ODA:1N∑i=0N-1i0⊗m→1N∑i=0N-1iDiAODB:1N∑i=0N-1i0⊗m→1N∑i=0N-1iDiBand gets the final states |ϕ′′〉=1/N∑i=0N-1|i|DiA, |ψ′′〉=1/N∑i=0N-1|i|DiB. Finally, Charlie sends ϕ′′〉, ψ′′〉 to Alice and Bob, respectively, with oblivious transfer strategy.Step 4.
After receivingϕ′′〉 from Charlie, Alice performs the modified Grover iteration on it to obtain the target state p〉DpA〉. Figure 4 describes the detailed process of modified Grover iteration, which consists of at most π/42n+m times application of a quantum subroutine, called the G operator. The whole process of G operator (also shown in Figure 5) can be subdivided into four steps as follows.
Step 4.1. Alice applies the oracle operation Os on ϕ′′〉, which conditionally changes the sign of the amplitudes of the query item(14)Os:1N∑i=0N-1iDiA→1N∑i=0N-1-1fiiDiAHere, we call the resultant state Osϕ′′〉, i.e., Osϕ′′〉=1/N∑i=0N-1(-1)f(i)i〉DiA〉, and fi is the judgment function defined by(15)fi=1,ifiisthequeryaddressi.e.,i=p0,elsei.e.,i≠p
Step 4.2. The Hadamard transformation H⊗(n+m) is applied on Osϕ′′〉,(16)1N∑i=0N-1-1fiiDiA→H⊗n+m1N∑i=0N-1-1fiiDiA.
Step 4.3. Alice applies conditionally phase transfer Op on the state H⊗n+mOsϕ′′〉,(17)Op:H⊗n+m1N∑i=0N-1-1fiiDiA→--1σi,DiH⊗n+m1N∑i=0N-1-1fiiDiA,where the function σi,Di is defined as follows: (18)σi,Di=1,i=0,Di=0,0,else.
Step 4.4. The Hadamard transformation H⊗(n+m) is applied again on OpH⊗n+mOsϕ′′〉 and obtains the state(19)ξ=H⊗n+mOPH⊗n+mOs1N∑i=0N-1iDiAAlice applies the above Grover iteration π/42n+m times and finally obtains the target state p〉DpA〉.
Similar to Alice, Bob also applies the modified Grover iteration on the received stateψ′′〉=1/N∑i=0N-1i〉DiA〉 and obtains the target query state q〉DqB〉.Figure 4
Schematic circuit of the modified Grover iteration applied on stateϕ′′〉, where G is the quantum subroutine illustrated in Figure 5.Figure 5
Schematic circuit of theG operator.Step 5.
Alice and Bob measure the lastm-qubit of state p〉DpA〉, q〉DqB〉 and extract the classic information of query result DpA, DqB, respectively.In addition, in order to check eavesdropping in the quantum channel, we can use decoy-photon technology. That is, the sender randomly inserts several decoy photons into the qubit sequence, where every decoy photon is prepared randomly with eitherZ-basis 0,1 orX-basis 1/2|0+1,1/2|0-1, and transmits them to the receiver. After confirming that the receiver has received the transmitted sequence, the sender announces the positions of the decoy photons and the corresponding measurement basis. The receiver measures the decoy photons according to the sender’s announcements and tells the sender his (her) measurement results. Then, the sender compares the measurement results from the receiver with the initial states of the decoy photons in the transmitted sequence and calculates the error rate. If the error rate is higher than the threshold determined by the channel noise, they cancel this scheme and restart; else they continue the next step.It is worth mentioning that we adopted the OT strategy and offset encryption mechanism in our scheme. In Step3, the OT strategy is utilized to transfer Charlie's data to Alice and Bob. As we know, the transmitted state |ψ is a superposition state which encapsulates all the encrypted data items {Di∣0≤i≤N-1}. So, the process of Charlie sending |ϕ′, |ψ′ to Alice and Bob can be viewed as the oblivious transfer mechanism. The use of OT strategy ensures that information about Charlie cannot be leaked. In addition, our scheme also applied the offset encryption mechanism. The offsets ∆sA, ∆sB can be computed by using the index of the query data items and the keys determined by clients’ measurement. Charlie updates the encryption keys according to these offsets and then encrypts data with these updated keys, respectively. The combination of OT strategy and offset mechanism allows Alice and Bob obtain the correct data they want to query, while Charlie cannot get their queried data, which guaranteed the privacy of client. At the same time, data encryption makes the data items into ciphertext, and neither the eavesdropper nor the clients can directly obtain the data item, thus ensuring the data security of the cloud server.


## 3.1. Some Definitions

In order to clearly illustrate our scheme, we first define the problem to be solved.Definition 1 (database query problem for privacy preservation in cloud environment).
In the cloud environment, the cloud server has a collection of sensitive dataD={D0,D1,…,DN-1}, and each client wants to query a data item Di(0≤i≤N-1) from the cloud server without revealing which item is queried. During the retrieving process, the client cannot gain any other data item except Di.Definition 2 (database query scheme for privacy preservation in cloud environment).
Each client inputs the index of query itemi0≤i≤N-1, and cloud server inputs sensitive dataset D={D0,D1,…,DN-1}. After executing this scheme, the client outputs the queried data item Di. In addition, the scheme should satisfy the following:(i)
Correctness. The client successfully obtains the correct data item he(she) wants to query (i.e., Di).(ii)
Clients’ Privacy. During the retrieving process, the cloud server cannot get any private information about the query index of the client.(iii)
Cloud Server’s Privacy. Clients cannot get any other data items from the cloud server except Di.


## 3.2. A Quantum-Based Database Query Scheme for Privacy Preservation in Cloud Environment

For the sake of simplicity, we take three parties (one cloud server Charlie, and two clients Alice, Bob) as an example to describe our scheme. Suppose Charile has a private databaseD withN items {D0,D1,…,DN-1} and an encryption key sequence K={K0,K1,…,KN-1}, and Alice and Bob want to, respectively, query an item, thep-th itemDp, and theq-th item Dq (0≤p,q≤N-1), from server. The scheme consists of five steps as follows (also shown in Figure 2).Figure 2
The five-step procedures of the QBDQ scheme among two clients and cloud server. The thick (thin) line represents quantum (classic) channel.Step 1.
Charlie prepares an (n+m)-qubit state ϕK〉=1/N∑i=0N-1|i⊗|0⊗m, where n=log⁡N, m=log⁡(max⁡ki∣0≤i≤N-1+1). And then he applies an oracle operation OK (its schematic circuit is sketched in Figure 3) on ϕK〉 referring to the sequence K={K0,K1,…,KN-1}. Here, OK is defined as follows:(9)OK:1N∑i=0N-1i⊗0⊗m→1N∑i=0N-1i⊗Ki,where |i denotes the index of the data item and |Ki is the encryption key originally assigned to encrypt thei-th data item. After the above operation, we can get the state, namely, |ϕ′〉=1/N∑i=0N-1|i⊗|Ki, and then Charlie sends it to Alice with oblivious transfer strategy. Similar to Alice, Charlie also prepares another state ψ′〉=1/N∑i=0N-1|i⊗|Ki in the same way and sends it to Bob.Figure 3
Schematic circuit of the oracle operationOK.Step 2.
After receivingϕ′〉 from Charlie, Alice takes {0〉,1〉,…,N-1〉} as the computational basis and performs projective measurement on the index qubits of ϕ′〉. Suppose the measurement result is λA(λA∈{0,1,…,N-1}); the remaining m qubits will collapse into |KλA, which means Alice can obtain KλA (i.e., one of the encryption keys) through projective measurement. Since Alice’s retrieving index is p, she computes the offset ∆sA=(λA-p) and sends it to Charlie. As same as Alice, Bob also performs the same operations and announces the offset ∆sB=(λB-q) to Charlie, where λB is the measurement result, and q represents the index of the data item Bob wants to query.Step 3.
Having received the offsets∆sA and ∆sB, Charlie updates every encryption key as(10)KiA=Ki+ΔsAmodNKiB=Ki+ΔsBmodNand obtains the new key sequence KA and KB, (11)KA=KiA∣0≤i≤N-1KB=KiB∣0≤i≤N-1.Then, Charlie encrypts every data items respectively with its new corresponding keys KiA and KiB as follows:(12)DiA=Di⊕KiA,0≤i≤N-1DiB=Di⊕KiB,0≤i≤N-1.
After that, Charlie prepares two states|ϕD〉=1/N∑i=0N-1|i⊗|0⊗m, |ψD〉=1/N∑i=0N-1|i⊗|0⊗m and applies the oracle operation ODA, ODB as (13)ODA:1N∑i=0N-1i0⊗m→1N∑i=0N-1iDiAODB:1N∑i=0N-1i0⊗m→1N∑i=0N-1iDiBand gets the final states |ϕ′′〉=1/N∑i=0N-1|i|DiA, |ψ′′〉=1/N∑i=0N-1|i|DiB. Finally, Charlie sends ϕ′′〉, ψ′′〉 to Alice and Bob, respectively, with oblivious transfer strategy.Step 4.
After receivingϕ′′〉 from Charlie, Alice performs the modified Grover iteration on it to obtain the target state p〉DpA〉. Figure 4 describes the detailed process of modified Grover iteration, which consists of at most π/42n+m times application of a quantum subroutine, called the G operator. The whole process of G operator (also shown in Figure 5) can be subdivided into four steps as follows.
Step 4.1. Alice applies the oracle operation Os on ϕ′′〉, which conditionally changes the sign of the amplitudes of the query item(14)Os:1N∑i=0N-1iDiA→1N∑i=0N-1-1fiiDiAHere, we call the resultant state Osϕ′′〉, i.e., Osϕ′′〉=1/N∑i=0N-1(-1)f(i)i〉DiA〉, and fi is the judgment function defined by(15)fi=1,ifiisthequeryaddressi.e.,i=p0,elsei.e.,i≠p
Step 4.2. The Hadamard transformation H⊗(n+m) is applied on Osϕ′′〉,(16)1N∑i=0N-1-1fiiDiA→H⊗n+m1N∑i=0N-1-1fiiDiA.
Step 4.3. Alice applies conditionally phase transfer Op on the state H⊗n+mOsϕ′′〉,(17)Op:H⊗n+m1N∑i=0N-1-1fiiDiA→--1σi,DiH⊗n+m1N∑i=0N-1-1fiiDiA,where the function σi,Di is defined as follows: (18)σi,Di=1,i=0,Di=0,0,else.
Step 4.4. The Hadamard transformation H⊗(n+m) is applied again on OpH⊗n+mOsϕ′′〉 and obtains the state(19)ξ=H⊗n+mOPH⊗n+mOs1N∑i=0N-1iDiAAlice applies the above Grover iteration π/42n+m times and finally obtains the target state p〉DpA〉.
Similar to Alice, Bob also applies the modified Grover iteration on the received stateψ′′〉=1/N∑i=0N-1i〉DiA〉 and obtains the target query state q〉DqB〉.Figure 4
Schematic circuit of the modified Grover iteration applied on stateϕ′′〉, where G is the quantum subroutine illustrated in Figure 5.Figure 5
Schematic circuit of theG operator.Step 5.
Alice and Bob measure the lastm-qubit of state p〉DpA〉, q〉DqB〉 and extract the classic information of query result DpA, DqB, respectively.In addition, in order to check eavesdropping in the quantum channel, we can use decoy-photon technology. That is, the sender randomly inserts several decoy photons into the qubit sequence, where every decoy photon is prepared randomly with eitherZ-basis 0,1 orX-basis 1/2|0+1,1/2|0-1, and transmits them to the receiver. After confirming that the receiver has received the transmitted sequence, the sender announces the positions of the decoy photons and the corresponding measurement basis. The receiver measures the decoy photons according to the sender’s announcements and tells the sender his (her) measurement results. Then, the sender compares the measurement results from the receiver with the initial states of the decoy photons in the transmitted sequence and calculates the error rate. If the error rate is higher than the threshold determined by the channel noise, they cancel this scheme and restart; else they continue the next step.It is worth mentioning that we adopted the OT strategy and offset encryption mechanism in our scheme. In Step3, the OT strategy is utilized to transfer Charlie's data to Alice and Bob. As we know, the transmitted state |ψ is a superposition state which encapsulates all the encrypted data items {Di∣0≤i≤N-1}. So, the process of Charlie sending |ϕ′, |ψ′ to Alice and Bob can be viewed as the oblivious transfer mechanism. The use of OT strategy ensures that information about Charlie cannot be leaked. In addition, our scheme also applied the offset encryption mechanism. The offsets ∆sA, ∆sB can be computed by using the index of the query data items and the keys determined by clients’ measurement. Charlie updates the encryption keys according to these offsets and then encrypts data with these updated keys, respectively. The combination of OT strategy and offset mechanism allows Alice and Bob obtain the correct data they want to query, while Charlie cannot get their queried data, which guaranteed the privacy of client. At the same time, data encryption makes the data items into ciphertext, and neither the eavesdropper nor the clients can directly obtain the data item, thus ensuring the data security of the cloud server.


## 4. Performance Evaluation

Our proposed QBDQ scheme in cloud environment tends to ensure the correctness of query result, protect the privacy of clients and servers in cloud, and also improve the efficiency during querying the cloud database. Therefore, we take three parties (i.e., clients Alice and Bob; cloud server Charlie) as an example and estimate the overall performance of the proposed scheme in terms of correctness analysis, security analysis, and the efficiency analysis.


### 4.1. Correctness Analysis

Now, we analyze the correctness of the proposed scheme. Without loss of generality, suppose that the server Charlie has a database of 16 itemsD={5,9,6,12,2,11,11,6,5,10,7,15,6,11,6,9}, and he holds the corresponding encryption key sequence K={14,8,3,4,7,1,11,6,15,2,12,13,0,5,9,10}. Since N=16, the max value in K is 15, n=log⁡N=log⁡16=4, m=log⁡(15+1)=4. Here, we take Alice as an example to analyze the procedures of our QBDQ scheme as follows (suppose Alice wants to query the 9th item of the database).In Step1, Charlie prepares an initial state ϕK〉=1/4∑i=015i〉⊗0000〉 and performs an oracle operation OK on it to encode his encryption keys,(20)ϕ′=140K0+1K1+2K2+3K3+4K4+5K5+6K6+7K7+8K8+9K9+10K10+11K11+12K12+13K13+14K10+15K11=14014+18+23+34+47+51+611+76+815+92+1012+1113+120+135+149+1510Then, he sends the resultant state ϕ′〉 to Alice. In Step 2, Alice performs projective measurement on the first four qubits (i.e., index qubits) of ϕ′〉 in the computational basis {|0000〉,|0001〉,…,|1111〉}. Suppose the random measurement result is 12〉 (i.e., λA = 12), then the remaining qubits (i.e., the key qubits) collapse to the state |KλA〉=|0000〉, which means KλA=0000. But the data Alice wants to query is the ninth data D8, so she computes the difference between λA and the desirable query index q, ∆s=(λA-q)=4, and sends ∆s to Charlie. After receiving ∆s, Charlie updates the key sequence K through the formulation KiA=K(i+∆s)modN, then KiA={7,1,11,6,15,2,12,13,0,5,9,10,14,8,3,4}. He uses KiA to encrypt every data items: DiA=Di⊕KiA, that is, {2,8,13,10,13,9,7,11,5,15,14,5,8,3,5,13}. Then, in Step 3, Charlie prepares another state ϕD〉=1/4∑i=015i〉⊗0000〉 and applies the oracle operation ODA to embed the encrypted data items DiA,(21)ϕ′′=140D0+1D1+2D2+3D3+4D4+5D5+6D6+7D7+8D8+9D9+10D10+11D11+12D12+13D13+14D14+15D15=1402+18+213+310+413+59+67+711+85+915+1014+115+128+133+145+1513.Then, he sends the state ϕ′′〉 to Alice.Further, Alice performs modified Grover iteration onϕ′′〉 up to R=π/42n+m=π/428=13 times (actually, the number of iterations is 6), then she can obtain the encrypted query item p〉DpA〉=8〉5〉 with a high possibility, and measures it to get DpA=5. Alice uses the obtained key K8A=0 to decrypt the ninth item(22)D8=D8A⊕K8A=0101⊕0000=0101.Therefore, regardless of what measurement result Alice has obtained, she can finally obtain the query data correctly.Figure6 shows the entire execution process of Alice querying Charlie’s database in a simplified way. At the same time, it also sketched the execution of the other user Bob (assuming it queries the fifth data).Figure 6
The schematic graph of the execution process of Alice and Bob in our QBDQ scheme, assuring they query the9-th and5-th items, respectively.


### 4.2. Security Analysis

#### 4.2.1. Privacy Analysis

Cloud Server's Privacy. Suppose the client Alice is dishonest, and she wants to obtain more information about Charlie’s database. In Step 1 of our scheme, the server Charlie sends the quantum state ϕ′〉=1/N∑i=0N-1i〉Ki〉 to client Alice through oblivious transfer strategy. Since all the information about the key sequence K is encoded in the state ϕ′〉, so Alice cannot extract the key form ϕ′〉 directly. Here we suppose the whole system of quantum state ϕ′〉 consisted of two subsystems, i.e., then-qubit quantum subsystemC(index qubits i〉) and them-qubit subsystemD(key qubits Ki〉). If Alice makes a projective measurement on the received state ϕ′〉, she will get the resultant state i〉Ki〉 for any i with the probability of 1/N. The whole system can be represented by the quantum ensemble ε=pi,ρ(i), here pi=1/N, (23)ρi=iKiKii.Here we get the upper limit of information that Alice can get from Charlie’s is determined by the Holevo bound [38],(24)HA:B≤Sρ-1N∑i=0N-1SρiHere Sρ denotes Von Neumann entropy of quantum state ρ,H(B:A) means the information Alice can get about Charlie’s key information (including the address i and according keys Ki), and we have(25)Sρ=S1N∑i=0N-1iKiKii=n+m.and Sρi=SiKiKi|i|=0; therefore,(26)HA:B≤n+m.Then, Alice can only get n-bit of address information (i.e., i) and the corresponding m-bit key (i.e., Ki) by measuring ρ. In addition, she will certainly lose the change to get her key Ki. This means Alice cannot extract more than one key from Charlie.Besides, in Step3, Charlie uses the offset key KiA=Ki+△s to encrypt the data items, and send its encoded state |ϕ′′〉=1/Δs∑i=0N-1i〉DiA〉 to Alice with oblivious transfer strategy. Alice’s privacy of query indexiis protected by the oblivious transfer strategy. For example, the transmitted state |ϕ′′〉 Alice received is a superposition state, i.e., |ϕ′′〉=1/N(0〉D0〉+1〉D1〉+⋯+N-1〉DN-1〉), which encapsulates all the query data DpA∣0≤p≤N-1 including the desirable one DpA. Alice obtains the query item DpA through the Grover iteration and the previously obtained key KλA. Suppose Bob is also dishonest, he has the same situation with Alice.Client’s Privacy. If Charlie is dishonest, he may try to obtain Alice’s private query indexp during the communication process. However, Alice only sends one classic message ∆s=λA-p to cloud server Charlie in Step 2, and Charlie does not know the encryption key which chosen by Alice, thus he cannot obtain any useful information about the data Alice wants to search. As same as Alice, Bob only sends a classic offset message ∆s=λB-p to Charlie, which prevents Charlie from obtaining his information.


#### 4.2.2. Channel Security Analysis

The security of the quantum channel is guaranteed by the decoy-photon checking technology. The process of eavesdropping detected done by the two neighbor participants in our scheme is essentially equivalent to that in the BB84 scheme [36], which has been proved to be unconditionally secure. To be specific, the decoy qubits, which are randomly inserted into target qubits, are generated by randomly chosen from 0〉,1〉,+〉,-〉. After one participant sends the mixed decoy qubits and encrypted target qubits to quantum center, he will ask quantum center to measure them with the same bases these qubits were produced. For any outside eavesdropper, the bases used by participants are all random; the eavesdropper cannot produce the same qubits like decoy qubits before quantum center receives the qubits. Just like the situation in the BB84 scheme, if any outside eavesdropper exists in the process of our scheme, the eavesdropping actions will be found by the two participants.The outside eavesdropper cannot get the shared key because eavesdropper cannot distinguish target qubits form decoy qubits, and he can only choose one set of orthogonal basis to measure it, so the eavesdropper will certainly change the states of the qubit, and then he will be discovered. We assume that eavesdropper will do intercept-resend attack. Eavesdropper applies operationUE and auxiliary system |E which satisfies the following conditions:(27)UE0E=a0E00+b1E01,(28)UE1E=c0E01+d1E11.Here, a2+b2=1 and c2+d2=1. If the eavesdropper wants to extract the encode information precisely, then UE must satisfy(29)UE+E=12a0E00+b1E01+c0E10+d1E11=12+aE00+bE01+cE10+dE11,(30)UE-E=12a0E00+b1E01-c0E10-d1E11=12-aE00-bE01-cE10+dE11,(31)UE+yE=12a0E00+b1E01+ic0E10+id1E11=12+yaE00-ibE01+icE10-dE11,(32)UE-yE=12a0E00+b1E01-ic0E10-id1E11=12+yaE00+ibE01-icE10+dE11.From (29)–(32) we can obtain that(33)aE00-bE01+cE10-dE11=0,(34)aE00+bE01-cE10-dE11=0,(35)aE00+ibE01+icE10-dE11=0,(36)aE00-ibE01-icE10-dE11=0,we can get that a=d=1, b=c=0, and E00〉=E11〉, then we get(37)UE0E=0E00,(38)UE1E=1E11,and we can summarize that eavesdropper would not be found only when decoy qubits and target qubits are |0,|1, which is impossible. So there is no way for the eavesdropper to know the secret key.


### 4.3. Efficiency Analysis

As we know, quantum-based schemes have greater information capacity than classic ones. In order to evaluate the efficiency of our QDBQ scheme more objectively, we choose some of the most representative quantum schemes as comparison objects, for example, Jakobi et al.’s quantum private query (QPQ) scheme (J11 for short) [39], Gao et al.’s QPQ scheme (G12) [40], and Rao et al.’s QPQ) scheme (R13) [41].To evaluate the efficiency of quantum communication schemes, there are mainly two indicators: the communication complexity (i.e., the number of transmitted qubits), and the consumption of exchanged classic messages (i.e., the number of exchanged classic bits).


#### 4.3.1. Communication Complexity

The communication complexity, i.e., the number of quantum bits (qubits) transmitted in the communication process, is one of the key indicators of the efficiency for communication scheme. In J11 and G12 schemes, the cloud server (Charlie) sendsk×N qubits to the client (Alice), where k is the number of divided substrings. These k substrings are added bitwise in order to reduce Alice’s information on the key to roughly one bit (i.e., n-=N(1/4)k≈1), so k=log⁡N. In summary, N×log⁡N qubits are transmitted in J11 and J12 schemes, and its communication complexity is O(Nlog⁡N). But in the R13 scheme, the number of qubits that need to be exchanged is reduced to O(N), so the communication complexity is O(N).In our QBDQ scheme, Charlie firstly transmits a (log⁡N+m)-qubit state ϕ′ (ψ′) for sending the encryption keys in Step 1, and the (log⁡N+m)-qubit state ϕ′′ (ψ′′) containing every encrypted data Di(0≤i≤N-1) is transmitted to Alice(Bob) in Step 3. Considering that each data item the cloud server holds is an only one-bit message in J11, G12 and R13 schemes, here we let m=1. Therefore, the transmitted qubits are 2(log⁡N+1), so its communication complexity is O(log⁡N).To be more intuitive, we calculate the numbers of transmitted qubits in different database capacities for the J11, G12, R13, and our QBDQ schemes (see Table2) and show the comparison results among them in Figure 7. As shown in this figure, J11 and G12 schemes have the same qubits consumption, R13 scheme reduces the consumption, and our QBDQ scheme has the lowest qubits consumption. That is, our scheme has the lowest communication complexity among them.Table 2
Numbers of transmitted qubits in different database capacities for J11, G12, R13, and our QBDQ schemes.
Database size Transmitted messages(qubit) Database size Transmitted messages(qubit) J11/ G12 R13 QBDQ J11/G12 R13 QBDQ 8 24 8 3 208 1664 208 8 16 64 16 4 216 1728 216 8 24 120 24 5 224 1792 224 8 32 160 32 5 232 1856 232 8 40 240 40 6 240 1920 240 8 48 288 48 6 248 1984 248 8 56 336 56 6 256 2048 256 8 64 384 64 6 264 2376 264 9 72 504 72 7 272 2448 272 9 80 560 80 7 280 2520 280 9 88 616 88 7 288 2592 288 9 96 672 96 7 296 2664 296 9 104 728 104 7 304 2736 304 9 112 784 112 7 312 2808 312 9 120 840 120 7 320 2880 320 9 128 896 128 7 328 2952 328 9 136 1088 136 8 336 3024 336 9 144 1152 144 8 344 3096 344 9 152 1216 152 8 352 3168 352 9 160 1280 160 8 360 3240 360 9 168 1344 168 8 368 3312 368 9 176 1408 176 8 376 3384 376 9 184 1472 184 8 384 3456 384 9 192 1536 192 8 392 3528 392 9 200 1600 200 8 400 3600 400 9Figure 7
Comparison of transmitted qubits among our QBDQ scheme, J11, G12, and R13 schemes.


#### 4.3.2. Consumption of Exchanged Classic Messages

For a communication scheme, it should also consider the consumption of the exchanged classic messages. In the J11, J12, and R13 schemes,N×1 bits of encrypted data, considering each data item is a one-bit message (i.e., m=1), is transmitted from the cloud server to the client, so their exchanged classic messages are all O(N) cbits. In our scheme, Alice (Bob) returns a classical message Δs, i.e., a (log⁡N×m)-cbit classic message, to Charlie in Step 2. Since m=1, the exchanged message is just O(log⁡N) cbits.Table3 lists the numbers of transmitted qubits in different database capacities for the J11, G12, R13, and our QBDQ schemes, while Figure 8 gives a more intuitive comparison between our QBDQ scheme and the other QPQ schemes (J11, G12, and R13 schemes). Obviously, our scheme needs less consumption of exchanged classic messages than other QPQ protocols.Table 3
Exchanged classic messages in different database capacities for J11, G12, R13, and our QBDQ schemes.
Database size Exchanged messages Database size Exchanged messages J11/G12/R13 QBDQ J11/G12/R13 QBDQ 8 8 3 88 88 7 16 16 4 96 96 7 24 24 5 104 104 7 32 32 5 112 112 7 40 40 6 120 120 7 48 48 6 128 128 7 56 56 6 136 136 8 64 64 6 144 144 8 72 72 7 152 152 8 80 80 7 160 160 8Figure 8
Comparison of exchanged classic bits between our QBDQ scheme and the other QPQ schemes (J11, G12, and R13 schemes).In summary, Table4 lists the comparison among our QBDQ scheme and the other three QPQ schemes clearly. As shown in Table 4, our scheme achieves a great reduction on both the communication complexity and the consumption of exchanged classic messages. Besides, our QBDQ scheme just needs to perform quantum measurement two times, which is obviously less than the other ones.Table 4
Comparison among our QBDQ scheme and the other QPQ schemes.
Schemes Communication complexity (qubit) Exchanged message(bit) Measurement times J11 O( N log ⁡ N ) N+1 kN G12 O( N log ⁡ N ) N+1 kN R13 O(N) N+1 N Ours O( log ⁡ N ) 1 2


## 4.1. Correctness Analysis

Now, we analyze the correctness of the proposed scheme. Without loss of generality, suppose that the server Charlie has a database of 16 itemsD={5,9,6,12,2,11,11,6,5,10,7,15,6,11,6,9}, and he holds the corresponding encryption key sequence K={14,8,3,4,7,1,11,6,15,2,12,13,0,5,9,10}. Since N=16, the max value in K is 15, n=log⁡N=log⁡16=4, m=log⁡(15+1)=4. Here, we take Alice as an example to analyze the procedures of our QBDQ scheme as follows (suppose Alice wants to query the 9th item of the database).In Step1, Charlie prepares an initial state ϕK〉=1/4∑i=015i〉⊗0000〉 and performs an oracle operation OK on it to encode his encryption keys,(20)ϕ′=140K0+1K1+2K2+3K3+4K4+5K5+6K6+7K7+8K8+9K9+10K10+11K11+12K12+13K13+14K10+15K11=14014+18+23+34+47+51+611+76+815+92+1012+1113+120+135+149+1510Then, he sends the resultant state ϕ′〉 to Alice. In Step 2, Alice performs projective measurement on the first four qubits (i.e., index qubits) of ϕ′〉 in the computational basis {|0000〉,|0001〉,…,|1111〉}. Suppose the random measurement result is 12〉 (i.e., λA = 12), then the remaining qubits (i.e., the key qubits) collapse to the state |KλA〉=|0000〉, which means KλA=0000. But the data Alice wants to query is the ninth data D8, so she computes the difference between λA and the desirable query index q, ∆s=(λA-q)=4, and sends ∆s to Charlie. After receiving ∆s, Charlie updates the key sequence K through the formulation KiA=K(i+∆s)modN, then KiA={7,1,11,6,15,2,12,13,0,5,9,10,14,8,3,4}. He uses KiA to encrypt every data items: DiA=Di⊕KiA, that is, {2,8,13,10,13,9,7,11,5,15,14,5,8,3,5,13}. Then, in Step 3, Charlie prepares another state ϕD〉=1/4∑i=015i〉⊗0000〉 and applies the oracle operation ODA to embed the encrypted data items DiA,(21)ϕ′′=140D0+1D1+2D2+3D3+4D4+5D5+6D6+7D7+8D8+9D9+10D10+11D11+12D12+13D13+14D14+15D15=1402+18+213+310+413+59+67+711+85+915+1014+115+128+133+145+1513.Then, he sends the state ϕ′′〉 to Alice.Further, Alice performs modified Grover iteration onϕ′′〉 up to R=π/42n+m=π/428=13 times (actually, the number of iterations is 6), then she can obtain the encrypted query item p〉DpA〉=8〉5〉 with a high possibility, and measures it to get DpA=5. Alice uses the obtained key K8A=0 to decrypt the ninth item(22)D8=D8A⊕K8A=0101⊕0000=0101.Therefore, regardless of what measurement result Alice has obtained, she can finally obtain the query data correctly.Figure6 shows the entire execution process of Alice querying Charlie’s database in a simplified way. At the same time, it also sketched the execution of the other user Bob (assuming it queries the fifth data).Figure 6
The schematic graph of the execution process of Alice and Bob in our QBDQ scheme, assuring they query the9-th and5-th items, respectively.


## 4.2. Security Analysis

### 4.2.1. Privacy Analysis

Cloud Server's Privacy. Suppose the client Alice is dishonest, and she wants to obtain more information about Charlie’s database. In Step 1 of our scheme, the server Charlie sends the quantum state ϕ′〉=1/N∑i=0N-1i〉Ki〉 to client Alice through oblivious transfer strategy. Since all the information about the key sequence K is encoded in the state ϕ′〉, so Alice cannot extract the key form ϕ′〉 directly. Here we suppose the whole system of quantum state ϕ′〉 consisted of two subsystems, i.e., then-qubit quantum subsystemC(index qubits i〉) and them-qubit subsystemD(key qubits Ki〉). If Alice makes a projective measurement on the received state ϕ′〉, she will get the resultant state i〉Ki〉 for any i with the probability of 1/N. The whole system can be represented by the quantum ensemble ε=pi,ρ(i), here pi=1/N, (23)ρi=iKiKii.Here we get the upper limit of information that Alice can get from Charlie’s is determined by the Holevo bound [38],(24)HA:B≤Sρ-1N∑i=0N-1SρiHere Sρ denotes Von Neumann entropy of quantum state ρ,H(B:A) means the information Alice can get about Charlie’s key information (including the address i and according keys Ki), and we have(25)Sρ=S1N∑i=0N-1iKiKii=n+m.and Sρi=SiKiKi|i|=0; therefore,(26)HA:B≤n+m.Then, Alice can only get n-bit of address information (i.e., i) and the corresponding m-bit key (i.e., Ki) by measuring ρ. In addition, she will certainly lose the change to get her key Ki. This means Alice cannot extract more than one key from Charlie.Besides, in Step3, Charlie uses the offset key KiA=Ki+△s to encrypt the data items, and send its encoded state |ϕ′′〉=1/Δs∑i=0N-1i〉DiA〉 to Alice with oblivious transfer strategy. Alice’s privacy of query indexiis protected by the oblivious transfer strategy. For example, the transmitted state |ϕ′′〉 Alice received is a superposition state, i.e., |ϕ′′〉=1/N(0〉D0〉+1〉D1〉+⋯+N-1〉DN-1〉), which encapsulates all the query data DpA∣0≤p≤N-1 including the desirable one DpA. Alice obtains the query item DpA through the Grover iteration and the previously obtained key KλA. Suppose Bob is also dishonest, he has the same situation with Alice.Client’s Privacy. If Charlie is dishonest, he may try to obtain Alice’s private query indexp during the communication process. However, Alice only sends one classic message ∆s=λA-p to cloud server Charlie in Step 2, and Charlie does not know the encryption key which chosen by Alice, thus he cannot obtain any useful information about the data Alice wants to search. As same as Alice, Bob only sends a classic offset message ∆s=λB-p to Charlie, which prevents Charlie from obtaining his information.


### 4.2.2. Channel Security Analysis

The security of the quantum channel is guaranteed by the decoy-photon checking technology. The process of eavesdropping detected done by the two neighbor participants in our scheme is essentially equivalent to that in the BB84 scheme [36], which has been proved to be unconditionally secure. To be specific, the decoy qubits, which are randomly inserted into target qubits, are generated by randomly chosen from 0〉,1〉,+〉,-〉. After one participant sends the mixed decoy qubits and encrypted target qubits to quantum center, he will ask quantum center to measure them with the same bases these qubits were produced. For any outside eavesdropper, the bases used by participants are all random; the eavesdropper cannot produce the same qubits like decoy qubits before quantum center receives the qubits. Just like the situation in the BB84 scheme, if any outside eavesdropper exists in the process of our scheme, the eavesdropping actions will be found by the two participants.The outside eavesdropper cannot get the shared key because eavesdropper cannot distinguish target qubits form decoy qubits, and he can only choose one set of orthogonal basis to measure it, so the eavesdropper will certainly change the states of the qubit, and then he will be discovered. We assume that eavesdropper will do intercept-resend attack. Eavesdropper applies operationUE and auxiliary system |E which satisfies the following conditions:(27)UE0E=a0E00+b1E01,(28)UE1E=c0E01+d1E11.Here, a2+b2=1 and c2+d2=1. If the eavesdropper wants to extract the encode information precisely, then UE must satisfy(29)UE+E=12a0E00+b1E01+c0E10+d1E11=12+aE00+bE01+cE10+dE11,(30)UE-E=12a0E00+b1E01-c0E10-d1E11=12-aE00-bE01-cE10+dE11,(31)UE+yE=12a0E00+b1E01+ic0E10+id1E11=12+yaE00-ibE01+icE10-dE11,(32)UE-yE=12a0E00+b1E01-ic0E10-id1E11=12+yaE00+ibE01-icE10+dE11.From (29)–(32) we can obtain that(33)aE00-bE01+cE10-dE11=0,(34)aE00+bE01-cE10-dE11=0,(35)aE00+ibE01+icE10-dE11=0,(36)aE00-ibE01-icE10-dE11=0,we can get that a=d=1, b=c=0, and E00〉=E11〉, then we get(37)UE0E=0E00,(38)UE1E=1E11,and we can summarize that eavesdropper would not be found only when decoy qubits and target qubits are |0,|1, which is impossible. So there is no way for the eavesdropper to know the secret key.


## 4.2.1. Privacy Analysis

Cloud Server's Privacy. Suppose the client Alice is dishonest, and she wants to obtain more information about Charlie’s database. In Step 1 of our scheme, the server Charlie sends the quantum state ϕ′〉=1/N∑i=0N-1i〉Ki〉 to client Alice through oblivious transfer strategy. Since all the information about the key sequence K is encoded in the state ϕ′〉, so Alice cannot extract the key form ϕ′〉 directly. Here we suppose the whole system of quantum state ϕ′〉 consisted of two subsystems, i.e., then-qubit quantum subsystemC(index qubits i〉) and them-qubit subsystemD(key qubits Ki〉). If Alice makes a projective measurement on the received state ϕ′〉, she will get the resultant state i〉Ki〉 for any i with the probability of 1/N. The whole system can be represented by the quantum ensemble ε=pi,ρ(i), here pi=1/N, (23)ρi=iKiKii.Here we get the upper limit of information that Alice can get from Charlie’s is determined by the Holevo bound [38],(24)HA:B≤Sρ-1N∑i=0N-1SρiHere Sρ denotes Von Neumann entropy of quantum state ρ,H(B:A) means the information Alice can get about Charlie’s key information (including the address i and according keys Ki), and we have(25)Sρ=S1N∑i=0N-1iKiKii=n+m.and Sρi=SiKiKi|i|=0; therefore,(26)HA:B≤n+m.Then, Alice can only get n-bit of address information (i.e., i) and the corresponding m-bit key (i.e., Ki) by measuring ρ. In addition, she will certainly lose the change to get her key Ki. This means Alice cannot extract more than one key from Charlie.Besides, in Step3, Charlie uses the offset key KiA=Ki+△s to encrypt the data items, and send its encoded state |ϕ′′〉=1/Δs∑i=0N-1i〉DiA〉 to Alice with oblivious transfer strategy. Alice’s privacy of query indexiis protected by the oblivious transfer strategy. For example, the transmitted state |ϕ′′〉 Alice received is a superposition state, i.e., |ϕ′′〉=1/N(0〉D0〉+1〉D1〉+⋯+N-1〉DN-1〉), which encapsulates all the query data DpA∣0≤p≤N-1 including the desirable one DpA. Alice obtains the query item DpA through the Grover iteration and the previously obtained key KλA. Suppose Bob is also dishonest, he has the same situation with Alice.Client’s Privacy. If Charlie is dishonest, he may try to obtain Alice’s private query indexp during the communication process. However, Alice only sends one classic message ∆s=λA-p to cloud server Charlie in Step 2, and Charlie does not know the encryption key which chosen by Alice, thus he cannot obtain any useful information about the data Alice wants to search. As same as Alice, Bob only sends a classic offset message ∆s=λB-p to Charlie, which prevents Charlie from obtaining his information.


## 4.2.2. Channel Security Analysis

The security of the quantum channel is guaranteed by the decoy-photon checking technology. The process of eavesdropping detected done by the two neighbor participants in our scheme is essentially equivalent to that in the BB84 scheme [36], which has been proved to be unconditionally secure. To be specific, the decoy qubits, which are randomly inserted into target qubits, are generated by randomly chosen from 0〉,1〉,+〉,-〉. After one participant sends the mixed decoy qubits and encrypted target qubits to quantum center, he will ask quantum center to measure them with the same bases these qubits were produced. For any outside eavesdropper, the bases used by participants are all random; the eavesdropper cannot produce the same qubits like decoy qubits before quantum center receives the qubits. Just like the situation in the BB84 scheme, if any outside eavesdropper exists in the process of our scheme, the eavesdropping actions will be found by the two participants.The outside eavesdropper cannot get the shared key because eavesdropper cannot distinguish target qubits form decoy qubits, and he can only choose one set of orthogonal basis to measure it, so the eavesdropper will certainly change the states of the qubit, and then he will be discovered. We assume that eavesdropper will do intercept-resend attack. Eavesdropper applies operationUE and auxiliary system |E which satisfies the following conditions:(27)UE0E=a0E00+b1E01,(28)UE1E=c0E01+d1E11.Here, a2+b2=1 and c2+d2=1. If the eavesdropper wants to extract the encode information precisely, then UE must satisfy(29)UE+E=12a0E00+b1E01+c0E10+d1E11=12+aE00+bE01+cE10+dE11,(30)UE-E=12a0E00+b1E01-c0E10-d1E11=12-aE00-bE01-cE10+dE11,(31)UE+yE=12a0E00+b1E01+ic0E10+id1E11=12+yaE00-ibE01+icE10-dE11,(32)UE-yE=12a0E00+b1E01-ic0E10-id1E11=12+yaE00+ibE01-icE10+dE11.From (29)–(32) we can obtain that(33)aE00-bE01+cE10-dE11=0,(34)aE00+bE01-cE10-dE11=0,(35)aE00+ibE01+icE10-dE11=0,(36)aE00-ibE01-icE10-dE11=0,we can get that a=d=1, b=c=0, and E00〉=E11〉, then we get(37)UE0E=0E00,(38)UE1E=1E11,and we can summarize that eavesdropper would not be found only when decoy qubits and target qubits are |0,|1, which is impossible. So there is no way for the eavesdropper to know the secret key.


## 4.3. Efficiency Analysis

As we know, quantum-based schemes have greater information capacity than classic ones. In order to evaluate the efficiency of our QDBQ scheme more objectively, we choose some of the most representative quantum schemes as comparison objects, for example, Jakobi et al.’s quantum private query (QPQ) scheme (J11 for short) [39], Gao et al.’s QPQ scheme (G12) [40], and Rao et al.’s QPQ) scheme (R13) [41].To evaluate the efficiency of quantum communication schemes, there are mainly two indicators: the communication complexity (i.e., the number of transmitted qubits), and the consumption of exchanged classic messages (i.e., the number of exchanged classic bits).


### 4.3.1. Communication Complexity

The communication complexity, i.e., the number of quantum bits (qubits) transmitted in the communication process, is one of the key indicators of the efficiency for communication scheme. In J11 and G12 schemes, the cloud server (Charlie) sendsk×N qubits to the client (Alice), where k is the number of divided substrings. These k substrings are added bitwise in order to reduce Alice’s information on the key to roughly one bit (i.e., n-=N(1/4)k≈1), so k=log⁡N. In summary, N×log⁡N qubits are transmitted in J11 and J12 schemes, and its communication complexity is O(Nlog⁡N). But in the R13 scheme, the number of qubits that need to be exchanged is reduced to O(N), so the communication complexity is O(N).In our QBDQ scheme, Charlie firstly transmits a (log⁡N+m)-qubit state ϕ′ (ψ′) for sending the encryption keys in Step 1, and the (log⁡N+m)-qubit state ϕ′′ (ψ′′) containing every encrypted data Di(0≤i≤N-1) is transmitted to Alice(Bob) in Step 3. Considering that each data item the cloud server holds is an only one-bit message in J11, G12 and R13 schemes, here we let m=1. Therefore, the transmitted qubits are 2(log⁡N+1), so its communication complexity is O(log⁡N).To be more intuitive, we calculate the numbers of transmitted qubits in different database capacities for the J11, G12, R13, and our QBDQ schemes (see Table2) and show the comparison results among them in Figure 7. As shown in this figure, J11 and G12 schemes have the same qubits consumption, R13 scheme reduces the consumption, and our QBDQ scheme has the lowest qubits consumption. That is, our scheme has the lowest communication complexity among them.Table 2
Numbers of transmitted qubits in different database capacities for J11, G12, R13, and our QBDQ schemes.
Database size Transmitted messages(qubit) Database size Transmitted messages(qubit) J11/ G12 R13 QBDQ J11/G12 R13 QBDQ 8 24 8 3 208 1664 208 8 16 64 16 4 216 1728 216 8 24 120 24 5 224 1792 224 8 32 160 32 5 232 1856 232 8 40 240 40 6 240 1920 240 8 48 288 48 6 248 1984 248 8 56 336 56 6 256 2048 256 8 64 384 64 6 264 2376 264 9 72 504 72 7 272 2448 272 9 80 560 80 7 280 2520 280 9 88 616 88 7 288 2592 288 9 96 672 96 7 296 2664 296 9 104 728 104 7 304 2736 304 9 112 784 112 7 312 2808 312 9 120 840 120 7 320 2880 320 9 128 896 128 7 328 2952 328 9 136 1088 136 8 336 3024 336 9 144 1152 144 8 344 3096 344 9 152 1216 152 8 352 3168 352 9 160 1280 160 8 360 3240 360 9 168 1344 168 8 368 3312 368 9 176 1408 176 8 376 3384 376 9 184 1472 184 8 384 3456 384 9 192 1536 192 8 392 3528 392 9 200 1600 200 8 400 3600 400 9Figure 7
Comparison of transmitted qubits among our QBDQ scheme, J11, G12, and R13 schemes.


### 4.3.2. Consumption of Exchanged Classic Messages

For a communication scheme, it should also consider the consumption of the exchanged classic messages. In the J11, J12, and R13 schemes,N×1 bits of encrypted data, considering each data item is a one-bit message (i.e., m=1), is transmitted from the cloud server to the client, so their exchanged classic messages are all O(N) cbits. In our scheme, Alice (Bob) returns a classical message Δs, i.e., a (log⁡N×m)-cbit classic message, to Charlie in Step 2. Since m=1, the exchanged message is just O(log⁡N) cbits.Table3 lists the numbers of transmitted qubits in different database capacities for the J11, G12, R13, and our QBDQ schemes, while Figure 8 gives a more intuitive comparison between our QBDQ scheme and the other QPQ schemes (J11, G12, and R13 schemes). Obviously, our scheme needs less consumption of exchanged classic messages than other QPQ protocols.Table 3
Exchanged classic messages in different database capacities for J11, G12, R13, and our QBDQ schemes.
Database size Exchanged messages Database size Exchanged messages J11/G12/R13 QBDQ J11/G12/R13 QBDQ 8 8 3 88 88 7 16 16 4 96 96 7 24 24 5 104 104 7 32 32 5 112 112 7 40 40 6 120 120 7 48 48 6 128 128 7 56 56 6 136 136 8 64 64 6 144 144 8 72 72 7 152 152 8 80 80 7 160 160 8Figure 8
Comparison of exchanged classic bits between our QBDQ scheme and the other QPQ schemes (J11, G12, and R13 schemes).In summary, Table4 lists the comparison among our QBDQ scheme and the other three QPQ schemes clearly. As shown in Table 4, our scheme achieves a great reduction on both the communication complexity and the consumption of exchanged classic messages. Besides, our QBDQ scheme just needs to perform quantum measurement two times, which is obviously less than the other ones.Table 4
Comparison among our QBDQ scheme and the other QPQ schemes.
Schemes Communication complexity (qubit) Exchanged message(bit) Measurement times J11 O( N log ⁡ N ) N+1 kN G12 O( N log ⁡ N ) N+1 kN R13 O(N) N+1 N Ours O( log ⁡ N ) 1 2


## 4.3.1. Communication Complexity

The communication complexity, i.e., the number of quantum bits (qubits) transmitted in the communication process, is one of the key indicators of the efficiency for communication scheme. In J11 and G12 schemes, the cloud server (Charlie) sendsk×N qubits to the client (Alice), where k is the number of divided substrings. These k substrings are added bitwise in order to reduce Alice’s information on the key to roughly one bit (i.e., n-=N(1/4)k≈1), so k=log⁡N. In summary, N×log⁡N qubits are transmitted in J11 and J12 schemes, and its communication complexity is O(Nlog⁡N). But in the R13 scheme, the number of qubits that need to be exchanged is reduced to O(N), so the communication complexity is O(N).In our QBDQ scheme, Charlie firstly transmits a (log⁡N+m)-qubit state ϕ′ (ψ′) for sending the encryption keys in Step 1, and the (log⁡N+m)-qubit state ϕ′′ (ψ′′) containing every encrypted data Di(0≤i≤N-1) is transmitted to Alice(Bob) in Step 3. Considering that each data item the cloud server holds is an only one-bit message in J11, G12 and R13 schemes, here we let m=1. Therefore, the transmitted qubits are 2(log⁡N+1), so its communication complexity is O(log⁡N).To be more intuitive, we calculate the numbers of transmitted qubits in different database capacities for the J11, G12, R13, and our QBDQ schemes (see Table2) and show the comparison results among them in Figure 7. As shown in this figure, J11 and G12 schemes have the same qubits consumption, R13 scheme reduces the consumption, and our QBDQ scheme has the lowest qubits consumption. That is, our scheme has the lowest communication complexity among them.Table 2
Numbers of transmitted qubits in different database capacities for J11, G12, R13, and our QBDQ schemes.
Database size Transmitted messages(qubit) Database size Transmitted messages(qubit) J11/ G12 R13 QBDQ J11/G12 R13 QBDQ 8 24 8 3 208 1664 208 8 16 64 16 4 216 1728 216 8 24 120 24 5 224 1792 224 8 32 160 32 5 232 1856 232 8 40 240 40 6 240 1920 240 8 48 288 48 6 248 1984 248 8 56 336 56 6 256 2048 256 8 64 384 64 6 264 2376 264 9 72 504 72 7 272 2448 272 9 80 560 80 7 280 2520 280 9 88 616 88 7 288 2592 288 9 96 672 96 7 296 2664 296 9 104 728 104 7 304 2736 304 9 112 784 112 7 312 2808 312 9 120 840 120 7 320 2880 320 9 128 896 128 7 328 2952 328 9 136 1088 136 8 336 3024 336 9 144 1152 144 8 344 3096 344 9 152 1216 152 8 352 3168 352 9 160 1280 160 8 360 3240 360 9 168 1344 168 8 368 3312 368 9 176 1408 176 8 376 3384 376 9 184 1472 184 8 384 3456 384 9 192 1536 192 8 392 3528 392 9 200 1600 200 8 400 3600 400 9Figure 7
Comparison of transmitted qubits among our QBDQ scheme, J11, G12, and R13 schemes.


## 4.3.2. Consumption of Exchanged Classic Messages

For a communication scheme, it should also consider the consumption of the exchanged classic messages. In the J11, J12, and R13 schemes,N×1 bits of encrypted data, considering each data item is a one-bit message (i.e., m=1), is transmitted from the cloud server to the client, so their exchanged classic messages are all O(N) cbits. In our scheme, Alice (Bob) returns a classical message Δs, i.e., a (log⁡N×m)-cbit classic message, to Charlie in Step 2. Since m=1, the exchanged message is just O(log⁡N) cbits.Table3 lists the numbers of transmitted qubits in different database capacities for the J11, G12, R13, and our QBDQ schemes, while Figure 8 gives a more intuitive comparison between our QBDQ scheme and the other QPQ schemes (J11, G12, and R13 schemes). Obviously, our scheme needs less consumption of exchanged classic messages than other QPQ protocols.Table 3
Exchanged classic messages in different database capacities for J11, G12, R13, and our QBDQ schemes.
Database size Exchanged messages Database size Exchanged messages J11/G12/R13 QBDQ J11/G12/R13 QBDQ 8 8 3 88 88 7 16 16 4 96 96 7 24 24 5 104 104 7 32 32 5 112 112 7 40 40 6 120 120 7 48 48 6 128 128 7 56 56 6 136 136 8 64 64 6 144 144 8 72 72 7 152 152 8 80 80 7 160 160 8Figure 8
Comparison of exchanged classic bits between our QBDQ scheme and the other QPQ schemes (J11, G12, and R13 schemes).In summary, Table4 lists the comparison among our QBDQ scheme and the other three QPQ schemes clearly. As shown in Table 4, our scheme achieves a great reduction on both the communication complexity and the consumption of exchanged classic messages. Besides, our QBDQ scheme just needs to perform quantum measurement two times, which is obviously less than the other ones.Table 4
Comparison among our QBDQ scheme and the other QPQ schemes.
Schemes Communication complexity (qubit) Exchanged message(bit) Measurement times J11 O( N log ⁡ N ) N+1 kN G12 O( N log ⁡ N ) N+1 kN R13 O(N) N+1 N Ours O( log ⁡ N ) 1 2


## 5. Related Work

Cloud database services are typically run on cloud computing platforms, and access to cloud databases is provided as a service, which takes care of scalability and availability of the database, and it makes the underlying software-stack transparent to the user.Benefit from cloud computing technologies and devices, more and more data owners are motivated to outsource their data to cloud servers for great convenience in data management, and cloud database query has attracted the attention of scholars. Cloud database query was firstly proposed by Chor et al. [42], where the privacy of the server cannot be guaranteed, which means that sensitive data (e.g., health records, financial transactions) stored in cloud database is threatened by information leaks. Therefore, how to preserve the privacy of sensitive data in the process of cloud database query has become an important topic. In order to solve the problem, many methods are proposed to guarantee the privacy preservation of database query [12–18]; one of the most popular methods is SE.SE is a special kind of private query, which enables the user to store the encrypted data to the cloud and execute keyword search over ciphertext. Since Song et al.[15] proposed the first practical private database query scheme for searching on encrypted data in cloud and provided the security proofs for the scheme, some other schemes to address privacy protection issues in cloud database queries have also been proposed[17, 18]. In order to support more complex queries, the conjunctive keyword search scheme [14] over encrypted data has been proposed. After that, a more general approach, predicate encryption [16], which supports inner-product, was also proposed.In general, most of the above schemes [12–18, 42] are based on public key cryptography such as RSA, and its security is based on mathematical NP-hard problems. Therefore, these schemes are difficult to crack in polynomial time for classic computers. All of the above protocols are based on public key cryptography such as RSA. On a quantum computer, to factor an integer N, Shor’s algorithm [19] can run in polynomial time (the time taken is polynomial in log⁡N, which is the size of the input. Specifically, it takes quantum gates of order O(log⁡N2log⁡log⁡Nlog⁡log⁡log⁡N) using fast multiplication [43], thus demonstrating that the integer-factorization problem (the large factorization problem is the security foundation of RSA) can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is almost exponentially faster than the most efficient known classical factoring algorithm, so we can say that these schemes [12–18, 42] are not resistant to quantum attacks. Different from classic schemes based on mathematical complexity, the security of quantum-based schemes is guaranteed by some properties of quantum mechanics, such as noncloning theorem and uncertainty principle. They are considered to have potential unconditional security and of course also include resistance to quantum attacks.Recently, some researchers have tried to utilize quantum mechanics to design private query schemes. In 2008, Giovannetti et al. [44] proposed the first quantum private query (QPQ) protocol. The client sends the query |jQ and a decoy state |jQ+|0Q/2 to the server in random order, then Bob uses each of them to interrogate his database using a qRAM (which records the reply to her queries in a register R) and returns |jQ|AjR or |jQ|AjR+|0Q|0R/2. The returned decoy state is used to check the eavesdropping of the server or the outside party. In 2011, Olejnik [45] presented a new QPQ protocol in a similar form with Giovannetti et al.’s protocol. By subtly selecting the oracle operation and the encoding scheme, one query state can achieve two aims simultaneously, i.e., obtaining the expected information and checking Bob's potential attack, so the communication complexity is reduced. Unfortunately, it is very vulnerable to the realities of significant transmission losses.Therefore, Jakobi et al. [39] proposed a novel QPQ protocol (J11) based on the QKD protocol, where QKD is essentially a quantum analog of SE. In this protocol, an asymmetric key can be distributed between Alice and Bob by utilizing SARG04 QKD protocol, and Bob encrypts the whole database with the QKD key. Alice only knows few bits of the key, which ensures the database privacy. Compared with the previous QPQ protocols, J11 protocol is loss-tolerant and more secure. What is more, the J11 protocol can be easily generalized to the large database. Later, Gao et al. [40] proposed a flexible generalized protocol (G12) based on the J11 protocol, which introduced a variable θ to adjust the balance between database security and client privacy. Considering a database with sizeN, the J11 and G12 protocols have a communication complexity ofO(Nlog⁡N). In order to reduce the complexity, Rao et al. [41] gave two more efficient protocols (R13), which reduced the number of exchanged qubits toO(N).Different from classical encryption schemes based on some mathematical difficult problems, these findings have shown the potential in either the improvements of efficiency or the enhancements of security in cloud computing field with large computing resources and also brought new quantum technologies to solve private database query problems. However, to the best of our knowledge, there are few studies focusing on the quantum-based privacy-preserving database query problem in cloud environment. Therefore, we combine quantum mechanics with cloud database queries and proposed a QBDQ which aims to realize the privacy preservation for the clients and cloud server.


## 6. Conclusion and Future Work

As far as we know, the existing QPQ schemes either belong to the qRAM-based schemes, such as Giovannetti et al.’s [44] and Olejnik’s [45] schemes, or belong to the QKD-based schemes, such as Jakobi et al.’s [39], Gao et al.’s [40], and Rao et al.’ s [41] schemes. These QKD-based schemes solve the problem of the server’s privacy; their communication complexity needs to be further reduced. In this study, we propose an efficient quantum private query scheme based on oracle operation, modified Grover iteration, oblivious transfer strategy, and the special offset encryption mechanism rather than QKD or qRAM. Compared with those schemes, our QBDQ scheme shows higher efficiency in terms of the communication complexity, the consumption of exchanged message, and the quantum measurement.In our QBDQ scheme, we adopt the oblivious transfer strategy to solve the problem of the client’s privacy; i.e., the client will ask the server to transmit all these encrypted data items to him/her. But in a real-world cloud environment, this is not a good approach. Although it guarantees that there is no information about the query index to be leaked, but it needs to transmit too many data items from the cloud database. Even if quantum resources have an exponential high-capacity advantage, it is also a waste of resources. Maybe the “query window” strategy is a better choice. To be specific, the client can firstly choose an index window that contains the desirable query item and ask the server to transmit these encrypted data items in this window scope other than the all data items, to him/her in a quantum way. Although there is certain information leakage from the perspective of information theory, it can save quantum resources. In this strategy, the selection of the size of a query window is a key point. In order to achieve a balance of efficiency and security, perhaps some game theory (such as, Nash Equilibrium [46, 47]) and penalty functions [48–50] can provide relevant optimized solutions.It is worth noting that although the proposed solution involves two clients, for the sake of brevity (and for comparison with other quantum schemes), Alice and Bob do not interact. This is the most common pattern in cloud database queries. For the multiparty joint inquiry method, we will discuss it in future work. In addition, we just consider the ideal framework of the privacy-preserving database query in cloud environment; i.e., all the clients and cloud server are semihonest. But in a real cloud environment, clients and servers may be untrustworthy. How to generalize our QBDQ into such multiuser and the untrusted scenario is an interesting work.



---

*Source: 4923590-2019-04-01.xml*