Privacy-Preserving Quantum Two-Party Geometric Intersection

Wenjie Liu ,Yong XuJames C.N.Yang,Wenbin Yu and Lianhua Chi

Abstract:Privacy-preserving computational geometry is the research area on the intersection of the domains of secure multi-party computation (SMC) and computational geometry.As an important field,the privacy-preserving geometric intersection (PGI)problem is when each of the multiple parties has a private geometric graph and seeks to determine whether their graphs intersect or not without revealing their private information.In this study,through representing Alice’s (Bob’s) private geometric graph as the set of numbered grids S A (S B ),an efficient privacy-preserving quantum two-party geometric intersection (PQGI) protocol is proposed.In the protocol,the oracle operation O A (O B ) is firstly utilized to encode the private elements of S A = (a 0, a 1,…,a M -1) into the quantum states,and then the oracle operation O f is applied to obtain a new quantum state which includes the XOR results between each element of and S B.Finally,the quantum counting is introduced to get the amount (t ) of the statesequaling to and the intersection result can be obtained by judging t ＞0 or not.Compared with classical PGI protocols,our proposed protocol not only has higher security,but also holds lower communication complexity.

Keywords:Privacy-preserving computational geometry,quantum two-party geometric intersection,oracle,quantum counting.

1 Introduction

The problem of privacy-preserving computational geometry is an important research area on the intersection of the domains of secure multi-party computation (SMC) [Oleshchuk and Zadorozhny (2007)] and computational geometry [Preparata and Shamos (2012)].It focuses on how cooperative users can use their own private geometric information as inputs in collaborative computing in the distributed systems,and they can obtain the correct results while ensuring their privacy.Since the privacy-preserving computational geometry is firstly proposed by Atallah et al.[Atallah and Du (2001)],the other researchers have drawn extensive attention on some related problems,such as point inclusion [Troncoso-Pastoriza,Katzenbeisser,Celik et al.(2007);Luo,Huang and Zhong (2007)],geometric intersection[Erlebach,Jansen and Seidel (2005);Paw lik,Kozik,Krawczyk et al.(2013)],nearest points or closest pair [Li and Ni (2002);Tao,Yi,Sheng et al.(2010)],and convex hull[Huang,Luo and Wang (2008);Löffler and van Kreveld (2010);Assarf,Gaw rilow,Herr et al.(2017)],which have been applied to many important military and commercial fields.Consider the following scenario,two countries A and B intend to build a railway in an of fshore area.Before the completion of the railway,the construction route is confidential.In order to prevent future collisionsoftrains,countries A and B hope to determine if there are any two disjoint routes without revealing their own routes,and to negotiate with the location of the intersection.The above problem is a typical application of privacypreserving geometric intersection (PGI).Different from the protocols based on circuit evaluation schemes,recently Qin et al.[Qin,Duan,Zhao et al.(2014)] proposed the Lagrange multiplier method to solve the intersection of the two private curves,and this method is suitable for solving general geometry intersection problems.On the other way,some researchers tried to study the geometric problems in three dimensional space [Li,Wu,Wang et al.(2014)].However,most of these classical solutions are based on computational complexity assumptions,and they cannot ensure the participants’ privacy under the attack of quantum computation.

Fortunately,quantum cryptography can provide the unconditional security,which is guaranteed by some physical principles of quantum mechanics,to resist against such impact.In additional,quantum parallelism makes it possible to greatly speed up solving some specific computational tasks,such as large-integer factorization [Shor (1994)] and database search [Grover (1996)].With quantum mechanics utilized in the information processing,many important research findings are presented in recent decades,such as quantum key distribution (QKD) [Bennett and Brassard (1984)],quantum key agreement(QKA) [Liu,Chen,Ji et al.(2017);Liu,Xu,Yang et al.(2018)],quantum secure direct communication [Liu,Chen,Ma et al.(2009);Liu,Chen,Liu (2016);Liu and Chen(2016)],quantum private comparison [Liu,Liu,Liu et al.(2014);Liu,Liu,Chen et al.(2014);Liu,Liu,Wang et al.(2014)],and quantum sealed-bid auction (QSBA) [Naseri(2009);Liu,Wang,Ji et al.(2014);Liu,Wang,Yuan et al.(2016)],and deterministic remote state preparation [Liu,Chen,Liu et al.(2015);Qu,Wu,Wang et al.(2017)].These findings have shown the potential power in either the efficiency improvements or the security enhancements.

In this study,we pay attention to the PGI problem:Alice owns a private geometric graphGA,Bob has the other geometric graphGB,and they want to determine whether these two graphs intersect without revealing any private information to each other.By utilizing some specific oracle operations and quantum counting algorithm,we propose an efficient privacy-preserving quantum two-party geometric intersection (PQGI) protocol.The rest of this paper is organized as follows,the PQGI protocol is proposed in Section 2,and the correctness,security and efficiency analysis of PQGI protocol are discussed in Section 3,while the conclusion is drawn in the last section.

