Open AccessArticle

Quantum Private Query Protocol Based on Two Non-Orthogonal States

Yan Chang

^*,

Shibin Zhang

Guihua Han

Zhiwei Sheng

Lili Yan

and

Jinxin Xiong

College of Information Security Engineering, Chengdu University of Information Technology, Chengdu 610225, China

Author to whom correspondence should be addressed.

Entropy 2016, 18(5), 163; https://doi.org/10.3390/e18050163

Submission received: 15 December 2015 / Revised: 14 April 2016 / Accepted: 20 April 2016 / Published: 3 May 2016

(This article belongs to the Special Issue Entanglement Entropy)

Download

Browse Figures

Figure 1
When N = 10,000, <math display="inline"> <semantics> <mrow> <mover accent="true"> <mi>n</mi> <mo stretchy="true">¯</mo> </mover> </mrow> </semantics> </math> << N can be achieved. "> Figure 2
The probabilities that Eve1 and Eve2 know Alice’s bits for different θ in our protocol, G-protocol and Y-protocol. The solid line represents the probabilities for G-protocol (PTG) and Y-protocol (PTY); the star line represents the probability for our protocol (PT). "> Figure 3
Comparison of probability with which Alice correctly guesses the bit of Bob for different θ between our protocol and G-protocol when k = 2. The solid line represents Pguess for G-protocol; the dotted line represents Pguess for our protocol. "> Figure 4
Comparisons of probability with which Bob knowing Alice’s bits for different θ between our protocol and G-protocol. The star line represents Pb for G-protocol; the dotted line represents the upper bound of Pb for our protocol; the solid line represents the lower bound of Pb for our protocol. ">

Versions Notes

Abstract

We propose a loss tolerant quantum private query (QPQ) protocol based on two non-orthogonal states and unambiguous state discrimination (USD) measurement. By analyzing a two-point attack by a third party, we find that our protocol has a stronger ability to resist external attacks than G-protocol and Y-protocol. Our protocol requires a smaller number of compressions than that in G-protocol (Gao et al., Opt. Exp. 2012, 20, 17411–17420) and Y-protocol (Yan et al. Quant. Inf. Process. 2014, 13, 805–813), which means less post-processing. Our protocol shows better database security and user privacy compared with G-protocol.

Keywords:

quantum private query; two-point attack; conclusive bits

1. Introduction

Nowadays, communications are omnipresent. The problems of security and privacy have come to assume an unprecedented importance. Cryptography is an effective way to ensure data security in communication. Both classical and quantum cryptography can be used to ensure security. However, a higher advantage in security has been shown for quantum physical principles. Therefore, in recent years, more and more scholars have been paying attention to quantum cryptography.

In communications, the safety of common privacy is usually considered. However, in communications among distrustful users, both common privacy and individual privacy need to be protected. Private information retrieval (PIR) [1] is an application in such research areas, which guarantees the security of private database query. Another similar application is called symmetrically private information retrieval (SPIR) [2], which finishes the following task: user (Alice) obtains a record in a database that she has paid for it, however, the database provider (Bob) should not know which record Alice obtains. On the other hand, Alice should not know about other records that she does not pay for. That is, SPIR protects both Alice’s privacy and Bob’s database privacy. However, classical cryptosystems and using physical principles cannot ideally realize the task of SPIR [3].

Quantum Private Query (QPQ) is the quantum scheme for the SPIR problem. Bennett [4] and Brassard [5] proposed quantum protocols to solve the similar tasks of SPIR, and it was found to be difficult to offer complete protection for both sides. In 2008, the pioneer QPQ scheme (GLM protocol, where GML denotes the first letter of the name of the three authors) has been put forward by Giovannetti et al. [6]. In the scheme, oracle operations are used to denote records in the database and are operated on the incoming query states. Query state and decoy state are needed in the protocol. The query state is used to obtain the needed record from the database. While possible attacks from Bob are checked with the decoy state, in the GLM scheme, Alice’s privacy is protected by the non-signaling principle, which means that the spiteful behavior of Bob may lead to wrong answers to Alice. The behavior of Bob will be found by Alice later which will destroy her trust in him, that is called being cheat sensitive for user privacy. On the other hand, GLM protocol shows good database privacy. That is, no more than two records are obtained through dishonest queries. GLM protocol displays better performance in communication complexity and computational complexity compared with existing schemes. After that, the proof-of-principle experimental realization and the security analysis of GLM protocol were done in Refs. [7,8], respectively. Similar with GLM protocol, Olejnik et al. put forward O-protocol [9] (another QPQ protocol) based on oracle operation. O-protocol reduces communication complexity further by using only one query state to obtain the needed record from the database and detect eavesdropping from Bob.

Although the existing schemes show high quality theoretically, they are hard to realize for large databases because of the difficulty of high-dimensional oracle operation. Jakobi et al. provides a new way for solving the difficulty, in which Alice and Bob share an oblivious key based on SARG04 QKD, which is proposed by Scarani et al. in 2004 [10]. This scheme is a pioneer practical QPQ protocol (J-protocol) [11]. In this practical scheme, Bob knows the whole key, which is for encrypting the whole database, and Alice knows only limited bits of the key, which safeguards the database privacy. Oracle operations and other complex operations are not included in J-protocol; therefore, it is easy to realize for a large database.

In 2012, Gao et al. put forward a flexible QPQ scheme (G-protocol) [12] based on J-protocol. G-protocol shows better performance in flexibility, communication complexity and security than J-protocol. In G-protocol, non-orthogonal states {|0 >,|1 >,|0′ >,|1′ >} are selected as carrier states. (Here, |0′ > = cosθ|0 > + sinθ|1 >, |1′ > = sinθ|0 > − cosθ|1 >, and θ is polarization angle). By adjusting the value of θ, the length of Alice’s key bits is limited to a certain reasonable value. When θ < π/4, G-protocol displays better database security, but poor user privacy.

In 2013, Yang et al. put forward another QPQ scheme (Y-protocol) [13] based on a two-particle entangled state and non-orthogonal projective measurements. Y-protocol has all the features of G-protocol, such as being flexible, loss tolerant and practical. What’s more, it displays a better user privacy.

In this paper, we presents another QPQ scheme based on two non-orthogonal states and unambiguous state discrimination (USD) measurement. Our protocol can resist two-point attacks by a third party. In our protocol, a smaller number of compressions is required than G-protocol and Y-protocol under similar conditions, which means that less post-processing is needed in our protocol. Our protocol shows better database security and user privacy compared with G-protocol. Furthermore, our protocol requires a bigger polarization angle to achieve similar conditions (the number of compressions, the average bits that Alice will know in the final key, the probability that Alice can not know any bits at all and the length of Bob’s final key) than G-protocol, which means that our protocol is easier to realize technically compared with Gao’s protocol.

2. The QPQ Protocol Based on Two Non-Orthogonal States

On assumption that N records are included in Bob’s database, one of them is bought by Alice, and Alice intends to obtain it in secret. The scheme is to help them to complete the task safely. Our idea is to distribute a pair of oblivious secret keys between Alice and Bob which is known completely to Bob and partly to Alice, through a series of steps. To try to reduce the bits Alice knows in the raw key, Bob generates a raw key with length kN, where k is a natural number.

(1): Bob randomly prepares some non-orthogonal states $| φ_{0} 〉$ or $| φ_{1} 〉$ forming quantum sequence S, where

$\begin{matrix} | φ_{0} 〉 = cos \frac{θ}{2} | 0 〉 + sin \frac{θ}{2} | 1 〉, \\ | φ_{1} 〉 = cos \frac{θ}{2} | 0 〉 - sin \frac{θ}{2} | 1 〉 . \end{matrix}$

(1)

The range of parameter θ is between 0 and π/2. Bob inserts some decoy states |+ >,|− >,|0 > or|1 > in sequence S randomly, which forms new sequence S’. Bob tells Alice the length of sequence S’ through an authenticated channel. Then, Bob sends new sequence S’ to Alice.

(2): When Alice receives each particle that Bob sends to her, she stores it in quantum memory firstly. After Alice has received the whole sequence S’, Alice informs Bob about this. Then, Bob tells Alice which particles are used as decoy states and the basis of the corresponding decoy state. Alice extracts decoy states and measures them. Alice tells Bob the measurement results. Bob determines whether there is eavesdropping by comparing the information Alice reports and the decoy states Bob prepares. If there is eavesdropping, Bob stops the protocol.
(3): Alice measures the rest particles with unambiguous state discrimination (USD) method [14] to distinguish which state the qubit is in. The success probability of this USD measurement is bounded (from above) by p = 1 − $F (| φ_{0} 〉 〈 φ_{0} |, | φ_{1} 〉 〈 φ_{1} |)$ =1 − $| 〈 φ_{0} | φ_{1} 〉 |$ = 1 − cosθ, where $F (| φ_{0} 〉 〈 φ_{0} |, | φ_{1} 〉 〈 φ_{1} |) =$ $T r (\sqrt{| φ_{0} 〉 〈 φ_{0} | | φ_{1} 〉 〈 φ_{1} | | φ_{0} 〉 〈 φ_{0} |})$ is the fidelity between the two states to be discriminated. That is, Alice obtains the state of the qubit she measures with probability p = 1 − cosθ. Thus, Alice knows the corresponding bit that the qubit is carrying with a certain probability p = 1 − cosθ. For Bob, he doesn’t know which particle Alice measures successfully. Alice represents $| φ_{0} 〉$ as “0” and $| φ_{1} 〉$ as “1”. Alice publishes which qubits in sequence S she has successfully received.
(4): Bob also obtains a binary sequence according to the quantum sequence S that Bob prepares and the rule: $| φ_{0} 〉$ denotes “0” and $| φ_{1} 〉$ denotes “1”.
(5): For the lost particles Alice publishes, Bob flips his corresponding bits randomly. Then Bob randomly adds a bit “0” or “1” behind his data; by doing so, Bob doubles his key. Obviously, Bob’s bits corresponding to lost particles are all used as parts of the raw key. Therefore, Alice will not falsely declare lost particles, because Alice will not benefit from reporting a lost particle for any unsuccessful USD measurement, such as increasing the probability of conclusive measurements and knowing a larger fraction of bits that are expected for a giving θ. On the contrary, Bob will obtain more information about Alice’s bits if Alice reports a lost particle for any unsuccessful USD measurement. In addition, by flipping Bob’s bits corresponding to lost particles randomly, Eve can not obtain database information by measuring some lost particles.

Table 1 and Table 2 are examples of sharing oblivious raw keys between Alice and Bob by using all particles in sequence S (the lost particles and received particles). Table 1 shows the case that Alice honestly reports all lost particles. Table 2 shows the case that Alice dishonestly reports the lost particles; that is, Alice will report some measuring failure particles as lost particles. In Table 1 and Table 2, “#” denotes the honest reporting of lost particle, “?” denotes measurement failure of Alice , “$” denotes measurement failure of Alice but reporting particles as lost particles, “*” denotes knowing nothing about the bit. In Table 1 and Table 2, the bits in Bob’s final bits corresponding to reporting as lost particles (including the honest reporting of lost particles and measurement failure by Alice, but reporting particles as lost particles) are the results of flipping the original Bob’s bits randomly.

In Table 1, Alice honestly reports all lost particles (1,9) and measurement failure of particles (4,5,7,8). In Table 2, Alice dishonestly reports the lost particles (1,4,7–9), where particles 4,7,8 are the case of measurement failure by Alice but reporting particles as lost particles. By comparing Alice’s bits and Bob’s final bits in Table 1 and Table 2, we find that the dishonest reporting of lost particles will not impact Alice’s bits. In addition, we still find that the bits corresponding to dishonest reporting of lost particles in Bob’s final bits are the results of flipping Bob’s corresponding original bits randomly; however, Alice knows nothing about these bits. From Table 1 and Table 2, we find that if Alice honestly reports lost particles, Bob knows that Alice may successfully measure particles 2–8; if Alice reports failure measurements as lost particles, Bob knows that Alice may successfully measure particles 2,3,5,6. That is, the probability that Bob knows Alice’s bits increases. Therefore, dishonest reporting of lost particles will make Bob know more information of Alice’s bits; however, Alice can not know more information about Bob’s final bits.

For Alice, with the exception of those two-bit-groups corresponding to lost particles, she owns the first bit of each of Bob’s two-bit-groups corresponding to received photons, but nothing about the second bit. Whatever the measurement result of Alice, the second bit is 0 or 1 with equal probability. Therefore, Alice knows the first bit of Bob’s each two-bit-group corresponding to received photons with probability p = 1 − cosθ.

In this way, Alice and Bob have shared a raw key K^r known completely to Bob and partly to Alice. Obviously, for each two-bit-group corresponding to received photons, Alice should know only one bit with probability 1 − cosθ. Therefore, Alice knows only p ≤ (1 − cosθ)/2 of the raw key K^r on average. That is, (1 − cosθ)/2 is the upper bound of the bits that Alice knows of the raw key K^r.

(6): To reduce the bits by Alice known in the raw key they shared in the above steps, Alice and Bob execute post-processing on the raw key. Because the length of K^r is kN, where k is a natural number, Alice and Bob break K^r up into k parts, thus the length of each parts is N. By adding the k parts bitwise, the raw key becomes a final key with length N. Bob knows the whole key, while Alice only knows several bits. For example, Bob’s bits are “011011100000” and Alice's bits are “**1*1***0***”, where “*” denotes that Alice knows nothing about the bit. If k = 2, Bob and Alice divide their bits into two parts, respectively: Bob's bits: “011011, 100000”; Alice's bits: “**1*1*, **0***”. Then, Bob and Alice perform bitwise exclusive-OR (XOR) operation on the top six bits and the post six bits, respectively: Bob: 011011 XOR 100000 = 111011; Alice: **1*1* XOR **0*** = **1***. Therefore, Bob’s and Alice’s key is 111011 and **1***, respectively. The process is similar to that in J-protocol, G-protocol and Y-protocol. If Alice knows nothing of the final key after this post-processing, the protocol should be restarted. However, this condition can be avoided by choosing appropriate parameters, which will be analyzed later.
(7): Bob encrypts the database and Alice obtains the record that she needs. The detailed procedure is as follows: if Alice owns the jth bit K_j of Bob’s key K, and she needs to obtain the ith record X_i in Bob’s database. Then, Alice tells Bob the value s = j − i. If s is a negative number, Bob shifts K right circularly with |s| bits; otherwise, Bob shifts K left circularly with s bits, by doing so Bob can obtain a new key K′. Bob encrypts the database with K′ in the way of a one-time pad. Alice decrypts the ith record with her key K_j.

3. Analysis

After step (6) (Alice and Bob add k substrings bitwise), Alice obtains

\bar{n} = N R^{k}

bits of the final key K on average, where R =

