Transcript p 1
Private Queries in Location-Based Services: Anonymizers are Not Necessary Gabriel Ghinita1 Panos Kalnis1 Ali Khoshgozaran2 Cyrus Shahabi2 Kian Lee Tan1 National University of Singapore 2 University of Southern California 1 2 Location-Based Services (LBS) LBS users Mobile devices with GPS capabilities Queries NN Queries Location server is NOT trusted “Find closest hospital to my present location” 3 Problem Statement Queries may disclose sensitive information But user location may disclose identity Query through anonymous web surfing service Triangulation of device signal Publicly available databases Physical surveillance How to preserve query source anonymity? Even when exact user locations are known 4 PIR Overview Computationally hard to find i from q(i) Bob can easily find Xi from r (trap-door) 5 Existing LBS Privacy Solutions 6 Spatial K-Anonymity Query issuer “hides” among other K-1 users Probability of identifying query source ≤ 1/K Idea: anonymizing spatial regions (ASR) 7 Casper[Mok06] Quad-tree based Fails to preserve anonymity for outliers Unnecessarily large ASR size A1 u2 • Let K=3 u1 u3 • If any of u1, u2, u3 queries, ASR is A1 NOT SECURE u !!! 4 A2 • If u4 queries, ASR is A2 • u4’s identity is disclosed [Mok06] – Mokbel et al, The New Casper: Query Processing for Location Services without Compromising Privacy, VLDB 2006 8 Reciprocity u3 u2 u1 u5 u4 u6 [KGMP07] – Kalnis P., Ghinita G., Mouratidis K., Papadias D., "Preventing Location-Based Identity Inference in Anonymous Spatial Queries", IEEE TKDE 2007. 9 Hilbert Cloak (HC) Based on Hilbert space-filling curve index users by Hilbert value of location partition Hilbert sequence into “K-buckets” Start End 10 Continuous Queries[CM07] Problems ASRs grows large Query dropped ifusome user in U disconnects 1 u 3 u2 [CM07] C.-Y. Chow and M. Mokbel “Enabling Private Continuous Queries For Revealed User Locations”. In Proc. of SSTD 2007 11 Space Encryption[KS07] Drawbacks Hilbert Mapping approximate answers are makes use of tamper-resistant devices P4 may be vulnerable if some POI12are 14 known 19 24 P1 P2 Q P1 P2 P4 P 3 P3 NN(15)=P2 15 [KS07] A. Khoshgozaran, C. Shahabi. Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy , In Proc. Of SSTD 2007 12 Motivation Limitations of existing solutions Assumption of trusted entities Considerable overhead for sporadic benefits anonymizer and trusted, non-colluding users maintenance of user locations No privacy guarantees especially for continuous queries 13 Our Approach 14 LBS Privacy with PIR PIR Two-party cryptographic protocol No pooling of a large user population required No trusted anonymizer required No trusted users required No need for location updates Location data completely obscured 15 PIR Theoretical Foundations Let N =q1*q2, q1 and q2 large primes Quadratic Residuosity Assumption (QRA) QR/QNR decision computationally hard Essential properties: QR * QR = QR QR * QNR = QNR 16 PIR Protocol for Binary Data a y1 Get X10 y2 y3 y4 QNR a=2, b=3 X4 X8 X12 X16 z4 X3 X7 X11 X15 z3 X2 X6 X10 X14 z2 X1 X5 X9 X13 z1 b 4 z2=QNR => X10=1 4( j 1) i j z2=QR => X10=0 j 1 zi X y 17 Approximate Nearest Neighbor p4 p6 p1 p5 p8 p2 p7 p9 p3 u Data organized as a square matrix Each column corresponds to index leaf An entire leaf is retrieved – the closest to the user 18 Exact Nearest Neighbor A A3: p1, p2, p3 A4: p1, --, -- B C D 4 p 1 3 2 Z4 p3 p4 u p2 Z3 Z2 Z1 1 Y1 Y2 Y3 Y4 QNR Only z2 needed 19 Rectangular PIR Matrix 20 Avoiding Redundant Computations Data mining Identify frequent partial products 21 Parallelize Computation Values of z can be computed in parallel Master-slave paradigm Offline phase: master scatters PIR matrix Online phase: Master broadcasts y Each worker computes z values for its strip Master collects z results 22 Experimental Settings Sequoia dataset + synthetic sets 10,000 to 100,000 POI Modulus up to 1280 bits 23 Parallel Execution 24 Data Mining Optimization 25 Disclosed POI 26 Conclusions PIR-based LBS privacy No need to trust third-party Secure against any location-based attack Future work Further reduce PIR overhead Support more complex queries Include more POI information in the reply 27 Bibliography [KGMP07] – Kalnis P., Ghinita G., Mouratidis K., Papadias D., "Preventing Location-Based Identity Inference in Anonymous Spatial Queries", IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE), 19(12), 1719-1733, 2007. [GZPK07] – Ghinita G., Zhao K., Papadias D., Kalnis P., Reciprocal Framework for Spatial K-Anonymity, Technical Report [GKS07a] – Ghinita G., Kalnis P., Skiadopoulos S., "PRIVE: Anonymous Location-based Queries in Distributed Mobile Systems", Proc. of World Wide Web Conf. (WWW), Banff, Canada, 371-380, 2007. [GKS07b] – Ghinita G., Kalnis P., Skiadopoulos S., "MOBIHIDE: A Mobile Peer-to-Peer System for Anonymous Location-Based Queries", Proc. of the Int. Symposium in Spatial and Temporal Databases (SSTD), Boston, MA, 221-238, 2007. http://anonym.comp.nus.edu.sg