2 Prelim inaries

Before introducing the procedures of PQGI protocol,we firstly make some definitions of PGI problem and PQGI protocol.Without loss of generality,we suppose there are two parties,i.e.,Alice and Bob,and the formal definitions are given as below.

2.1 The problems

Problem 1 (Privacy-preserving point inclusion):There are two parties,Alice has a pointpA,and Bob has a geometric graphGB.They want to decide whetherpA∈GBwithout revealing to each other anything more than what can be inferred from that answer.

Problem 2 (Privacy-preserving two-party geometric intersection):Two parties Alice,Bob own the private geometric graphsGA,GB,respectively,and decide whetherGA∩GB≠∅ without disclosing their respective private information.

As a point can be viewed as a special geometric graph whose area is small enough to be one dot,Problem 1 is a typical case of Problem 2.In the study,we only consider the geometric intersection of Problem 2.

2.2 The definition of PQGI

In order to solve Problem 2,the private geometric graph can be represented as the set of grids in the area of the graph (suppose these girds are divided sufficiently),then the intersection of two geometric graphs is transformed into the intersection of two sets.Without loss of generality,we suppose Alice and Bob have a private geometric graphGAandGBon the plane,and they divide and number the whole plane intoRgrids (HereRis a large enough integer),then Alice’s and Bob’s graphs can be denoted asrespectively (shown in Fig.1).

Figure1:The illustration of partitioning and numbering the plane with R =400.The green(blue) part is Alice’s graph G A (Bob’ graph G B ),respectively,and the yellow part is the intersection area

Through representing Alice’s and Bob’s private geometric graphsGA,GBas the grid setsSA,SB),the PQGI protocol is defined as follows.

Definition 1 (the PQGI protocol):Alice and Bob encode their serial numbers of graph grids,i.e.,into two initial statesandrespectively,hereAfter executing this protocol,they can obtain the result of whether the two graphs intersect without revealing their private information.To be specific,the PQGI protocol should guarantee the following privacy:

●Alice’s PrivacyBob cannot learn any secret information about Alice’s geometric graph without risking Alice’s detection.

●Bob’s PrivacyAlice cannot get any secret information about Bob’s geometric graph without risking Bob’s detection.

3 The privacy-preserving quantum two-party geometric intersection protocol

Suppose Alice and Bob’s private geometric graphsGAandGBare located on a unified plane,and the plane is uniformly divided intoRgrids,hereRis a large enough integer that the whole plane can be represented by these grids with sufficient accuracy.Thus Alice’s and Bob’s graphsGA,GBcan be represented as the sets of grids:whereai,bjare unique serial numbers in [1,R],0 ≤i≤M-1,0≤j≤N-1.The detailed protocol is described in detail as follows (shown in Fig.2).

Figure2:The procedure of the proposed PQGI protocol.The dotted (solid) line denotes the quantum (classic) channel

1.Alice and Bob prepare the initial statesrespectively,whereanddenote Alice’s(m-qubit) and Bob’s (n-qubit) address qubits,whileDaandDbrepresent Alice’s and Bob’s (r-qubit) data qubits,Then Alice and Bob apply the oracle operationto encode their private elements of(shown in Fig.3 and Fig.4).

Then Alice and Bob obtain the result statesrespectively,then Alice sends her stateto Bob.

Figure3:Schematic circuit of the oracle operation O A

Figure4:Schematic circuit of the oracle operation O B.

Then he sends the result stateto Alice.

Figure5:Schematic circuit of the oracle operation O f

Figure6:Schematic circuit of the oracle operation O A

4.After the cheating check,Alice executes the quantum counting algorithm [Brassard,HØyer and Tapp (1998)] onto countwheretis the number of states thatequaling toin(i∈[0,M-1],j∈[0,N-1]).After executing the quantum algorithm,Bob obtains the result oft.Then Alice judges whetherGAandGBintersect according to the value oft:ift＞0,then it can be deduced that there existsai=bjfor anyiandj,then get the conclusion thatGAintersects withGB,otherwise,GAandGBare not intersect.

5.Alice tells Bob the result of whetherGAintersects withGB.

3 Correctness,security and efficiency analysis

3.1 Correctness analysis

Without loss of generality,we suppose that Alice (Bob) has a private graphGA(GB),which is represented asSA={1,2,5,6}(SB={6,7,10,11}),and thusM=4,N=4,R=16,Alice and Bob want to determine whether there exists an intersection betweenGAandGB(shown in Fig.7).

Figure7:The example of the two intersecting geometric graphs G A and G B

In Step 1,Alice and Bob prepare two initial quantum statesin the form ofand then apply oracle operationon them,the two result statesare as follows:

Then Bob applies the oracle operationOfon stateand obtains the state

Bob further sends the result stateto Alice.Alice then applies the oracle operationon the data qubitsDaofand obtains the result stateas follow:

Alice then performs measurement on the data qubitsDaofthe measurement outcome turns to bethen she can conclude that Bob has not cheated.Then Alice executes the quantum counting algorithm on.Since the counting result,thus graphGAintersects with graphGB.

3.2 Security analysis

Now we discuss the security of our protocol.To realize such a secure PQGI protocol,two security requirements should be satisfied,that are Alice’s privacy and Bob’s privacy.

3.2.1 Alice’s privacy

Suppose Bob wants to extract information about private graphGA(i.e.,aiwithout affecting the final result of the protocol.If Bob performs the projective measurement on statehe can randomly obtain one elementfromThe statecan also be represented by an ensembleis the probability that Bob obtains Alice’s coordinates:

Here,we get the upper bound of information that Bob can get from Alice's coordinates is determined by the Holevo’s bound [Holevo (2011)]:

whereS(ρ)denotes the Von Neumann entropy of quantum stateρ,H(A:B)means the information Bob can get about Alice’s secret information,we have:

Then,Bob can only get coordinate information by measuring the stateρ.If Bob performs measurement on the statethe state will collapse into one basis state,i.e.,and the statewill be changed toIn Step 3 of our protocol,Alice checks whether Bob has cheated by applying oracle operationOAon the data qubitsDainand then performs measurement on them.Since the measured data qubitsdoes not equal toshe can conclude Bob has cheated and aborts the protocol.

3.2.2 Bob’s privacy

Suppose Alice wants to extract any information about private graphGB(i.e.biwithout affecting the final result of the protocol.If Bob performs the projective measurement on statehe can randomly obtain one element,i.e.

However,the state Alice received isand Alice does not know choose which base to measure and obtainbj.On the other hand,the received information is in the form ofai⊕bj,which means he even does not know whichaiencodes thebj,and therefore prevents his cheating on Bob’s privacy.

3.3 Efficiency analysis

The communication cost is one of the key indicators of the e efficiency for communication protocols.In order to analyze the efficiency of our PQGI protocol,we choose the classical PGI protocols [Atallah and Du (2001);Qin,Duan,Zhao et al.(2014)] as comparative references.In the Atallah et al.’s protocol,the participants send total 4M2messages to Bob,hereMis the number of divided edges of the e geometric graph,and each message requiresRbits.So the transmitted messages of the eir protocol are 4M2*R,and their communication complexity isO(M2R).While in Qin et al.’s protocol [Qin,Duan,Zhao et al.(2014)],it requires to send 2(M2+N2)messages,and each message requiresRbits.HereMandNare the number of curves from the edges of the e geometry,and its communication complexity is

In our PQGI protocol,Alice sends a (m+r)-qubit statesto Bob in Step 1,and thenBob sends a (m+n+2r)-qubit state to Alice in Step 3,wherethus the total transmitted messages of our protocol arequbits.Thus our communication complexity isO(l ogMNR).Through the above calculations,we can get the results of the e three protocols’communication complexity (see Tab.1).Obviously,our protocol achieves a great reduction in the communication complexity aspect.

Table1:Comparison among our protocol and the other PGI protocols

4 Conclusion and discussion

In this paper,we present a novel quantum solution to two-party geometric intersection based on oracle and the quantum counting algorithm.The security of them is based on the quantum cryptography instead of difficulty assumptions of mathematical problem.Compared with the classical related protocols,our solution has the advantage of higher security and lower communication complexity.In addition,our proposed protocol can also be extended to some other complicated privacy-preserving computation problems,such as privacy-preserving database queries over cloud data [Cao,Wang,Li et al.(2014);Shen,Li,Li et al.(2017)],privacy-preserving set operations in cloud computing [Cao,Li,Dang et al.(2017);Zhuo,Jia,Guo et al.(2017)],and privacy-preserving reversible data hiding over encrypted image [Cao,Du,Wei et al.(2016)].

Furthermore,the method of the oracle operation applied in the presented protocols is general and can be employed to solve other similar privacy-preserving computation geometry problems,such as convex hull,polygon inclusion,etc.However,how to extend our two party scenarios to the multi-party scenario,and the more complex situations such as geometric union is another problem.We would like to investigate the applications of quantum technologies in more kinds of privacy-preserving computational geometric protocols in the future.

Acknowledgement:The authors would like to thank the anonymous reviewers and editors for their comments that improved the quality of this paper.This work is supported by the Nature Science Foundation of China (Grant Nos.61502101 and 61501247),the Natural Science Foundation of Jiangsu Province,China (Grant No.BK20171458),the Six Talent Peaks Project of Jiangsu Province,China (Grant No.2015-XXRJ-013),the Natural science Foundation for colleges and universities of Jiangsu Province,China (Grant No.16KJB520030),the Research Innovation Program for College Graduates of Jiangsu Province,China (Grant No.KYCX17_0902),the Practice Innovation Training Program Projects for the Jiangsu College Students (Grant No.201810300016Z),and the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD).