SA Two-level Protocol to Answer Private Location-based QueriesRoopa VishwanathanYan HuangRoopaVishwanathan, Computer Science and EngineeringUniversity of North TexasPrivacy Issues in Location-based ServicesSClient requests information from the server related to her current locationSClient wants to maintain privacy and anonymitySLocation can be associated with user identity, e.g. service request at your own houseSThus client does not want the server to know her locationSServer wants to release as precise information as possible06/09/09ISI 2009, Dallas, Texas1Existing ApproachesSCloaking: k-anonymity 345SClient requests are sent to an anonymizerSAnonymizer “cloaks” clients location to a region that include k-1 other clientsSAnonymizer forwards queries to the server using the cloaked locationSNeed to trust the anonymizer06/09/09ISI 2009, Dallas, Texas2Existing Approaches contdSPeer-to-peer 67SA client c searches for k-1 peersSOne peer acts as agent on behalf cSChosen agent forwards requests to server using cloaked regionSNeed to be able to find k-1 peersSNeed to trust the chosen agent peer306/09/09ISI 2009, Dallas, TexasDrawbacks of Existing ApproachesSNeed to trust the anonymizer or peersSReveals some spatial information (general region of query)SCorrelation attacksSCould possibly identify the clientSLarge volume of query results06/09/09ISI 2009, Dallas, Texas4Problem Definition and MotivationSNearest Neighbor Query Example: Find me the nearest gas station from the location based server (LBS)SGoal: Find a way to protect privacy of the client while ensuring server returns precise dataSPrivacy means: no release of identity or location of the clientSMotivation: Recent research shows PIR is a feasible and privacy-preserving approach, but server reveals too much data 506/09/09ISI 2009, Dallas, TexasOur ApproachSFocus on Exact-Nearest-Neighbour queriesSUses PIR framework by Shahabi et al. 1 as a first stepSApplies Oblivious Transfer 2 as the second step (to make server data precise)06/09/09ISI 2009, Dallas, Texas6Private Information Retrieval (PIR)SBased on a computationally hard problemSClient sends an encrypted request for informationSServer does not know what it reveals06/09/09ISI 2009, Dallas, Texas7Bob: 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, Texas9SUser input: y1,y2,.,yn SServer computes: zr = nj=1 w (r,j)Sw (r,j)=yj2 if Mr,j = 0 and w (r,j)=yj otherwiseSServer returns: z = z1, z2, ., znSUser computes: If za QR, Ma,b = 0else Ma,b = 1Example of PIR in LBS06/09/09ISI 2009, Dallas, Texas10SUser location: M2,3SUser generates request: y =y1,y2,y3,y4Sy3 QNR, y1,y2,y4 QRSServer replies: z1,z2,z3,z4SIf z2 QR, M2,3 = 0, else M2,3 = 1Oblivious TransferSFundamental cryptographic protocolSAlice asks for one bit of information from BobSAlice does not get to know any other bit SBob does not know what bit Alice asked for SMany variants: 1-of-2, 1-of-n, k-of-n1106/09/09ISI 2009, Dallas, TexasExample of Oblivious Transfer (OT)1206/09/09ISI 2009, Dallas, TexasExampleof OT contd1306/09/09ISI 2009, Dallas, TexasThe Two-level Protocol: First Step06/09/09ISI 2009, Dallas, Texas14SServer divides the area into Voronoi cells and superimposes a grid on itSEach grid cell has list of Points Of Interests (POIs) associated with itSOne POI each in a Voronoi cellSContents of grid cells are the list of POIsFirst Step: PIR . contd06/09/09ISI 2009, Dallas, Texas15SClient requests a column corresponding to its grid cell using PIR: .PIR(C)SServer prepares encrypted column CSecond Step Oblivious Transfer (OT)SClient initiates 1-of-n OT with serverSClient and server agree on a set of keys SServer encrypts each bit of PIR response with a different set of keys (according to the index of the bit) and sends it acrossSServer and client exchange keys (through 1-of-2 OT)SClient can decrypt the bit it wants and none else1606/09/09ISI 2009, Dallas, TexasHigh-level ViewSClient knows it locationSTries to execute PIR to get its cellSServer prepares PIR response corresponding to a column that the client is in and encrypts itSClient and server engage in 1-of-n OT to get clients cell from the column1706/09/09ISI 2009, Dallas, TexasHigh-level View contdSContents of clients grid cell are its neighbours (Point of Interests of POIs)SClient can easily calculate which point is the nearest SMay contain redundant POIsSRepeated/redundant POIs can be discarded1806/09/09ISI 2009, Dallas, TexasComplexity SN : number of objects (POIs), S M: number of bits in eachSRequest by client: O(M N)SResponse by server: O(MN + N log N)STotal 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(mlogn+mn)O(mn+logn)ConclusionSContribution: Proposed a two-level protocol for private location queriesSPIR over the entire grid large amount of data would be revealedSOT over the entire grid very expensiveSOur approach reduces amount of data revealed, not very expensiveSFuture direction: alternative approach (multi-level PIR)2106/09/09ISI 2009, Dallas, TexasReferences1.G. 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.2.B. Pinkas and M. Naor. Efficient Oblivious Transfer Protocols. In Proc. Of 12th ACM-SIAM Symposium on Discrete Algorithms. pp. 448-457, 2001.3.B. Gedik and L. Liu. Privacy in mobile systems: A personalized anonymization model. In Proc. Of ICDCS. Pp. 620-629, 2005.4.P. Kalnis, G. Ghinita, K. Mouratidis and D. Papadias. Preventing location-based identity inference in anonymous spatial queries. In Proc. Of IEEE TKDE, pp. 239-257, 2007.2206/09/09ISI 2009, Dallas, TexasReferences contd5.M. Mokbel, C. Chow and W. Aref. The new Casper: Query Processing for location-based services without compromising privacy. In Proc. Of VLDB, pp. 219-239, 2005.6.C.Y. Chow, M. Mokbel and X. Liu. A peer-to-peer spatial cloaking algorithm for anonymous location-based services. In Proc. of ACM International Symposium on GIS. Pp. 247-256, 2006.7.G. Ghinita, P. Kalnis and S. Skiadopoulos. PRIVE: Anonymous location-based queries in distributed mobile systems. In Proc. of 1st Intl. Conference on World Wide Web (WWW), pp. 371-380, 2007.2306/09/09ISI 2009, Dallas, Texas