OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 20, Iss. 16 — Jul. 30, 2012
  • pp: 17411–17420

Optics InfoBase > Optics Express > Volume 20 > Issue 16 > Page 17411

« Show journal navigation

Flexible quantum private queries based on quantum key distribution

Fei Gao, Bin Liu, Qiao-Yan Wen, and Hui Chen  »View Author Affiliations


Optics Express, Vol. 20, Issue 16, pp. 17411-17420 (2012)
http://dx.doi.org/10.1364/OE.20.017411


View Full Text Article

Acrobat PDF (1440 KB)


Advanced Search

Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

By adding a parameter θ in M. Jakobi et al’s protocol [Phys. Rev. A 83, 022301 (2011)], we present a flexible quantum-key-distribution-based protocol for quantum private queries. We show that, by adjusting the value of θ, the average number of the key bits Alice obtains can be located on any fixed value the users wanted for any database size. And the parameter k is generally smaller (even k = 1 can be achieved) when θ < π/4, which implies lower complexity of both quantum and classical communications. Furthermore, the users can choose a smaller θ to get better database security, or a larger θ to obtain a lower probability with which Bob can correctly guess the address of Alice’s query.

© 2012 OSA

1. Introduction

Cryptography is the approach to protect data secrecy in public environment. As we know, the security of most classical cryptosystems is based on the assumption of computational complexity and might be susceptible to the strong ability of quantum computation [1

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on the Foundations of Computer Science , (Santa Fe, New Mexico, 1994), 124–134. [CrossRef]

, 2

L. K. Grover, “A fast quantum mechanical algorithm for database search,” in 28th Annual ACM Symposium on Theory of Computing , (New York, 1996), 212–219.

]. Fortunately, this difficulty can be overcome by quantum cryptography [3

C.H. Bennett and G. Brassard, “Quantum cryptography: public-key distribution and coin tossing,” in IEEE Int. Conf. on Computers, Systems, and Signal Processing , (Bangalore, 1984), 175–179.

, 4

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002). [CrossRef]

], where the security is assured by physical principles. With the advantage of higher security, quantum cryptography has attracted a great deal of attention now.

In some cryptographic communications, we need not only protect the security of the transmitted message against eavesdropping from an outside adversary, but also the communicators’ individual privacy against each other. Private information retrieval (PIR) [5

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM 45, 965–981 (1998). [CrossRef]

] and symmetrically private information retrieval (SPIR) [6

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci. 60, 592–629 (2000). [CrossRef]

] are protocols for such circumstance. Both of them deal with the problem of private user queries to a database, where Alice wants to obtain one item secretly from Bob’s database. Generally it is assumed that Alice knows the address of this item in the database and, for simplicity, the content of it is just a bit. In a PIR protocol the aim is that Alice gets the item she wanted correctly and, at the same time, Bob does not know which item Alice has obtained. SPIR protects not only Alice’s privacy but also the security of Bob’s database, that is, Alice cannot get other items except the one she wanted in the database. However, the task of SPIR cannot be implemented ideally [7

H. K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A 56, 1154–1162 (1997). [CrossRef]

]. More practically, it is generally required that Alice can elicit sufficiently little content of the database, or at least cannot get the whole database by dishonest operations.

Quantum Private Queries (QPQ) is the quantum scheme for SPIR problem. In 2008 V. Giovannetti et al proposed the first QPQ protocol (GLM protocol) [8

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett. 100, 230502 (2008). [CrossRef] [PubMed]

], where the database is represented by a unitary operation (i.e. oracle operation) and it is performed on the coming query states. In this protocol two query states are needed. One is for getting the wanted information from the database and the other, a superposition state, for checking potential attack from Bob. GLM protocol is cheat sensitive for Alice’s privacy: if Bob tries to obtain information on the query he would be discovered by Alice with a certain probability. It ensures perfect data privacy of the database: Alice can obtain at most two items if she perform dishonest queries. Compared with previous schemes GLM protocol displays an exponential reduction in both communication complexity and running-time computational complexity. Furthermore, the security of GLM protocol was deeply analyzed [9

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory 56, 3465–3477 (2010). [CrossRef]

] and a proof-of-principle experimental realization of it was implemented [10

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A 80, 010302 (2009). [CrossRef]

].

