Gabriel Ghinita
Cyrus Shahabi
ABSTRACT
Mobile devices equipped with positioning capabilities (e.g., GPS) can ask location-dependent queries to Location Based Services (LBS). To protect privacy, the user location must not be disclosed. Existing solutions utilize a trusted anonymizer between the users and the LBS. This approach has several drawbacks: (i) All users must trust the third party anonymizer, which is a single point of attack. (ii) A large number of cooperating, trustworthy users is needed. (iii) Privacy is guaranteed only for a single snapshot of user locations; users are not protected against correlation attacks (e.g., history of user movement).
We propose a novel framework to support private location-dependent queries, based on the theoretical work on Private Information Retrieval (PIR). Our framework does not require a trusted third party, since privacy is achieved via cryptographic techniques. Compared to existing work, our approach achieves stronger privacy for snapshots of user locations; moreover, it is the first to provide provable privacy guarantees against correlation attacks. We use our framework to implement approximate and exact algorithms for nearest-neighbor search. We optimize query execution by employing data mining techniques, which identify redundant computations. Contrary to common belief, the experimental results suggest that PIR approaches incur reasonable overhead and are applicable in practice.
- G. Aggarwal, N. Mishra, and B. Pinkas. Secure Computation of the k th-Ranked Element. In Proc. of Int. Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 40--55, 2004.]]Google Scholar
Cross Ref
- R. Agrawal, T. Imielinski, and A. N. Swami. Mining Association Rules between Sets of Items in Large Databases. In Proc. of ACM SIGMOD, pages 207--216, 1993.]] Google ScholarDigital Library
- R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar. Preserving user location privacy in mobile data management infrastructures. In Int. Workshop on Privacy Enhancing Technologies, pages 393--412, 2006.]] Google ScholarDigital Library
- B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In IEEE Symposium on Foundations of Computer Science, pages 41--50, 1995.]] Google ScholarDigital Library
- C.-Y. Chow and M. F. Mokbel. Enabling Private Continuous Queries for Revealed User Locations. In Proc. of SSTD, pages 258--275, 2007.]] Google ScholarDigital Library
- C.-Y. Chow, M. F. Mokbel, and X. Liu. A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-based Services. In ACM International Symposium on Advances in Geographic Information Systems, 2006.]] Google ScholarDigital Library
- M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000.]] Google ScholarDigital Library
- R. Fagin. Combining Fuzzy Information from Multiple Systems. In Proc. of ACM PODS, pages 216--226, 1996.]] Google ScholarDigital Library
- J. Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. Strauss, and R. N. Wright. Secure Multiparty Computation of Approximations. In Int. Colloquium on Automata, Languages and Programming (ICALP), 2001.]] Google ScholarDigital Library
- D. E. Flath. Introduction to Number Theory. John Wiley & Sons, 1988.]]Google Scholar
- B. Gedik and L. Liu. Location Privacy in Mobile Systems: A Personalized Anonymization Model. In Proc. of ICDCS, pages 620--629, 2005.]] Google ScholarDigital Library
- G. Ghinita, P. Kalnis, and S. Skiadopoulos. PRIVE: Anonymous Location-based Queries in Distributed Mobile Systems. In Proc. of Int. Conference on World Wide Web (WWW), pages 371--380, 2007.]] Google ScholarDigital Library
- O. Goldreich. The Foundations of Cryptography, volume 2. Cambridge University Press, 2004.]] Google ScholarDigital Library
- M. Gruteser and D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. In Proc. of USENIX MobiSys, 2003.]] Google ScholarDigital Library
- H. Hu and D. L. Lee. Range Nearest-Neighbor Query. IEEE TKDE, 18(1):78--91, 2006.]] Google ScholarDigital Library
- P. Indyk and D. P. Woodruff. Polylogarithmic Private Approximations and Efficient Matching. In Proc. of Theory of Cryptography Conference (TCC), pages 245--264, 2006.]] Google ScholarDigital Library
- P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias. Preventing Location-Based Identity Inference in Anonymous Spatial Queries. IEEE TKDE, 19(12):1719--1733, 2007.]] Google ScholarDigital Library
- A. Khoshgozaran and C. Shahabi. Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy. In Proc. of SSTD, pages 239--257, 2007.]] Google ScholarDigital Library
- E. Kushilevitz and R. Ostrovsky. Replication is NOT needed: Single database, computationally-private information retrieval. In IEEE Symposium on Foundations of Computer Science, pages 364--373, 1997.]] Google ScholarDigital Library
- M. F. Mokbel, C. Y. Chow, andW. G. Aref. The New Casper: Query Processing for Location Services without Compromising Privacy. In Proc. of VLDB, 2006.]] Google ScholarDigital Library
- B. Moon, H. V. Jagadish, C. Faloutsos, and J. H. Saltz. Analysis of the Clustering Properties of the Hilbert Space-Filling Curve. IEEE TKDE, 13(1):124--141, 2001.]] Google ScholarDigital Library
- P. Samarati. Protecting Respondents? Identities in Microdata Release. IEEE TKDE, 13(6):1010--1027, 2001.]] Google ScholarDigital Library
- M. Shaneck, Y. Kim, and V. Kum. Privacy Preserving Nearest Neighbor Search. In Int. Workshop on Privacy Aspects of Data Mining (PADM), 2006.]] Google ScholarDigital Library
- R. Sion and B. Carbunar. On the Computational Practicality of Private Information Retrieval. In Proc. of Network and Distributed System Security Symposium (NDSS), 2007.]]Google Scholar
- J. Vaidya and C. Clifton. Privacy-Preserving Top-K Queries. In Proc. of ICDE, pages 545--546, 2005.]] Google ScholarDigital Library
Index Terms
- Private queries in location based services: anonymizers are not necessary
Recommendations
Understanding the privacy-efficiency trade-off in location based queries
SPRINGL '08: Proceedings of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBSMobile devices with global positioning capabilities (e.g., GPS) allow users to ask queries relative to their present location. Since certain queries may be privacy-sensitive, it is important to protect the identity of the users who send requests for ...
Location anonymity in continuous location-based services
GIS '07: Proceedings of the 15th annual ACM international symposium on Advances in geographic information systemsA major concern for large-scale deployment of location-based services (LBSs) is the potential abuse of their client location data, which may imply sensitive personal information. Location privacy protection is challenging because a location itself may ...
Protecting query privacy with differentially private k-anonymity in location-based services
Nowadays, location-based services (LBS) are facilitating people in daily life through answering LBS queries. However, privacy issues including locationprivacy and queryprivacy arise at the same time. Existing works for protecting queryprivacy either ...
Comments