Location anonymity in continuous location-based services

ABSTRACT

A 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 reveal a subject's identity. To support location anonymity, existing research reduces location resolution by ensuring each location reported to a service provider is a cloaking area that contains at least K mobile nodes. This strategy is effective when each location update can be considered as an independent event. In this paper, we investigate location anonymity in the context of continuous LBSs, which require frequent location updates from service users. Knowing that a user is inside a cloaking area constrains its position in the next cloaking area. Thus, simply ensuring each cloaking area contains at least K users does not give a user K-anonymity protection. We propose to measure the anonymity degree of a cloaking area using entropy, which takes into account not only the number of the entities inside, but also their anonymity probability distribution. To find a cloaking area that can provide a given level of anonymity protection and is also as small as possible, we present a novel technique with a polynomial time complexity. The effectiveness of our techniques is studied under various conditions using location data synthetically generated using real road maps and traffic volume data. The results show that our techniques can indeed protect user anonymity at a desired level, and at the same time, minimize the size of each cloaking area, allowing users to receive high quality services.

REFERENCES

• 1: P. E. Agre. Transport Informatics and the New Landscape of Privacy Issues. In Computer Professionals for Social Responsibility (CPSR) Newsletter, volume 13(3), 1995.
• 2: L. Barkhuus and A. Dey. Location-based Services for Mobile Telephony: A Study of Users' Privacy Concerns. In 9th International Conference on Human-Computer Interaction, 2003.
• 3: Alastair R. Beresford , Frank Stajano, Location Privacy in Pervasive Computing, IEEE Pervasive Computing, v.2 n.1, p.46-55, January 2003 [doi>10.1109/MPRV.2003.1186725 ]
• 4: Thomas Brinkhoff, A Framework for Generating Network-Based Moving Objects, Geoinformatica, v.6 n.2, p.153-180, June 2002 [doi>10.1023/A:1015231126594 ]
• 5: Ying Cai , Kien A. Hua , Guohong Cao , Toby Xu, Real-Time Processing of Range-Monitoring Queries in Heterogeneous Mobile Databases, IEEE Transactions on Mobile Computing, v.5 n.7, p.931-942, July 2006 [doi>10.1109/TMC.2006.105]
• 6: R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar. Preserving User Location Privacy in Mobile Data Management Infrastructure. In 6th Workshop on Privacy Enhancing Technologies, 2006.
• 7: 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]
• 8: Thomas M. Cover , Joy A. Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience, 2006
• 9: J. Cuellar, J. Morris, and D. Mulligan. In Internet Engineering Task Force Geopriv Requirements, http://www.ietf.org/html.charters/geopriv-charter.html.
• 10: J. Cuellar , J. Morris , D. Mulligan , J. Peterson , J. Polk, Geopriv Requirements, RFC Editor, 2004
• 11: Sastry Duri , Marco Gruteser , Xuan Liu , Paul Moskowitz , Ronald Perez , Moninder Singh , Jung-Mu Tang, Framework for security and privacy in automotive telematics, Proceedings of the 2nd international workshop on Mobile commerce, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570705.570711]
• 12: B. Gedik and L. Liu. A Customizable k-Anonymity Model for Protecting Location Privacy. In ICDCS'05, pages 620--629, 2005.
• 13: 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]
• 14: Baik Hoh , Marco Gruteser, Protecting Location Privacy Through Path Confusion, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.194-205, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.33]
• 15: P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias. Preserving Anonymity in Location Based Services. In Technical Report TRB6/06, Department of Computer Science, National University of Singapore.
• 16: P. A. Karger and Y. Frankel. Security and Privacy Threats to ITS. In Proceedings of the Second World Congress on Intelligent Transport Systems, volume 5, pages 2452--2458, 1995.
• 17: H. Kido, Y. Yanagisawa, and T. Satoh. An Anonymous Communication Technique using Dummies for Location-based Services. In IEEE ICPS'05, pages 88--97, 2005.
• 18: Marc Langheinrich, A Privacy Awareness System for Ubiquitous Computing Environments, Proceedings of the 4th international conference on Ubiquitous Computing, p.237-245, September 29-October 01, 2002, Göteborg, Sweden
• 19: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 20: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 21: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 22: 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
• 23: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 24: G. Myles, A. Friday, and N. Davies. Preserving Privacy in Environments with Location-based Applications. In IEEE Pervasive Computing, volume 02, pages 56--64, 2003.
• 25: D. Reid. An Algorithm for Tracking Multiple Targets. IEEE Transactions on Automatic Control, 24(6):843--854, December 1979.
• 26: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 27: A. Serjantov and G. Danezis. Towards an Information Theoretic Metric for Anonymity. In Roger Dingledine and Paul Syverson, editors, Privacy Enhancing Technologies workshop (PET 2002), volume 2482 of LNCS, pages 41--53. Springer-Verlag, 2002.
• 28: C. Shannon. The Mathematical Theory of Communication. In Bell System Technical Journal, volume 30, pages 50--64, 1948.
• 29: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 30: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 31: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 32: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 33: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 34: J. Warrior, E. McHenry, and K. McGee. They Know Where You Are. In IEEE Spectrum, 2003.
• 35: B. Zheng, W.-C. Lee, and D. Lee. Search continuous nearest neighbors on the air. In the First International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous'04), pages 236--245, Boston, MA, U.S.A, August 22--26 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Experimentation

Keywords:
continuous location updates, location anonymity, location-based services