Recently L. Olejnik presented a quantum PIR protocol (O-protocol) [11

L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A 84, 022313 (2011). [CrossRef]

], which is similar to GLM protocol in terms of form. In this protocol the oracle operation and the coding method are subtly selected so that one query state can achieve two aims simultaneously, i.e. obtaining the expected information and checking Bob’s potential attack. Here Alice’s checking is not a real-time one (like that in GLM protocol) because only one query is executed, but Bob’s answer may be wrong if he tries to obtain Alice’s privacy, which will leave the trace of his attack and be discovered by Alice later. Moreover, O-protocol can reduce communication complexity further.

Though the above two protocols exhibit significant advantages in theory, they are difficult to implement because when large database is concerned the dimension of the oracle operation will be very high. To solve this problem, M. Jakobi et al gave a new QPQ protocol (J-protocol) based on quantum key distribution (QKD) [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

], which is the first practical QPQ protocol and quite different from the previous ones. In this protocol SARG04 QKD protocol [13

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett. 92, 057901 (2004). [CrossRef] [PubMed]

] is utilized to distribute asymmetric key between Alice and Bob, and the whole database is encrypted by the key. Because Alice only knows some bits of the key, she can obtain limited items in the database. Compared with GLM protocol and O-protocol, J-protocol can be easily generalized to large database and it is loss tolerant. Furthermore, it is difficult for Bob to obtain the address of Alice’s query even though he tries his best to attack. In this sense, Alice’s privacy is protected better in J-protocol. Therefore, this new model of QPQ, i.e. QKD-based QPQ, is very attractive and will become a studying point in the future.

In this paper, inspired by the work of M. Jakobi et al [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

], we propose a new QPQ protocol based on QKD, which can be seen as a generalization of J-protocol. We show that our protocol preserves all the features of J-protocol and the most importantly, is significantly more flexible for implementation. In particular, by adjusting the parameters the expected value of the key bits Alice obtains can be located on a certain number for databases of any size. And it also displays the advantages of lower communication complexity and higher security degree when suitable parameters are selected.

The rest of this paper is organized as follows. In Sec. II we describe our protocol in detail and show its features especially on the flexibility. The security of our protocol is analyzed in Sec. III and Sec.IV is our conclusion.

2. QPQ protocol based on QKD

Without loss of generality, suppose there are N items in Bob’s database, and Alice has bought one of them and wants to obtain it secretly. The two users can execute the following protocol.

