PAD: privacy-area aware, dummy-based location privacy in mobile services

ABSTRACT

Location privacy in mobile services has the potential to become a serious concern for service providers and users. Existing privacy protection techniques that use k-anonymity convert an original query into an anonymous query that contains the locations of multiple users. Such techniques, however, generally fail in offering guaranteed large privacy regions at reasonable query processing costs. In this paper, we propose the PAD approach that is capable of offering privacy-region guarantees. To achieve this, PAD uses so-called dummy locations that are deliberately generated according to either a virtual grid or circle. These cover a user's actual location, and their spatial extents are controlled by the generation algorithms. The PAD approach only requires a lightweight server-side front-end in order for it to be integrated into an existing client/server mobile service system. In addition, query results are organized according to a compact format on the server, which not only reduces communication cost, but also facilitates the result refinement on the client side. An empirical study shows that our proposal is effective in terms of offering location privacy, and efficient in terms of computation and communication costs.

REFERENCES

• 1: C. A. Ardagna, M. Cremonini, E. Damiani, S. D. C. di Vimercati, and P. Samarati. Location Privacy Protection Through Obfuscation-Based Techniques. In Proc. DBSec, 2007.
• 2: C. Bettini, S. Mascetti, X. S. Wang, and S. Jajodia. Anonymity in Location-Based Services: Towards a General Framework. In Proc. MDM, 2007.
• 3: C.-Y. Chow and M. F. Mokbel. Enabling Private Continuous Queries For Revealed User Locations. In Proc. SSTD, 2007.
• 4: C.-Y. Chow, M. F. Mokbel, and X. Liu. A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-based Services. In Proc. ACM GIS, 2006.
• 5: R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar. Preserving User Location Privacy in Mobile Data Management Infrastructures. In Proc. PET, 2006.
• 6: M. Duckham and L. Kulik. A Formal Model of Obfuscation and Negotiation for Location Privacy. In Proc. PERVASIVE, 2005.
• 7: M. Duckham and L. Kulik. Simulation of Obfuscation and Negotiation for Location Privacy. In Proc. COSIT, 2005.
• 8: B. Gedik and L. Liu. Location Privacy in Mobile Systems: A Personalized Anonymization Model. In Proc. ICDCS, 2005.
• 9: G. Ghinita, P. Kalnis, and S. Skiadopoulos. MobiHide: A Mobile Peer-to-Peer System for Anonymous Location-Based Queries. In Proc. SSTD, 2007.
• 10: G. Ghinita, P. Kalnis, and S. Skiadopoulos. PRIVÉ: Anonymous Location-Based Queries in Distributed Mobile Systems. In Proc. WWW, 2007.
• 11: M. Gruteser and D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. In Proc. USENIX MobiSys, 2003.
• 12: P. Indyk and D. Woodruff. Polylogarithmic Private Approximations and Efficient Matching. In Proc. TCC, 2006.
• 13: 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.
• 14: A. Khoshgozaran and C. Shahabi. Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy. In Proc. SSTD, 2007.
• 15: H. Kido, Y. Yanagisawa, and T. Satoh. An Anonymous Communication Technique using Dummies for Location-based Services. In Proc. ICPS, 2005.
• 16: W.-S. Ku, R. Zimmermann, W.-C. Peng, and S. Shroff. Privacy Protected Query Processing on Spatial Networks. In Proc. ICDE Workshops, 2007.
• 17: M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The New Casper: Query Processing for Location Services without Compromising Privacy. In Proc. VLDB, 2006.
• 18: M. L. Yiu, C. S. Jensen, X. Huang, and H. Lu. SpaceTwist: Managing the Trade-Offs Among Location Privacy, Query Performance, and Query Accuracy in Mobile Services. In Proc. ICDE, 2008.
• 19: L. Sweeney. k-Anonymity: A Model for Protecting Privacy. International Journal on Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557--570, 2002.
• 20: J. Voelcker. Stalked by Satellite: An Alarming Rise in GPS-enabled Harassment. IEEE Spectrum, 47(7):15--16, 2006.