a twolevel protocol to answer private locationb：一二級(jí)協(xié)議回答私人locationb

1、A Two-level Protocol to Answer Private Location-based QueriesRoopa VishwanathanYan HuangRoopaVishwanathan, Computer Science and EngineeringUniversity of North TexasPrivacy Issues in Location-based ServicesClient requests information from the server related to her current locationClient wants to main

2、tain privacy and anonymityLocation can be associated with user identity, e.g. service request at your own houseThus client does not want the server to know her locationServer wants to release as precise information as possible06/09/09ISI 2009, Dallas, Texas1Existing ApproachesCloaking: k-anonymity 3

3、45Client requests are sent to an anonymizerAnonymizer “cloaks” clients location to a region that include k-1 other clientsAnonymizer forwards queries to the server using the cloaked locationNeed to trust the anonymizer06/09/09ISI 2009, Dallas, Texas2Existing Approaches contdPeer-to-peer 67A client c

4、 searches for k-1 peersOne peer acts as agent on behalf cChosen agent forwards requests to server using cloaked regionNeed to be able to find k-1 peersNeed to trust the chosen agent peer306/09/09ISI 2009, Dallas, TexasDrawbacks of Existing ApproachesNeed to trust the anonymizer or peersReveals some

5、spatial information (general region of query)Correlation attacksCould possibly identify the clientLarge volume of query results06/09/09ISI 2009, Dallas, Texas4Problem Definition and MotivationNearest Neighbor Query Example: Find me the nearest gas station from the location based server (LBS)Goal: Fi

6、nd a way to protect privacy of the client while ensuring server returns precise dataPrivacy means: no release of identity or location of the clientMotivation: Recent research shows PIR is a feasible and privacy-preserving approach, but server reveals too much data 506/09/09ISI 2009, Dallas, TexasOur

7、 ApproachFocus on Exact-Nearest-Neighbour queriesUses PIR framework by Shahabi et al. 1 as a first stepApplies Oblivious Transfer 2 as the second step (to make server data precise)06/09/09ISI 2009, Dallas, Texas6Private Information Retrieval (PIR)Based on a computationally hard problemClient sends a

8、n encrypted request for informationServer does not know what it reveals06/09/09ISI 2009, Dallas, Texas7E (i)Bob: X 1,2,3,.,N Alice: Wants bit iv(X, E(i)PIR Theory806/09/09ISI 2009, Dallas, TexasPIR in Location-based Services06/09/09ISI 2009, Dallas, Texas9User input: y1,y2,.,yn Server computes: zr =

9、 nj=1 w (r,j)w (r,j)=yj2 if Mr,j = 0 and w (r,j)=yj otherwiseServer returns: z = z1, z2, ., znUser computes: If za QR, Ma,b = 0else Ma,b = 1Example of PIR in LBS06/09/09ISI 2009, Dallas, Texas10User location: M2,3User generates request: y =y1,y2,y3,y4y3 QNR, y1,y2,y4 QRServer replies: z1,z2,z3,z4If

10、z2 QR, M2,3 = 0, else M2,3 = 1Oblivious TransferFundamental cryptographic protocolAlice asks for one bit of information from BobAlice does not get to know any other bit Bob does not know what bit Alice asked for Many variants: 1-of-2, 1-of-n, k-of-n1106/09/09ISI 2009, Dallas, TexasExample of Oblivio

11、us Transfer (OT)1206/09/09ISI 2009, Dallas, TexasExampleof OT contd1306/09/09ISI 2009, Dallas, TexasThe Two-level Protocol: First Step06/09/09ISI 2009, Dallas, Texas14Server divides the area into Voronoi cells and superimposes a grid on itEach grid cell has list of Points Of Interests (POIs) associa

12、ted with itOne POI each in a Voronoi cellContents of grid cells are the list of POIsFirst Step: PIR . contd06/09/09ISI 2009, Dallas, Texas15Client requests a column corresponding to its grid cell using PIR: .PIR(C)Server prepares encrypted column CSecond Step Oblivious Transfer (OT)Client initiates

13、1-of-n OT with serverClient and server agree on a set of keys Server encrypts each bit of PIR response with a different set of keys (according to the index of the bit) and sends it acrossServer and client exchange keys (through 1-of-2 OT)Client can decrypt the bit it wants and none else1606/09/09ISI

14、 2009, Dallas, TexasHigh-level ViewClient knows it locationTries to execute PIR to get its cellServer prepares PIR response corresponding to a column that the client is in and encrypts itClient and server engage in 1-of-n OT to get clients cell from the column1706/09/09ISI 2009, Dallas, TexasHigh-le

15、vel View contdContents of clients grid cell are its neighbours (Point of Interests of POIs)Client can easily calculate which point is the nearest May contain redundant POIsRepeated/redundant POIs can be discarded1806/09/09ISI 2009, Dallas, TexasComplexity N : number of objects (POIs), M: number of b

16、its in eachRequest by client: O(M N)Response by server: O(MN + N log N)Total time: O(MN + N log N)1906/09/09ISI 2009, Dallas, TexasComparison of Costs2006/09/09ISI 2009, Dallas, TexasActionPIROTOur Two Level ProtocolReq. by user O(n)O(logn) O(n+logn)Res. By serverO(mn)O(mn)O(mn)Total timeO(mn)O(mlog

17、n+mn)O(mn+logn)ConclusionContribution: Proposed a two-level protocol for private location queriesPIR over the entire grid large amount of data would be revealedOT over the entire grid very expensiveOur approach reduces amount of data revealed, not very expensiveFuture direction: alternative approach

18、 (multi-level PIR)2106/09/09ISI 2009, Dallas, TexasReferencesG. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi and K.Tan. Private Queries in Location Based Services: Anonymizers are not Necessary. In Proc. of ACM SIGMOD 2008, pp. 121-132.B. Pinkas and M. Naor. Efficient Oblivious Transfer Protocols

19、. In Proc. Of 12th ACM-SIAM Symposium on Discrete Algorithms. pp. 448-457, 2001.B. Gedik and L. Liu. Privacy in mobile systems: A personalized anonymization model. In Proc. Of ICDCS. Pp. 620-629, 2005.P. Kalnis, G. Ghinita, K. Mouratidis and D. Papadias. Preventing location-based identity inference in anonymous spatial queries. In Proc. Of IE