Private queries in location based services: anonymizers are not necessary

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.

REFERENCES

• 1: 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.
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: 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.
• 4: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 5: C.-Y. Chow and M. F. Mokbel. Enabling Private Continuous Queries for Revealed User Locations. In Proc. of SSTD, pages 258--275, 2007.
• 6: Chi-Yin Chow , Mohamed F. Mokbel , Xuan Liu, A peer-to-peer spatial cloaking algorithm for anonymous location-based service, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183500]
• 7: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 8: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 9: Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin Strauss , Rebecca N. Wright, Secure Multiparty Computation of Approximations, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.927-938, July 08-12, 2001
• 10: D. E. Flath. Introduction to Number Theory. John Wiley & Sons, 1988.
• 11: Bugra Gedik , Ling Liu, Location Privacy in Mobile Systems: A Personalized Anonymization Model, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.620-629, June 06-10, 2005 [doi>10.1109/ICDCS.2005.48]
• 12: Gabriel Ghinita , Panos Kalnis , Spiros Skiadopoulos, PRIVE: anonymous location-based queries in distributed mobile systems, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242623]
• 13: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 14: Marco Gruteser , Dirk Grunwald, Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking, Proceedings of the 1st international conference on Mobile systems, applications and services, p.31-42, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1189037]
• 15: Haibo Hu , Dik Lun Lee, Range Nearest-Neighbor Query, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.78-91, January 2006 [doi>10.1109/TKDE.2006.15]
• 16: P. Indyk and D. P. Woodruff. Polylogarithmic Private Approximations and Efficient Matching. In Proc. of Theory of Cryptography Conference (TCC), pages 245--264, 2006.
• 17: Panos Kalnis , Gabriel Ghinita , Kyriakos Mouratidis , Dimitris Papadias, Preventing Location-Based Identity Inference in Anonymous Spatial Queries, IEEE Transactions on Knowledge and Data Engineering, v.19 n.12, p.1719-1733, December 2007 [doi>10.1109/TKDE.2007.190662]
• 18: 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.
• 19: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 20: Mohamed F. Mokbel , Chi-Yin Chow , Walid G. Aref, The new Casper: query processing for location services without compromising privacy, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 21: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 22: P. Samarati, Protecting Respondents' Identities in Microdata Release, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1010-1027, November 2001 [doi>10.1109/69.971193]
• 23: Mark Shaneck , Yongdae Kim , Vipin Kumar, Privacy Preserving Nearest Neighbor Search, Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, p.541-545, December 18-22, 2006 [doi>10.1109/ICDMW.2006.133]
• 24: R. Sion and B. Carbunar. On the Computational Practicality of Private Information Retrieval. In Proc. of Network and Distributed System Security Symposium (NDSS), 2007.
• 25: Jaideep Vaidya , Chris Clifton, Privacy-Preserving Top-k Queries, Proceedings of the 21st International Conference on Data Engineering, p.545-546, April 05-08, 2005 [doi>10.1109/ICDE.2005.112]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Design, Experimentation, Security

Keywords:
location anonymity, private information retrieval, query privacy