2.1. The protocol

  1. Bob prepares a long sequence of photons which are randomly in one of the states {|0〉, |1〉, |0′〉, |1′〉}, and sends them to Alice. Here
    | 0′〉=cosθ |0〉+sinθ |1〉, | 1′〉=sinθ |0〉−cosθ |1〉,
    (1)
    and |0〉 and |1〉 represent bit 0, while |0′〉 and |1′〉 code for bit 1. The parameter θ ∈ (0, π/2) can be selected continuously according to particular situations, which will be demonstrated below.
  2. Alice randomly measures each received photon in the basis B = {|0〉, |1〉} or the basis B′ = {|0′〉, |1′〉}. Obviously this measurement does not allow her to infer the value of the bit sent by Bob.
  3. Alice announces in which instances she has successfully detected the qubit. The bits carried by the lost photons are disregarded. Note that Alice cannot cheat by lying in this step (e.g. announcing a photon lost when she gets an unwanted measurement result). This is because till now Alice has no information about the sent bits and she cannot obtain any benefit by such a lie. Therefore, this protocol is completely loss tolerant, which is similar to that in J-protocol.
  4. For each qubit that Alice has successfully measured, Bob announces one bit 0 or 1, where 0 represents this qubit is originally in the state |0〉 or |0′〉, while 1 implies the qubit is |1〉 or |1′〉.
  5. Alice interprets her measurement results in step 2. According to her measurement result and Bob’s declaration, Alice can obtain the sent bit with a certain probability. This process is similar to that in B92 QKD protocol [14

    C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett. 68, 3121–3124 (1992). [CrossRef] [PubMed]

    ]. For example, if Bob’s declaration is 0 and Alice’s measurement result is |1〉 (|1′〉), she knows the qubit must be in the state |0′〉 (|0〉) before the measurement and then the sent bit is 1 (0). As a result, with Bob’s declaration in step 4, Alice’s measurements will yield p = (sin2θ)/2 of conclusive results and 1 − p of inconclusive ones. Both conclusive and inconclusive results are stored. by this way Alice and Bob now share a raw key Kr which is known completely to Bob and partly to Alice (she knows p = (sin2θ)/2 of the whole).
  6. Two users execute postprocessing to the key so that Alice’s known bits in the key are reduced to 1 bit or a little more. Without loss of generality, suppose the length of the raw key shared between Alice and Bob is kN. Here the natural number k is a parameter and we will discuss its value later. Alice and Bob cut the raw key into k substrings of length N, and add these k strings bitwise, obtaining the final key K with length N. This process is the same as that in J-protocol (please see Fig.1 in Ref. [12

    M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

    ]). Till now, Bob knows the whole key K and Alice generally knows only several bits in it. But if Alice is left with no known bit after this step, the protocol has to be restarted. As we will show later, if suitable parameters are selected this event happens only with small probability.
  7. Bob encrypts his database and Alice obtains the item she wanted with one of her known bits in K. In particular, suppose Alice knows the jth bit Kj and wants the ith item (bit) of the database Xi. She declares the number s = j − i. Then Bob shifts K by s and using the obtained key K′ to encrypt his database in the manner of one-time pad. Thus Xi is encrypted by Kj and consequently can be correctly obtained by Alice when she gets the encrypted database.

2.2. The features of our protocol

It is not difficult to see that our protocol is actually a generalization of J-protocol. When θ = π/4 our protocol becomes J-protocol, where the carrier states are { |0〉, |1〉, |+〉= 1 2 ( |0〉+ |1〉), |−〉= 1 2 ( |0〉− |1〉)}. In fact the idea of using such nonothogonal states as that in our protocol was originally proposed by V. Scarani et al in SARG04 QKD protocol [13

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett. 92, 057901 (2004). [CrossRef] [PubMed]

]. The difference between the two applications of these states is as follows. In SARG04 protocol, to persue high efficiency of QKD, unambiguous state discrimination (USD) is used to measure the qubits and π/4 is the optimal value of θ (using a θ other than π/4 seems needless because it brings no benefits in theory but reduces the QKD efficiency). On the contrary, in our protocol we might expect that Alice gets less bits in the raw key. Therefore, common projective measurements are enough and, as we will show, a smaller θ generally displays some better features than π/4. Strictly speaking, our protocol is based on the variant of SARG04 protocol. Therefore, the features of J-protocol are still hold in ours. Furthermore, because θ can be selected continuously in (0, π/2) our protocol is more flexible and even exhibits advantages in communication complexity and security. In the following, by making the comparison to J-protocol, we discuss the features of our protocol.

On the one hand, our protocol has the same features as J-protocol in the following aspects.

  1. Different from BB84-based QPQ, our protocol can stand against the quantum memory attack by Alice. If Alice stores a received photon and measures it after Bob’s declaration in step 4, she cannot obtain this bit because she still has to discriminate nonorthogonal states.
  2. Our protocol is loss tolerant. As discussed above, Alice has no need to tell a lie on whether one photon is lost (especially saying that a photon she has received disappeared) because before Bob’s declaration she cannot get any information about the corresponding bit. Note that after Bob’s declaration Alice’s measurement is just like that in B92 protocol [14

    C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett. 68, 3121–3124 (1992). [CrossRef] [PubMed]

    ]. We can also directly use B92 protocol to perform QPQ (i.e. the carrier qubit is randomly in two states, |0〉 or |0′〉), where Bob’s declaration is not necessary anymore. But in this condition Alice will obtain some information about the sent bit after her measurement. To elicit more bits in the raw key, for example, Alice lies that the photon on which she gets a inconclusive result is lost. So, the B92-based QPQ is not so robust against channel-loss attack.
  3. Our protocol is practical and can be easily generalized to huge-database condition. This is because Alice and Bob just execute a simple QKD protocol and no high-dimension oracle operation [8

    V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett. 100, 230502 (2008). [CrossRef] [PubMed]

    , 11

    L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A 84, 022313 (2011). [CrossRef]

    ] is needed.

On the other hand, our protocol has some peculiar merits. For example, it is much more flexible for practical application, and greatly saves both quantum and classical communication. Furthermore, it also exhibits some advantages in security. In the following we discuss these advantages in detail.

As in J-protocol, after adding the substrings in step 6, Alice will on average know n̄ = Npk (p = (sin2θ)/2) bits of the final key K, where the number n follows approximately a Poisson distribution. Here we only consider the bits which are obtained from the conclusive results by honest measurements. The situation where Alice uses a delayed-choice unambiguous measurement will be discussed in Sec.III, where Alice will get almost perfect information about every raw bit for θ approaching π/2. And the probability that she does not know any bits at all and that the protocol must be restarted is P0 = (1 − pk)N. Now let us see what will happens when θ < π/4. Without loss of generality, suppose p = (sin2θ)/2 = 0.15. In this condition we can ensure both n̄ ≪ N and small P0, which implies a successful execution of QPQ [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

], by choosing an appropriate value of k (see Table 1). It can be seen that fewer substrings (i.e. a smaller k) are needed than that in J-protocol, which means the number of transmitted qubits are greatly reduced. For example, when N=50000 only 5 substrings are needed, while in J-protocol k is 7 to achieve similar n̄ and P0. Thus at least 2N = 105 qubits (not including the lost ones in the channel) are saved in our protocol. In fact, in our protocol k = 1 is even feasible for not so large database size N (see Tables 2 and 3). This is obviously a significant improvement with the comparison to J-protocol. Note that the condition k = 1 will not compromise the cheat-sensitive character of the QPQ protocol, which we will discuss in the next section.

Table 1  Example of possible choice of k and the values P0 and n̄ for different database sizes N (p = 0.15).
N1035 × 1031045 × 104105106
k344556
n̄3.382.535.063.797.5911.39
P00.0340.0800.0060.0225 × 10−410−5
Table 2  For different N, θ can be selected so that k = 1 and n̄ = 3.
N125010020050010005000
p0.250.060.030.0150.0060.0036×10−4
P00.0320.0450.0480.0490.0490.0500.050
θ0.785( π4)0.3540.2470.1740.1100.0780.035
Table 3  For different N, θ can be selected so that k = 1 and n̄ = 5.
N205010020050010005000
p0.250.10.050.0250.010.0050.001
P00.0030.0050.0050.0060.0060.0060.006
θ0.785( π4)0.4640.3220.2260.1420.1000.045

Furthermore, in our protocol the average number of the key bits Alice obtains n̄ can be located on any fixed value the users wanted for any database size N. Let us recall the results in J-protocol first (see Table I in Ref. [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

], which is similar to Table 1 here). When N = 50000 we have almost no choice but letting k = 7 and n̄ = 3.05 in J-protocol. This is because n̄ will be 12.21 if k = 6 and 0.76 (P0 = 0.466) if k = 8, which are not so suitable for the aim of QPQ. The similar result exists for other N. But in our protocol the condition will be changed. By selecting different values of θ we can set n̄ equals an expected value for any N. Tables 2 and 3 are the results with k = 1 when the wanted n̄ is 3 and 5, respectively.

It can be see that if we pursue k = 1, which means the optimal communication complexity in our protocol, θ will be very small for large N. This might make its realization technically difficult. Therefore, k > 1 is needed when N is large. In this condition we can also locate n̄ on an expected value for any N by selecting suitable θ and k. For example, even though θ > 0.2 is required we can also achieve n̄ = 3 for any N by simply adjusting k (see Table 4).

Table 4  For different N, θ (> 0.2) can be selected so that n̄ = 3 and P0 ≈ 0.05.
N1035 × 1031045 × 104105106
k223334
θ0.3370.2230.3750.2840.2520.293

Figure 1, where we locate n̄ = 3, is a general illustration about the flexibility of our protocol. It is shown that, we can achieve n̄ = 3 by simply selecting a relatively small θ, as long as it is feasible in the realization, and a suitable k for any N.

Fig. 1 How to achieve n̄ = 3 for any N. Similar result also exists when we pursue n̄ other than 3.

In fact, except for the above example for n̄ = 3, n̄ can be set on any expected number smaller than N in our protocol. Sometimes we may want that Alice obtains key bits a litter more. On the one hand, as pointed in Ref. [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

], Alice can use some key bits to get some other items in the database and then use them to detect Bob’s potential attack. On the other hand, two users can also compare some key bits publicly (as in BB84) to check the error rate in the key. Obviously in a practical QPQ protocol Alice’s final key bits may be different from Bob’s, which is caused by an outside eavesdropper’s attack or channel noise. Now we still have no effective way to perform error correction or privacy amplification to achieve high correctness of the final key in such a special QKD protocol (that is, Alice only gets parts of the whole key and Bob does not know which bits are obtained by Alice). Though the above comparison cannot ensure Alice’s key bit, corresponding to the item she wants, is determinately the same as Bob’s one, the error rate still implies the correctness of the shared key bit to some extent. For example, if the error rate is 1/10 Alice knows the key bit, which will be used to get the wanted item in the database, equals to Bob’s with a high probability. On the contrary, if the error rate is higher than a threshold she will discard this result. Figure 2 shows that in our protocol different n̄ can be achieved for a fixed N by adjusting θ and k.

Fig. 2 Any n̄ ≪ N can be achieved for N = 10000.

Furthermore, our protocol also saves classical communication. In our protocol Bob only needs to send 1 bit, i.e. 0 or 1, to Alice for a qubit in step 4, while 2 bits are needed in J-protocol. In addition, our protocol exhibits some advantages in security, which will be demonstrated in the next section.

3. Security analysis

Now we consider the security of our protocol. Because it is actually a generalization of J-protocol, where θ = π/4, the analysis in Ref. [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

] can be adapted here directly. It is not difficult to imagine that our protocol can also ensure the security of the database and the privacy of the user. In the following we focus on how the security degree changes when θ ≠ π/4 in our protocol.

3.1. Database security

If Alice is dishonest and she wants to obtain more items in Bob’s database, she has to try to obtain more key bits in the raw key Kr. To this aim Alice can store the qubits received from Bob and take more effective measurements on them after Bob’s declaration in step 4.

Let us consider the simple measurement for Alice first, i.e. individual one for each qubit she received. For example, if Bob said a qubit is in one of the states {|0〉, |0′〉} by declaring 0, Alice performs the optimal unambiguous state discrimination (USD) measurement [15

P. Raynal, “Unambiguous State Discrimination of two density matrices in Quantum Information Theory,” e-print arXiv:quant-ph/0611133.

, 16

U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A 71, 050301 (2005). [CrossRef]

] to distinguish which state the qubit is in. The success probability of this USD measurement is bounded by 1 − F(ρ0, ρ1), where F(ρ0, ρ1) is the fidelity between the two states to be discriminated. So in our protocol this probability is pUSD = 1 − 〈0|0′〉 = 1 − cosθ. It can be seen that, the advantage Alice obtains by USD measurement is negligible compared with the legal projective one, where the probability is p = (sin2θ)/2, especially when θ is small (see Fig. 3). For example, when θ = 0.284, N = 50000 and k = 3 (see Table 4), Alice can get n̄USD = 50000 × (1 − cos0.284)3 = 3.21 bits of the key by USD measurement, which is just a little more than the value by projective one, i.e. n̄ = 50000×[(sin0.284)2/2]3 = 3.02. Note that this implies an improvement compared to J-protocol, where n̄USD = 9.3 in the same situation, i.e. pursuing n̄ = 3.

Fig. 3 Comparison between Alice’s success probability by USD measurement and projective one on a qubit. The dashed line represents the result for USD measurement and the solid line is for projective one.

As analyzed in Ref. [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

], Alice can also perform joint measurement on the k qubits which contribute to an element of the final key. By this means she wants to obtain the bit value of the final key directly without distinguishing the individual bit values of the raw key. In this condition two kinds of measurements can be used by Alice. One is Helstrom’s minimal error-probability measurement, i.e., the measurement that distinguishes two quantum states with the highest information gain [17

C. A. Fuchs, “Distinguishability and Accessible Information in Quantum Theory,” e-print arXiv:quant-ph/9601020.

, 18

C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, New York, 1976).

]. To distinguish two equally likely quantum states ρ0 and ρ1, the probability to guess the state correctly is bounded by p guess= 12+ 12D ( ρ0, ρ1), where D(ρ0, ρ1) is the trace distance between ρ0 and ρ1. In our protocol, therefore, Alice can correctly guess a final key bit with the probability at most p guess= 12+ 12 sinkθ. Obviously when is θ small this probability is close to 1/2 (a random guess). The other measurement Alice can use is USD measurement. In this condition the success probability of unambiguously discriminating the two k-qubit mixed states corresponding to odd and even parity can be obtained, which declines rapidly with k (see Fig. 4). In Fig. 4 the probabilities that Alice can get the final key bits by joint USD are depicted for different values of θ, where we can see that when θ is small Alice’s advantage by joint USD is distinctly decreased.

Fig. 4 Alice’s success probabilities to obtain the final key bits by joint USD measurement for different θ. Among them the line denoted as θ = π/4 is the result of J-protocol. It can be seen that when θ is small, Alice will get less bits in the final key, which implies a higher security degree for the database under this kind of attack.

To sum up, if θ < π/4 is chosen in our protocol it exhibits an obvious improvement compared to J-protocol in terms of the database security.

3.2. User privacy

In QPQ protocols, the user privacy is pursued in the manner of cheat-sensitive [8

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett. 100, 230502 (2008). [CrossRef] [PubMed]

, 11

L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A 84, 022313 (2011). [CrossRef]

, 12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

]. That is, Bob will run the risk of being discovered if he tries to obtain the address queried by Alice. In GLM protocol such a dishonest Bob will inevitably send unexpected answer to Alice and then be discovered with a certain probability. While in O-protocol and J-protocol dishonest Bob might send wrong answer to Alice, which will also be detected by Alice at a later time.

Our protocol is also cheat sensitive for user privacy in the sense that Bob cannot simultaneously obtain the query address and give right answer for the query deterministically. The reason is the same as that in Ref.[12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

]. If dishonest Bob, by sending fake states or performing special measurements, can get both the conclusiveness of one of Alice’s elements of the raw key and the corresponding value of this key bit, he knows the exact measurement basis chosen by Alice. Thus, Bob knows Alice’s choice once she measured the qubit randomly in one of two bases, which implies superluminal communication. Therefore, the security of user privacy in our protocol is assured by the no-signaling principle.

In the following we briefly discuss the probability with which Bob can obtain the conclusiveness of any of Alice’s bits in the raw key, and demonstrate the relation between this probability and the value of θ. Similar to the analysis in Ref. [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

], Bob can get the conclusiveness of Alice’s one bit with the optimal probability by sending |0″〉 (|1″〉) and announcing 1 (0) in step 4. Here
| 0″〉=cos ( θ/2) |0〉+sin ( θ/2) |1〉, | 1″〉=sin ( θ/2) |0〉−cos ( θ/2) |1〉.
(2)
Thus Bob knows that Alice will get conclusive result on this qubit with the probability pc = cos2(θ/2). If Bob expects that Alice gets inconclusive result on one qubit, he just sends |0″〉 (|1″〉) and announcing 0 (1) in step 4. By this method the probability with which Alice gets conclusive result equals pi = 1 − pc = sin2(θ/2). Figure 5 demonstrates the relation between pc and θ. It can be seen that a smaller θ implies a higher probability with which Bob can predict Alice’s conclusive bits. As analyzed above, we are inclined to use a small θ ∈ (0, π/4) to achieve its advantages in communication complexity and security degree of the database. In this condition Bob generally can obtain the address of Alice’s query with relatively higher probability. But this does not decrease Alice’s privacy in the sense that it is still cheat sensitive. This is because Bob will inevitably lose the knowledge about the value of the key bit when he tries to obtain its conclusiveness, which is the same as that in J-protocol. For example, in the above attack, Bob will completely not know the value of the corresponding key bit though he can optimally estimate the address of Alice’s query. Consequently it is impossible for Bob to give Alice a right answer with certainty. This is assured by the no-signaling principle.

Fig. 5 The relation between the probability pc, with which Alice gets conclusive result, and the value of θ under Bob’s attack. The dashed line denotes the result in J-protocol (i.e. θ = π/4).

Generally speaking, as pointed out in Sec.II, the users can choose a suitable value of θ so that k = 1 in our protocol, which means the optimal communication complexity. Recalling the process in step 6, we know that it is easier for Bob to guess the conclusiveness of one bit in Alice’s final key when k is smaller. But this fact does not hurt the security of this protocol when k = 1 because Bob will lose the value of the bit when he tries to get its conclusiveness. Of course, a large θ (e.g. θ > π/4) can also be selected to achieve a small pc if we pursue a low probability with which Bob can correctly guess the address of Alice’s query (see Fig. 5). This exhibits the flexibility of our protocol again.

4. Conclusion

We present a flexible QKD-based QPQ protocol, which can be seen as a generalization of J-protocol [12

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

]. Though the modification, i.e. adding a parameter θ, seems minor in contrast to J-protocol, the effect of this modification is significant. On the one hand, it retains all the features of J-protocol. For example, it is loss tolerant, practical and robust against quantum memory attack. On the other hand, our protocol is very flexible and controllable due to introducing the parameter θ, which can be selected as a continuous value. When a small θ(θ < π/4) is used the aim of QPQ can be achieved with a smaller k (even k = 1) than that in J-protocol, which implies lower complexity of both quantum and classical communications. In our protocol, by adjusting the value of θ, the average number of the key bits Alice obtains can be located on any fixed value the users wanted for any database size N. In addition, when θ < π/4 our protocol exhibits better database security, which is ensured by the impossibility of perfectly distinguishing nonorthogonal quantum states. At the same time, user privacy is ensured by the no-signaling principle and, in some special conditions, θ > π/4 can be also selected to obtain a low probability with which Bob can correctly guess the address of Alice’s query.

Acknowledgments

This work is supported by NSFC (Grant Nos. 61170270, 61100203, 60903152, 61003286, 61121061), NCET (Grant No. NCET-10-0260), SRFDP (Grant No. 20090005110010), Beijing Natural Science Foundation (Grant Nos. 4112040, 4122054), the Fundamental Research Funds for the Central Universities (Grant Nos. BUPT2011YB01, BUPT2011RC0505, 2011PTB-00-29, 2011RCZJ15, 2012RC0612), Science and Technology on Communication Security Laboratory Foundation (Grant No. 9140C110101110C1104).

References and links

1.

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on the Foundations of Computer Science , (Santa Fe, New Mexico, 1994), 124–134. [CrossRef]

2.

L. K. Grover, “A fast quantum mechanical algorithm for database search,” in 28th Annual ACM Symposium on Theory of Computing , (New York, 1996), 212–219.

3.

C.H. Bennett and G. Brassard, “Quantum cryptography: public-key distribution and coin tossing,” in IEEE Int. Conf. on Computers, Systems, and Signal Processing , (Bangalore, 1984), 175–179.

4.

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002). [CrossRef]

5.

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM 45, 965–981 (1998). [CrossRef]

6.

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci. 60, 592–629 (2000). [CrossRef]

7.

H. K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A 56, 1154–1162 (1997). [CrossRef]

8.

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett. 100, 230502 (2008). [CrossRef] [PubMed]

9.

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory 56, 3465–3477 (2010). [CrossRef]

10.

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A 80, 010302 (2009). [CrossRef]

11.

L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A 84, 022313 (2011). [CrossRef]

12.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A 83, 022301 (2011). [CrossRef]

13.

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett. 92, 057901 (2004). [CrossRef] [PubMed]

14.

C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett. 68, 3121–3124 (1992). [CrossRef] [PubMed]

15.

P. Raynal, “Unambiguous State Discrimination of two density matrices in Quantum Information Theory,” e-print arXiv:quant-ph/0611133.

16.

U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A 71, 050301 (2005). [CrossRef]

17.

C. A. Fuchs, “Distinguishability and Accessible Information in Quantum Theory,” e-print arXiv:quant-ph/9601020.

18.

C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, New York, 1976).

OCIS Codes
(270.0270) Quantum optics : Quantum optics
(270.5568) Quantum optics : Quantum cryptography

ToC Category:
Quantum Optics

History
Original Manuscript: June 13, 2012
Revised Manuscript: July 9, 2012
Manuscript Accepted: July 10, 2012
Published: July 16, 2012

Citation
Fei Gao, Bin Liu, Qiao-Yan Wen, and Hui Chen, "Flexible quantum private queries based on quantum key distribution," Opt. Express 20, 17411-17420 (2012)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-20-16-17411


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on the Foundations of Computer Science, (Santa Fe, New Mexico, 1994), 124–134. [CrossRef]
  2. L. K. Grover, “A fast quantum mechanical algorithm for database search,” in 28th Annual ACM Symposium on Theory of Computing, (New York, 1996), 212–219.
  3. C.H. Bennett and G. Brassard, “Quantum cryptography: public-key distribution and coin tossing,” in IEEE Int. Conf. on Computers, Systems, and Signal Processing, (Bangalore, 1984), 175–179.
  4. N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002). [CrossRef]
  5. B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998). [CrossRef]
  6. Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000). [CrossRef]
  7. H. K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A56, 1154–1162 (1997). [CrossRef]
  8. V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett.100, 230502 (2008). [CrossRef] [PubMed]
  9. V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory56, 3465–3477 (2010). [CrossRef]
  10. F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009). [CrossRef]
  11. L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A84, 022313 (2011). [CrossRef]
  12. M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011). [CrossRef]
  13. V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004). [CrossRef] [PubMed]
  14. C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett.68, 3121–3124 (1992). [CrossRef] [PubMed]
  15. P. Raynal, “Unambiguous State Discrimination of two density matrices in Quantum Information Theory,” e-print arXiv:quant-ph/0611133.
  16. U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A71, 050301 (2005). [CrossRef]
  17. C. A. Fuchs, “Distinguishability and Accessible Information in Quantum Theory,” e-print arXiv:quant-ph/9601020.
  18. C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, New York, 1976).

Cited By

 Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig. 1 Fig. 2 Fig. 3
 
Fig. 4 Fig. 5
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited