Yi-Hua Zhou(周藝華),Xue-Wei Bai(白雪瑋), Lei-Lei Li(黎雷蕾),Wei-Min Shi(侍偉敏), and Yu-Guang Yang(楊宇光)

1Faculty of Information Technology,Beijing University of Technology,Beijing 100124,China

2School of Computer,Beijing University of Posts and Telecommunications,Beijing 100876,China

1 Introduction

SPIR(symmetrically private information retrieval)is proposed to solve the problem in which user queries certain item ofNitems owned by database.In addition,it is also required that user cannot get other items and database cannot know which item user wants to get.While the two sides without trust are communicating,they want to not only prevent the common privacy from being eavesdropped but also protect the personal privacy.

The security of most traditional SPIR schemes is based on unproven assumptions of mathematical difficulty.However,with the rapid development of quantum computation,they are facing with more and more severe challenges.

QPQ protocol is the quantum solution of SPIR problem and the security is ensured by unconditional security theoretically in terms of physical principles.In QPQ protocols,an asymmetric key is generated between the user and database.The database knows the key all while the user only knows a little fraction.But the database has no idea about which part of the key the user knows.Using the asymmetric key,SPIR problem can be solved.Jakobiet al.proposed the first QKD-based QPQ protocol(J protocol).[1]It was based on SARG04 scheme,[2]and solved the problem of lacking support for large database.From then on,more and more researches focus on QKD-based QPQ protocols.Meanwhile,many improved protocols have been proposed.[3?23]

The factors that in fluence security of QPQ protocols are divided into external factors and internal factors.The attack from participants is usually more crucial than that from external part for a protocol.Thus a protocol needs to make sure that the common privacy is invulnerable to external factors,more importantly,it needs to ensure the personal privacy even if both sides of communication are dishonest,because they may cheat each other by sending a faked internal state or make a fake announcement to invade data privacy of the other side.

However,there is not any protocol could ensure the privacy of both user and database in previous QKD-based QPQ protocols.According to the one who prepares initial qubits,previous protocols can be divided into two categories.One is database Bob prepares initial qubits,while the other is user Alice prepares initial qubits.

Most of previous QKD-based QPQ protocols[1,4?21]use approach that Bob prepares and sends initial qubits thus with relative lower user privacy.Take J protocol[1]as an example.In this protocol,Database Bob sends qubits firstly and makes correlative classical announcement after Alice has received.As a result,this protocol has shortage of internal attack from database.[22]Bob can have higher probability to know the information about the bit locations of Alice by easily preparing a fake state.Thus the user privacy is threatened.Yanget al.[9]also proposed a protocol in which Bob prepares and sends initial photons in stateIn this protocol,Bob even could 100%know the bit locations of Alice by sending certain fake states and announcing certain announcement,[22]therefore the user privacy is worse than J protocol.

In addition,Weiet al.[18]proposed a protocol in which Bob makes quantum state to resist JM attack.In her protocol,user could not control the manipulations which Bob does on the signal.The reason is that individual attack of Bob may threaten user privacy and the protocol does not detect his cheating behavior.This also shows Wei’s protocol has some defects for user privacy.Thus,it can be inferred that,in the protocols which Bob makes initial state,it is very likely for Bob to launch internal attack because Bob knows the information about initial state accurately.In this paper we take J protocol as the representative of this kind of protocols to compare with our protocol.

Others ensure user privacy by using approach that Alice prepares initial quantum qubits,but there are some defects for,database security.For example,Yuet al.[22]proposed an improved J protocol against internal attack from database Bob and can enhance user privacy.In their protocol,the initial qubits are sent by Alice instead of Bob.So the database cannot know any information of initial quantum states.By this way,if Bob wants to implement internal attack,he can only infer initial quantum state according to outcome state and further make a fake announcement to get the bit locations of Alice.The user privacy has been greatly enhanced and then the threat of Bob’s attack is reduced.Moreover,together with honesty checking,the cheats of Bob can be detected and then be well resisted.However,this modi fication was at the cost of losing part of database privacy.By preparing fake states,Alice can get more final keys than normal condition after post-processing.In addition,there is no detection for cheating of Alice.Thus the database privacy will be threatened.Another protocol in which Alice prepares initial qubits is Yang’s protocol.It adds detection of database and cancels detection of user.Yang’s protocol[23]has discussed that the user privacy could be enhanced if the initial quantum states are made by Alice.Yang thinks the user privacy of their protocol is perfect,because the initial quantum states are made and transmitted by Alice.And according to Heisenberg uncertainty principle,Bob cannot get any information about the state.

In fact,however,although Bob cannot get any information about the state and thus improve the user privacy,user privacy is not perfect.This is because Bob will measure the quantum state after received it,he can infer initial state with certain probability,launch an internal attack and gain bene fit.What is more,it costs nothing for Bob to do so because there is no detection for his cheating,which in fluences protocol’s user privacy.Therefore,the detection for cheating from database is added to our protocol.Thus we could not only provide a better user privacy but also detect external attack.In this paper,when comparing protocols in which Alice prepares initial qubits,we primarily discuss representative protocol,Yu’s protocol.

To enhance the privacy of both sides,we proposed a two-way-four-state-QKD-based QPQ protocol.In our protocol,the fake state attacking of Alice is useless thus it can ensure database security.Because the initial state is made by Alice,the user privacy is similar to Yu’s protocol[22](the protocol with best user privacy of present four-state-QKD-based QPQ protocols),together with the detection for cheating from database,it can ensure high user privacy.

The rest of this paper is organized as follows.In Sec.2,we describe our proposed protocol in detail.In Sec.3,we analyze the security of our protocol compared with other typical QPQ protocols.Finally,we make a conclusion according to our analysis in Sec.4.

2 The Proposed Private Query Protocol

Step 1Alice prepares a long sequence of photons in one of the four state,and sends them to Bob.

Step 2Bob generates a random stringa∈{0,1}nas the final keyKr.For the instances that Bob has successfully received,he measures thei-th particle inZbasisifai=1.At this time,Bob chooses one of follow mode randomly for his photon to operate.

Ctrl mode:Return his photon to Alice directly.

Shift mode:If the results that Bob has got isorthen his photon will pass theXgate and return to Alice;if the result isthen makes his photon pass theZgate and return to Alice.As a result,after this operation,transformed totransformed totransformed totransformed to

Step 3Alice announces which instances she detects.For each qubit,Bob announces which mode he chooses.

Ctrl mode:For each qubit,Alice uses base with sending state(to measure.If the result is different from the state of the sending photon,which means the measure base is different from which Bob uses,then Bob’s measure base,i.e.the value ofcan be judged;if the result is the same as the state of the sending photon,Alice cannot judge the measure base which Bob uses.

For example,assuming that the state of photon which Alice sends to Bob isthe result must beif Bob usesZbase.When Alice receives the photon from Bob,if she usesZbase then the result is alsoAt this moment,Alice does not know which base Bob uses;if Bob usesXbase,then the result might beWhen Alice receives photons from Bob,the result might beorafter measuring usingZbase.And if the result is,then Alice cannot get any information;if the result isthen Alice can realize that Bob usesXbase,that is,=1.It can be concluded that Alice has a quarter of possibility((1/2)×(1/2)=1/4)to indicate the value of.That is,Alice can indicate a quarter ofKr.

Table 1 Data for bit learning in Ctrl mode(initial state is

Table 1 Data for bit learning in Ctrl mode(initial state is

The measure base chosen Returned The measure base chosen Alice’s sent by Alice The state by Bob:The outcome state of Bob by Alice:The derivation state of Bob measurement results Z:|0? |0? Z:|0? ?|0?X:|+? |+? Z:|1? 1 Z:|0? ?X:|?? |?? Z:|1? 1 Z:|0? ?

Table 2 Data for bit learning in Shift mode(initial states is

Table 2 Data for bit learning in Shift mode(initial states is

The measure base chosen Returned The measure base chosen The results Alice’s sent by Alice The state by Bob:The outcome state of Bob by Alice:The after derivation state of Bob measurement results transformed Z:|0? |1? Z:|1? |0? ?|0?X:|+? |?? Z:|1? |0? ?Z:|0? |1? 1 X:|?? |+? Z:|1? |0? ?Z:|0? |1? 1

Shift mode:Alice uses base with sending state(Zbase for.Once the results are measured,it needs to be transferred:|0?transformed totransformed totransformed totransformed toThen compare the results with the state of photon that sending from itself.The approach is similar to Ctrl mode.

Step 4Alice randomly selects half of theKrand requires Bob to announce his measurement value from Step 2.Then Alice can infer whetherKris right by comparing the outcome states of Bob with her initial states and outcome states of herself.Supposing Bob cheats Alice,Alice could recognize the fraud,and she would abort protocol;otherwise,they will continue to Step 5.

Step 5At this point,Alice and Bob get half of theKr,denoted asKM.Bob and Alice execute classical postprocessing which is similar to Yang’s protocol.[23]

where the threshold should be set tothe function,the valuekandtshould be set appropriately so that Alice can get about one bit of the final keyO.

Step 6Suppose Alice knows thej-th bitOjand wants to retrieve thex-th itemXi.She declares the numbers=j?i.Then,Bob shiftsObysand uses the new keyO’to encrypt his database.BecauseXiis encrypted byOj,Alice can decryptXicorrectly.

3 Security Analysis

This protocol meets loss tolerance.Bob operates the two modes in this protocol in order to meet loss tolerance.When Alice received photon from Bob,she could not realize which results are necessary before she received announcement of Bob.For example,Alice prepares initial qubitand sends to Bob,then Bob implements Step 2 to return measured qubit.Finally,Alice usesZbase to measure the qubit and the outcome state might beWhen Bob chooses Ctrl mode,the bit can be obtained by Alice if the outcome state is|1>;when Bob chooses Shift mode,the bit can be obtained by Alice if the outcome state is|0>.Because the two modes that Bob has chosen are completely random and Alice cannot get any information about it.So Alice cannot judge which bit Bob can get according to the outcome states.Thus,Alice totally need not to cheat Bob for which photon she has lost.

In addition,our protocol is also cheat-sensitive.Bob’s cheating behavior will also be found by Alice in Step 4.The reason is described as follows.Suppose that the outcome state of Bob is|0>,if Bob announces|1>instead of|0>,then Alice will detect the cheating with probability of 1/2 in the condition of that Alice’s initial state of is|0>.Here,we give a detailed describe of calculating detected cheat probability while Bob announcing fake state.For example,if Bob announces state|+>,Alice will detect the cheating when the initial state or the outcome state of Alice is|?>.In our calculating,we set eventAwhen Bob announces state|+>and set eventBwhile initial state of Alice is|?>.Then we can calculate the probability that Alice detects cheating when Bob announces state|+>is:

Similarly,if Bob announces|?>,Alice will also detect the cheating with probability of 3/8.

Bob will state|+>or|?>to avoid being detected,but the probability is very low.There is still a probability of 3/8 for each bit of being detected.The probability attains 1?(1?3/8)nthat Alice will detect the cheating in the detection fornbit.This probability can reach at 99.994%whenn=10 whilenis usually more than 10 in the real application,so the cheating behavior of Bob may be detected with extremely high probability and this protocol is cheat-sensitive.

For Yu’s protocol,[22]the lowest probability that Bob’s cheating will be detected by Alice is 1/4 which is lower than ours.The reason is that Bob announces outcome state while the value of bit in our protocol.Thus our protocol is super to Yu’s protocol[22]in cheat-sensitive.

The protocol uses the post-processing similar as Yang’s protocol,[23]which can make the protocol resist jointmeasurement attack.

3.1 Database Security

3.1.1Fake single state attacks

In present protocols that Alice sends initial states,Alice can threat the security of database by preparing fake states.But in our protocol,Alice derives the key bit by comparing initial quantum state and outcome state of quantum returned by database,Alice’s fake states are useless and fake state attack is avoided.The detailed analysis is described as follows:

Assume that Alice is dishonest,she can prepare a fake quantum state|φ1>=cosθ|0>+sinθ|1>(0<θ/2<π),and send it to Bob.When Bob measures the qubit inZbase orXbase,the result could be one of the following states:|0>,|1>,|+>,and|?>.Since Bob is lack of the information of the photon being measured at this moment,he could not choose a measure base,which can bring more bene fit to him.Thus,we affirm that the probabilities of Bob’s choice for two bases are same(i.e.,1/2).We can calculate the four possibilities of Bob’s results:the possibility of getting|0>is(1/2)cos2θ,(1/2)sin2θfor|1>,(1/2)cos2(π/4?θ)for|+>,and(1/2)sin2(π/4?θ)for|?>,respectively.Since Bob chooses any one of the two modes in order to meet loss tolerance,the mode itself has no in fluence on the results of Alice after Bob announced his choice of mode.Thus we assume that Bob uses Ctrl mode.

Assuming that Alice usesZbase to measure her qubit after she received from Bob,the results could be|0>or|1>.When the result is|0>,Alice could infer the probability which Bob usesZbase is:

Obviously,the value reached maximum whenθ=0,P1=2/3 and the probability that Bob usesXbase isP2=P(X|result=|0>)=1?P1=1/3. The value reached minimum whenθ=π/2,P1=0,andP2=1?P1=1 at this time.When the result is|1>,Alice could infer the probability which Bob usesZbase is:

Obviously,the value reached maximum whenθ=π/2,P3=2/3,and the probability that Bob usesXbase isP4=P(X|result=|1>)=1?P3=1/3;the value reached minimum whenθ=0,P3=0,andP4=1?P3=1 at this time.

In conclusion,in order to get more items of qubits,Alice needs to get maximum probability of Bob’s measuring base.That is,she will useθ=π/2 orθ=0(i.e.|φ1>is|0>or|1>),and this is one of the four states,which Alice needs to send in our protocol.

Similarly,if Alice usesXbase to measure,maximum probability of Bob’s measuring base she could obtain only when she sends|+>or|?>,which is exactly one of the four states that Alice needs to send.That is,Alice does not have to send fake state to attack because the probability that she gets the key is de finitely less than the four state(|0>,|1>,|+>,|?>)no matter which cheat state she sends.

It means that Alice can greatly improve the possibility of getting bits by preparing fake states,so Alice can get more bit of final key.Obviously,our protocol has higher database security comparing to Yu’s protocol.[22]

3.1.2EPR Attacks

Alice is likely to use the strategy of faking EPR-pair in order to get more items. She could prepare state|φ2>=(1/2)(|0>|0>+|1>|1>),and send the first particle to Bob.If Alice measures her particle before Bob finished his measurement,the whole process will be the same as the original protocol.Thus there will be no sense for Alice to do so.We infer that Alice measures her particle after Bob finished measurement.

If Bob chooses Ctrl mode,Alice will have two photons with same state after Bob returning his photon.At this moment,if Alice usesZbase to measure a photon and the outcome state is|0>,then the probability that the state of another photon is 1/4 for|+>,1/4 for|?>,and 1/2 for|0>.This is similar to the situation in the original protocol.The probability that Alice gets the key is 1/4,so Alice needs not to fake EPR.

For Shift mode,Alice transfers the outcome state of the returned photon.Thus the Shift mode will be consistent with Ctrl mode,the same security can be ensured.

3.2 User Privacy

In our protocol,if the outcome state which Bob has got was|0>,Bob could know the qubit probability sent by Alice was|0>is 1/2,1/4 for|+>and 1/4 for|?>.Suppose Bob is dishonest,and he wants to obtain the address queried by Alice.Bob can prepare a fake state,|ψ>=cosθ|0>+sinθ|1>,then return to Alice.After Alice’s measurement,Bob could infer the probability of Alice to a conclusive result is:

It reaches maximum(P5=3/4)whenθ=π/2 and minimum(P5=1/4)whenθ=0 which is the same as Yu’s protocol.[22]That is to say,user privacy in our protocol is similar to Yu’s protocol.For J protocol,if Bob tries to obtain the address queried by Alice,he can send fake states and improve the probability of Alice to a conclusive result of 85.36%or decrease to approximately 14.64%.[1]Obviously,by comparing the data it can be showed that our protocol has better user privacy compared with J protocol.

It also proves that,after Alice prepared initial state,the threat of Bob’s spoo fing is greatly reduced because Bob could not get the information of initial state accurately.

4 Conclusion

We propose a new QPQ protocol in this paper which Alice prepares and sends quantum states to improve user privacy. What is more,it also uses speci fic two-way communication approach in which Bob returns measured quantum state by Ctrl or Shift mode instead of announcing two non-orthogonal qubits,which may leak half of the correct qubit,so the database security of ours is also strengthened.By comparing our protocol with some protocols in which Bob prepares initial qubits and protocols in which Alice prepares initial qubits,it can be showed that our protocol is better for both user privacy and database security.

(i)It has high database security compared with other QPQ protocols in which Alice initializes qubits.In our protocol,it is useless to get more key bits for Alice by sending fake qubits.So the database security has been signi ficantly improved.

(ii)The initial quantum states are generated by Alice while Bob cannot know the exact information,thus user privacy of this protocol is improved as well.What is more,the user privacy is strengthened by checking process of internal attacking behavior of Bob.

(iii)It can resist JM attack because of the postprocessing methods proposed by Yang’s protocol.[23]

As a two way QPQ protocol,of course,it has a little more complicated compared with its counterparts of one way protocols,while enhancing the security of both parts of communications.Similar to many present QPQ protocols which based on QKD protocol,our protocol also has not solved the problem that Alice always obtains more than one bit of the final key.We will continue to the research in the future.

[1]M.Jakobi,C.Simon,N.Gisin,et al.,Phys.Rev.A 83(2011)022301.

[2]V.Scarani,A.Acin,G.Ribordy,and N.Gisin,Phys.Rev.Lett.92(2004)057901.

[3]F.Gao,B.Liu,Q.Y.Wen,and H.Chen,Opt.Express.20(2012)17411.

[4]J.L.Zhang,F.Z.Guo,F.Gao,et al.,Phys.Rev.A.88(2013)022334.

[5]Y.G.Yang,S.J.Sun,P.Xu,and J.Tian,Quantum.Inf.Process.13(2014)805.

[6]Y.G.Yang,S.J.Sun,J.Tian,and P.Xu,Optik.125(2014)5538.

[7]C.Wang,L.Hao,and L.J.Zhao,Chin.Phys.Lett.28(2011)080302.

[8]P.Chan,I.Lucio,Martinez,et al.,Sci.Rep.4(2014)05233.

[9]Y.G.Yang,M.O.Zhang,and R.Yang,Quantum.Inf.Process.14(2015)1017.

[10]S.J.Sun,Y.G.Yang,and M.O.Zhang,Quantum.Inf.Process.14(2015)1443.

[11]F.Yu and D.W.Qiu,Quantum.Inf.Comput.14(2014)91.

[12]D.S.Shen,X.C.Zhu,W.P.Ma,et al.,J.Optoelectron Adv.M 14(2012)504.

[13]H.Lai,M.A.Orgun,J.Pieprzyk,et al.,Phys.Lett.A 379(2015)2561.

[14]B.Liu,F.Gao,W.Huang,and Q.Y.Wen,Sci.China.Phys.Mech.58(2015)100301.

[15]T.Hogg and L.Zhang,Int.J.Quantum.Inf.7(2009)459.

[16]C.Y.Wei,F.Gao,Q.Y.Wen,and T.Y.Wang,Sci.Rep.4(2014)7537.

[17]W.X.Shi,X.T.Liu,J.Wang,and C.J.Tang,Commun.Theor.Phys.64(2015)299.

[18]C.Y.Wei,T.Y.Wang,and F.Gao,Phys.Rev.A 93(2016)042318.

[19]Z.W.Sun,J.P.Yu,P.Wang,and L.L.Xu,Phys.Rev.A 91(2015)052303.

[20]S.W.Xu,Y.Sun,and S.Lin,Quantum.Inf.Process.15(2016)3301.

[21]T.Y.Wang,S.Y.Wang,and J.F.Ma,Int.J.Theor.Phys.55(2016)3309.

[22]F.Yu,D.W.Qiu,H.Z.Situ,et al.,Quantum.Inf.Process.14(2015)4201.

[23]Y.G.Yang,Z.C.Liu,J.Li,et al.,Phys.Lett.A.380(2016)4033.