\frac{1 - cos θ}{2}

. The probability that Alice can not know any bits at all is

P_{0} = {(1 - R^{k})}^{N} = {(1 - \frac{\bar{n}}{N})}^{N}

. When

N ≫ \bar{n}

is satisfied,

P_{0} \approx e^{- \bar{n}}

is obtained and

\bar{n}

follows a Poisson distribution approximately. When

\bar{n} \leq 2

is satisfied, we have

P_{0} \geq 0.135

; when

\bar{n} \geq 3

is satisfied, we have

P_{0} \leq 0.05

. In order to make Alice get less bits, at the same time, the failure rate is very small, obviously,

\bar{n} = 3

is an optimal value. We have

P_{\geq 4} = 1 - P_{3} - P_{2} - P_{1} - P_{0} = 1 - 13 e^{- 3} = 0.35

and

P_{\geq 5} =

1 - P_{4} - P_{3} - P_{2} - P_{1} - P_{0} = 0.18

, where

P_{\geq 4}

denotes the probability that Alice knows more than four bits in a distribution and

P_{\geq 5}

denotes the probability that Alice knows more than five bits in a distribution when the average value of

\bar{n}

is three. That is to say, the success probability of Alice to learn more bits by cheating is very small. The distribution of

\bar{n}

in G-protocol and Y-protocol also follows a Poisson distribution approximately.

Figure 1 (locating N = 10,000) indicates that a different

\bar{n}

is reached by adjusting θ and k when N is fixed. Compared with G-protocol (see Figure 2 in [12]), we find that, to achieve similar N and

\bar{n}

, the value of k ranges from 2 to 5 in our protocol, while from 5 to 10 in G-protocol. This means that we need smaller k compared with G-protocol under similar conditions (

\bar{n}

, θ and N). That is, less post-processing is required in our protocol.

3.1. Loss Tolerant

The following two reasons can show that our protocol is loss tolerance. Firstly, Bob’s bits corresponding to lost particles are all used as parts of the raw key. Therefore, Alice will not falsely declare lost particles, because Alice will not benefit from reporting a lost photon for any unsuccessful USD measurement, such as increasing the probability of conclusive measurements and knowing a larger fraction of bits than expected for a giving θ. On the contrary, Bob will obtain more information about Alice’s bits if Alice reports a lost particle for any unsuccessful USD measurement. Secondly, by flipping Bob’s bits corresponding to lost particles randomly and post-processing on the raw key, Eve can not obtain database information by measuring some lost photons.

3.2. The Third-Party Attacks

The intercept resend attack and Trojan Horse attack are two common attack strategies in quantum secure communication. In our protocol, the particles are one-way transmission, and there is no loop (circuit); therefore, there is no Trojan Horse attack. Two-point attack [15] is a specific intercept resend attack strategy aiming to attack the QKD system based on two non-orthogonal states [16]. In two-point attacks, there are two third-party eavesdroppers Eve1 and Eve2. Eve1 is located at a point near Alice’s security domain, and Eve2 at a point near Bob’s security domain. Eve1 and Eve2 can communicate with each other through a classical channel. Eve1 intercepts the quantum channel and measures every quantum state. Eve2 resends the quantum state according to the measurement result Eve1 tells him. Next, we analyze the influence of two-point attacks on user privacy and database privacy in our protocol.

(1): The influence of two-point attacks on user privacy

In our protocol, if Eve1 intercepts a particle and successfully measures it with a USD method, after Eve1 tells the result to Eve2, Eve2 resends the particle to Alice. Then, Eve1 and Eve2 will know the bit of Alice. That is, user privacy is threat. However, because Bob inserts decoy particles with x-basis and z-basis randomly in quantum sequence S, Eve1 and Eve2 has 1/3 probability or less to select correct basis (USD, x-basis or z-basis) to measure the intercepted particles successfully. In addition, the eavesdropping of Eve1 and Eve2 will be easily found with probability 2/3. They only have the probability

P_{T} = \frac{1 - cos θ}{3}

(2)

to know the corresponding bit of Alice. While in G-protocol and Y-protocol, the probability that Eve1 and Eve2 are found is 0, and the probability that Eve1 and Eve2 know the corresponding bit of Alice is

P_{T}^{G} = P_{T}^{Y} = \frac{{sin}^{2} θ}{2} .

(3)

From Figure 2, we find that the probability that Eve1 and Eve2 know Alice’s bits for different θ in our protocol is much lower than that in G-protocol and Y-protocol.

(2): The influence of two-point attacks on database privacy

In our protocol, Bob’s bits corresponding to particles that are intercepted by Eve1 without being resend by Eve2 are flipped randomly; therefore, Eve1 and Eve2 know nothing about these bits. For the particles that Eve1 intercepts and Eve2 resends, according to analysis in the influence of two-point attacks on user privacy, we know that Eve1 and Eve2 will be easily found with probability 2/3, and they only have the probability (1 − cosθ)/3 to know the corresponding bit. Therefore, it is difficult to obtain database information for Eve1 and Eve2, and their eavesdropping will be found easily.

3.3. Qubit Efficiency Comparison

To estimate the efficiency of QPQ, we define the qubit efficiency as

η = \frac{N}{\bar{n} (M + l)}

, where N denotes the final classical bits that can be generated for Bob,

\bar{n}

denotes the final classical bits that can be generated for Alice, M denotes the total coding particles in each communication, and l denotes the decoy photons to check the presence of eavesdropping in each communication.

Because

\bar{n}

= NR^k, we have

\frac{N}{\bar{n}} = \frac{1}{R^{k}}

, then

η = \frac{1}{R^{k} (M + l)}

(4)

For G-protocol,

R = \frac{{sin}^{2} θ}{2}

M = k N

and there is no eavesdropping detecting, thus

η_{G} = \frac{1}{{(\frac{{sin}^{2} θ}{2})}^{k} k N} .

(5)

For Y-protocol,

R = \frac{{sin}^{2} θ}{2}

M = 2 k N

and there is no eavesdropping detecting, thus

η_{Y} = \frac{1}{{(\frac{{sin}^{2} θ}{2})}^{k} 2 k N} .

(6)

For our protocol,

R = \frac{1 - cos θ}{2}

M = k N

, thus

η_{O u r} = \frac{1}{{(\frac{1 - cos θ}{2})}^{k} (k N + l)} .

(7)

In Table 3, we compare the qubit efficiency of G-protocol [12], Y-protocol [13] and our protocol when N = 10,000.

From Table 3, we find that our protocol has better qubit efficiency than G-protocol [12] and Y-protocol [13].

3.4. Database Security

Database security means that Alice can not get extra records in Bob’s database no matter the methods she uses. Suppose that, to obtain extra records, Alice performs more efficient measurements on particles that Bob sends to her.

As analyzed in Ref. [11], there is a measurement called minimal error probability measurement [17], which distinguishes two equally likely qubits. If Alice measures the k qubits forming an element of the final key K with the efficient measurement, she obtains the bits of K directly. By using minimal error probability measurement, the maximal chance of distinguishing the two states ρ₀ and ρ₁ correctly is P_guess = 1/2 + D(ρ₀, ρ₁)/2, where D(ρ₀, ρ₁) denotes trace distance between ρ₀ and ρ₁. In our protocol, the probability is P_guess = (

\frac{1}{2} + \frac{1}{2} {sin}^{k} θ

) at most. However, even though Alice guesses

| φ_{0} 〉

and

| φ_{1} 〉

correctly, (the probability is P_guess/3), she can infer correctly the corresponding two-bit group of Bob with 50% chance, that is, on average, Alice can infer correctly each bit of Bob with a 75% chance. Therefore, Alice can correctly guess the bit of Bob with probability

P_{g u e s s} = \frac{1}{4} (\frac{1}{2} + \frac{1}{2} {sin}^{k} θ)

(8)

at most. Obviously the probability is much less than that in G-protocol (

P_{g u e s s}^{G} = \frac{1}{2} + \frac{1}{2} {sin}^{k} θ

), which means better database security than that in G-protocol. Figure 3 shows that P_guess in our protocol is much less than that in G-protocol for a giving k = 2.

3.5. User Security

We suppose that Bob transmits a false qubit |Θ> to Alice, where |Θ> = cosβ|+> + sinβ|->. Alice obtains the conclusive result with probability (1 − cos(θ ± β))/2. By sending a fake state, Bob biases the probability of measurement results of Alice between ((1 − cos(θ + β))/2, (1 − cos(θ − β))/2) unless β = 0. Let Y = cos(θ − β) − cos(θ + β), by deducing

\frac{d Y}{d β} = 0

and

\frac{d^{2} Y}{d^{2} β}

, we can get β = π/2 when

\frac{d^{2} Y}{d^{2} β} < 0

. We construe this result as that optimal probability with which Bob knows Alice’s bits is between ((1 − cos(θ + π/2))/2, (1 − cos(θ − π/2))/2). That is, the bounds on P_b (the probability with which Bob knows Alice’s bits) is:

(1 − cos(θ + π/2))/2 < P_b < (1 − cos(θ − π/2))/2.

(9)

Figure 4 shows that when θ ∈ (0,π/2), the low bound of P_b for our protocol is smaller than that in G-protocol. The upper bound of P_b for our protocol is smaller than that in G-protocol when 0 < θ < π/4, and bigger than that in G-protocol when π/4 < θ < π/2. That is, when 0 < θ < π/4, we can achieve a better user privacy compared with G-protocol.

4. Discussion

In the above section, we have analyzed the advantages of our protocol in the aspect of less post-processing (smaller k) compared with G-protocol under similar conditions (

\bar{n}

, θ and N), in the aspect of qubit efficiency compared with G-protocol and Y-protocol for fixed N, and θ and k, in the aspect of database security and user security compared with G-protocol. In this section, we give a more comprehensive discussion focusing on security and resources for specific, optimal sets of parameters.

From Table 4, we find that when

\bar{n}

is fixed, G-protocol, Y-protocol and our protocol have the same P₀. When N and

\bar{n}

are given , for a specific k, P_b in our protocol is much lower than that in G-protocol and is close to that in Y-protocol, which means that our protocol shows much higher user security than G-protocol and the user security of our protocol is close to Y-protocol. Furthermore, in the same condition, our protocol always needs bigger θ than that in G-protocol and Y-protocol. Because a very small θ might make its realization technically difficult [12], our protocol is easier to realize technically than G-protocol and Y-protocol.

Table 5 shows that, for a given N and

\bar{n}

, when three protocols (Y-protocol, G-protocol and our protocol) achieve similar θ, our protocol shows higher qubit efficiency than Y-protocol and better user privacy than G-protocol.

In a practical condition, channel noise is inevitable, which will cause errors in the obvious key shared between Alice and Bob. Therefore, error correction is necessary. We can use the method proposed in Ref. [18] to correct errors. Suppose the kN-bit raw oblivious key is denoted as

O^{R} =

O_{1}^{R} O_{2}^{R} ... O_{k N}^{R}

, the final obvious key after dilution is denoted as .

O^{F} =

O_{1}^{F} O_{2}^{F} ... O_{N}^{F}

. Here,

O_{i}^{F} =

\oplus_{j = 0}^{k - 1} O_{i + j N}^{R}

1 \leq i \leq N

, and

\oplus

denotes the addition module 2. Alice and Bob select a [k, s] error-correcting code [19] which uses k bits codeword to encode s bits word using generator matrix G and can correct one codeword error bits with error-correcting function. Bob chooses a bits word M = (m₁, m₂, …, m_s) and obtains the corresponding bits codeword W = (w₁, w₂, …, w_k) by calculating W = M·G. Then, Bob encrypts W with {

O_{i + j N}^{R}

} as the key, by using a one-time pad, and sends the ciphertext c to Alice. If Alice knows all the k bits {

O_{i + j N}^{R}

}, Alice decrypts c with {

O_{i + j N}^{R}

} and obtains a k-bit codeword W’. Alice corrects the error in W’ and obtains W. By adding the k bits in W bitwise, Alice knows

O_{i}^{F}

. If Alice does not know all the k bits in {

O_{i + j N}^{R}

}, she labels

O_{i}^{F}

= ?. Bob also adds the k bits in W bitwise to obtain his corresponding bit

O_{i}^{F}

5. Conclusions

We put forward a novel QPQ protocol based on two non-orthogonal states and unambiguous state discrimination (USD) measurement. Our protocol is loss tolerant. Compared with existing QPQ protocols, we have the following differences:

(1): We analyze the influence of two-point attacks by a third party on user privacy and database privacy in our protocol. By comparing, we find that the probability that Eve1 and Eve2 know Alice’s bits for different θ in our protocol is much lower than that in G-protocol and Y-protocol, which means that our protocol has a stronger ability to resist external attacks than G-protocol and Y-protocol.
(2): Smaller k is required to achieve similar conditions (n, θ and N) than G-protocol and Y-protocol, which means less post-processing and higher qubit efficiency.
(3): For a given N and $\bar{n}$ , our protocol shows much higher user security than G-protocol and the user security of our protocol is close to Y-protocol. However, in the same condition, our protocol always needs bigger θ than that in G-protocol and Y-protocol. Because a very small θ might make its realization technically difficult [12], our protocol is easier to realize technically than G-protocol and Y-protocol.

However, because of eavesdropping detection in Step (2), our protocol requires quantum memory on the Alice side. The use of quantum memory will bring our protocol difficulties in practicality and realizability using current technology.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant Nos. 61402058, 61572086), the Fund for Middle and Young Academic Leaders of Chengdu University of Information Technology (Grant No. J201511), the Science and Technology Support Project of Sichuan Province of China (Grant No. 2013GZX0137), and the Fund for Young Persons Project of Sichuan Province of China (Grant No. 12ZB017).

Author Contributions

All of the authors read and approved the final manuscript. Yan Chang and Shibin Zhang conceived and designed the protocol; Yan Chang and Guihua Han performed the experiments; Yan Chang analyzed the data; Yan Chang, Zhiwei Sheng, Lili Yan and Jinxin Xiong contributed modification of paper; Yan Chang wrote the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

Chor, B.; Goldreich, O.; Kushilevitz, E.; Sudan, M. Private Information Retrieval. J. ACM 1998, 45, 965–981. [Google Scholar] [CrossRef]
Gertner, Y.; Ishai, Y.; Kushilevitz, E.; Malkin, T. Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci. 2000, 60, 592–629. [Google Scholar] [CrossRef]
Lo, H.-K. Insecurity of quantum secure. Phys. Rev. A 1997, 56, 1154–1162. [Google Scholar] [CrossRef]
Bennett, C.-H.; Brassard, G.; Crlpeau, C.; Skubiszewska, M.H. Practical quantum oblivious transfer. Adv. Cryptol. 1992, 576, 351–366. [Google Scholar]
Brassard, G.; Crepeau, C.; Jozsa, R.; Langlois, D. A quantum bit commitment scheme provably unbreakable by both parties. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, USA, 3–5 November 1993; Volume 362.
Giovannetti, V.; Lloyd, S.; Maccone, L. Quantum private queries. Phys. Rev. Lett. 2008, 100, 230502. [Google Scholar] [CrossRef]
Martini, F.D.; Giovannetti, V.; Lloyd, S.; Maccone, L.; Nagali, E.; Sansoni, L.; Sciarrino, F. Experimental quantum private queries with linear optics. Phys. Rev. A 2009, 80, 010302. [Google Scholar] [CrossRef]
Giovannetti, V.; Lloyd, S.; Maccone, L. Quantum private queries: Security analysis. IEEE Trans. Inf. Theory 2010, 7, 3465–3477. [Google Scholar] [CrossRef]
Olejnik, L. Secure quantum private information retrieval using phase-encoded queries. Phys. Rev. A 2011, 84, 022313. [Google Scholar] [CrossRef]
Scarani, V.; Acin, A.; Ribordy, G.; Gisin, N. Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations. Phys. Rev. Lett. 2004, 92, 057901. [Google Scholar] [CrossRef] [PubMed]
Jakobi, M.; Simon, C.; Gisin, N.; Bancal, J.D.; Branciard, C.; Walenta, N.; Zbinden, H. Practical private database queries based on a quantum-key-distribution protocol. Phys. Rev. A 2011, 83, 022301. [Google Scholar] [CrossRef]
Gao, F.; Liu, B.; Wen, Q.Y. Flexible quantum private queries based on quantum key distribution. Opt. Exp. 2012, 20, 17411–17420. [Google Scholar] [CrossRef] [PubMed]
Yang, Y.-G.; Sun, S.J.; Xu, P.; Tian, J. Flexible protocol for quantum private query based on B92 protocol. Quant. Inf. Process. 2014, 13, 805–813. [Google Scholar] [CrossRef]
Raynal, P. Unambiguous State Discrimination of two density matrices in Quantum Information Theory. 2006; arXiv: quant-ph/0611133. [Google Scholar]
Yang, L.; Wu, L.-A. Two-point attack on the two nonorthogonal states QKD protocol over a fiber optic channel. 2005; arXiv: quant-ph/0310080. [Google Scholar]
Bennett, C.-H. Quantum Cryptography Using Any Two Nonorthogonal States. Phys. Rev. Lett. 1992, 68. [Google Scholar] [CrossRef]
Helstrom, C.W. Quantum Detection and Estimation Theory; Academic Press: New York, NY, USA, 1976. [Google Scholar]
Gao, F.; Liu, B.; Huang, W.; Wen, Q.-Y. Postprocessing of the oblivious key in Quantum Private Query. IEEE J. Sel. Top. Quant. Electron. 2014, 21, 6600111. [Google Scholar]
MacWilliams, F.J.; Sloane, N.J.A. The Theory of Error-Correcting Codes; North-Holland Publishing Company: Amsterdam, The Netherlands, 1977. [Google Scholar]

Figure 1. When N = 10,000,

\bar{n}

<< N can be achieved.

Figure 1. When N = 10,000,

\bar{n}

<< N can be achieved.

Figure 2. The probabilities that Eve1 and Eve2 know Alice’s bits for different θ in our protocol, G-protocol and Y-protocol. The solid line represents the probabilities for G-protocol (P_T^G) and Y-protocol (P_T^Y); the star line represents the probability for our protocol (P_T).

Figure 3. Comparison of probability with which Alice correctly guesses the bit of Bob for different θ between our protocol and G-protocol when k = 2. The solid line represents P_guess for G-protocol; the dotted line represents P_guess for our protocol.

Figure 4. Comparisons of probability with which Bob knowing Alice’s bits for different θ between our protocol and G-protocol. The star line represents P_b for G-protocol; the dotted line represents the upper bound of P_b for our protocol; the solid line represents the lower bound of P_b for our protocol.

Table 1. The case that Alice honestly reports all lost particles.

**Table 1.** The case that Alice honestly reports all lost particles.
Order Number	1		2		3		4		5		6		7		8		9
The states Bob prepares	$\| φ_{0} 〉$		$\| φ_{1} 〉$		$\| φ_{1} 〉$		$\| φ_{1} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$
Bob’s original bits	0	1	1	0	1	1	1	0	0	1	0	1	0	0	0	1	0	1
Lost particles and Alice’s measuring result	#	*	$\| φ_{1} 〉$	*	$\| φ_{1} 〉$	*	?	*	?	*	$\| φ_{0} 〉$	*	?	*	?	*	#	*
Alice’s bits			1		1						0
Bob’s final bits	0	1	1	0	1	1	1	0	0	1	0	1	0	0	0	1	1	1

Notes:

| φ_{0} 〉

and

| φ_{1} 〉

denotes non-orthogonal states in Equation (1).

Table 2. The case that Alice dishonestly reports the lost particles.

**Table 2.** The case that Alice dishonestly reports the lost particles.
Order Number	1		2		3		4		5		6		7		8		9
The states Bob prepares	$\| φ_{0} 〉$		$\| φ_{1} 〉$		$\| φ_{1} 〉$		$\| φ_{1} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$		$\| φ_{0} 〉$
Bob’s original bits	0	1	1	0	1	1	1	0	0	1	0	1	0	0	0	1	0	1
Lost particles and Alice’s measuring result	#	*	$\| φ_{1} 〉$	*	$\| φ_{1} 〉$	*	$	*	?	*	$\| φ_{0} 〉$	*	$	*	$	*	#	*
Alice’s bits			1		1						0
Bob’s final bits	0	1	1	0	1	1	0	0	0	1	0	1	1	0	0	1	1	1

Table 3. Examples of qubit efficiency comparison of G-protocol, Y-protocol and our protocol when N = 10,000 and l = 15,000.

**Table 3.** Examples of qubit efficiency comparison of G-protocol, Y-protocol and our protocol when N = 10,000 and l = 15,000.
θ, k	θ = 0.15, k = 2	θ = 0.25, k = 2	θ = 0.36, k = 3	θ = 0.4, k = 3	θ = 0.57, k = 4	θ = 0.62, k = 4
G-protocol	0.4010	0.0534	0.1395	0.0765	0.0556	0.0308
Y-protocol	0.2005	0.0267	0.0698	0.0382	0.0278	0.0154
Our protocol	0.9064	0.1183	0.6749	0.3614	0.4656	0.2424

Table 4. Examples of P₀, P_b, θ and M + l comparison of G-protocol, Y-protocol and our protocol for a given N and

\bar{n}

**Table 4.** Examples of P₀, P_b, θ and M + l comparison of G-protocol, Y-protocol and our protocol for a given N and $\bar{n}$ .
a. N = 10⁴, $\bar{n}$ = 3 and k = 3
Protocol	P₀	P_b	θ	M + l
Y-protocol	0.05	0.32~0.68	0.375	6 × 10⁴
G-protocol	0.05	0.98	0.375	3 × 10⁴
Our-protocol	0.05	0.25~0.75	0.5234	4.5 × 10⁴
b. N = 10⁵, $\bar{n}$ = 3 and k = 3
Protocol	P₀	P_b	θ	M + l
Y-protocol	0.05	0.38~0.62	0.252	6 × 10⁵
G-protocol	0.05	0.98	0.252	3 × 10⁵
Our-protocol	0.05	0.33~0.67	0.3544	4.5 × 10⁵
c. N = 10⁵, $\bar{n}$ = 3 and k = 4
Protocol	P₀	P_b	θ	M + l
Y-protocol	0.05	0.31~0.69	0.395	8 × 10⁵
G-protocol	0.05	0.96	0.395	4 × 10⁵
Our-protocol	0.05	0.24~0.76	0.5510	5.5 × 10⁵

Table 5. Examples of P₀, P_b, θ and M + l comparison of G-protocol, Y-protocol and our protocol for N = 10⁴ and a given

\bar{n}

**Table 5.** Examples of P₀, P_b, θ and M + l comparison of G-protocol, Y-protocol and our protocol for N = 10⁴ and a given $\bar{n}$ .
a. $\bar{n}$ = 3
Protocol	P₀	P_b	θ	k	M + l
Y-protocol	0.05	0.24~0.76	0.539	4	8 × 10⁴
G-protocol	0.05	0.93	0.539	4	4 × 10⁴
Our-protocol	0.05	0.25~0.75	0.5234	3	4.5 × 10⁴
b. $\bar{n}$ = 5
Protocol	P₀	P_b	θ	k	M + l
Y-protocol	0.0067	0.23~0.77	0.579	4	8 × 10⁴
G-protocol	0.0067	0.92	0.579	4	4 × 10⁴
Our-protocol	0.0067	0.23~0.77	0.5712	3	4.5 × 10⁴

© 2016 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC-BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Chang, Y.; Zhang, S.; Han, G.; Sheng, Z.; Yan, L.; Xiong, J. Quantum Private Query Protocol Based on Two Non-Orthogonal States. Entropy 2016, 18, 163. https://doi.org/10.3390/e18050163

AMA Style

Chang Y, Zhang S, Han G, Sheng Z, Yan L, Xiong J. Quantum Private Query Protocol Based on Two Non-Orthogonal States. Entropy. 2016; 18(5):163. https://doi.org/10.3390/e18050163

Chicago/Turabian Style

Chang, Yan, Shibin Zhang, Guihua Han, Zhiwei Sheng, Lili Yan, and Jinxin Xiong. 2016. "Quantum Private Query Protocol Based on Two Non-Orthogonal States" Entropy 18, no. 5: 163. https://doi.org/10.3390/e18050163

APA Style

Chang, Y., Zhang, S., Han, G., Sheng, Z., Yan, L., & Xiong, J. (2016). Quantum Private Query Protocol Based on Two Non-Orthogonal States. Entropy, 18(5), 163. https://doi.org/10.3390/e18050163

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu