Gabriel Ghinita
ABSTRACT
Nowadays, mobile users with global positioning devices canaccess Location Based Services (LBS) and query about pointsof interest in their proximity. For such applications to succeed,privacy and confidentiality are essential. Encryptionalone is not adequate; although it safeguards the systemagainst eavesdroppers, the queries themselves may disclosethe location and identity of the user. Recently, there havebeen proposed centralized architectures based on K-anonymity,which utilize an intermediate anonymizer between themobile users and the LBS. However, the anonymizer mustbe updated continuously with the current locations of allusers. Moreover, the complete knowledge of the entire systemposes a security threat, if the anonymizer is compromised.In this paper we address two issues: (i) We show thatexisting approaches may fail to provide spatial anonymityfor some distributions of user locations and describe a noveltechnique which solves this problem. (ii) We propose Prive,a decentralized architecture for preserving the anonymityof users issuing spatial queries to LBS. Mobile users self-organizeinto an overlay network with good fault toleranceand load balancing properties. Prive avoids the bottleneckcaused by centralized techniques both in terms of anonymizationand location updates. Moreover, the system state isdistributed in numerous users, rendering Prive resilient toattacks. Extensive experimental studies suggest that Priveis applicable to real-life scenarios with large populations ofmobile users.
- C. C. Aggarwal. On k-Anonymity and the Curse of Dimensionality. In Proc. of VLDB, pages 901--909, 2005. Google Scholar
Digital Library
- S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable application layer multicast. In Proc. of ACM SIGCOMM, pages 205--217, 2002. Google ScholarDigital Library
- S. Banerjee and S. Khuller. A Clustering Scheme for Hierarchical Control in Wireless Networks. In Proc. of IEEE INFOCOM, pages 1028--1037, 2001.Google Scholar
- R. Bayardo and R. Agrawal. Data Privacy through Optimal k-Anonymization. In Proc. of ICDE, pages 217--228, 2005. Google ScholarDigital Library
- T. Brinkhoff. A Framework for Generating Network-Based Moving Objects. Geoinformatica, 6(2):153--180, 2002. Google ScholarDigital Library
- A. R. Butz. Alternative Algorithm for Hilbert's Space-Filling Curve. IEEE Trans. on Computers, 20(4):424--426, 1971.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 In Proc. of ACM GIS, pages 171--178, 2006. Google ScholarDigital Library
- A. Crainiceanu, P. Linga, J. Gehrke, and J. Shanmugasundaram. Querying P2P Networks using P-trees. In Proc. of WebDB, pages 25--30, 2004. Google ScholarDigital Library
- 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
- M. Gruteser and D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. In Proc. of USENIX MobiSys, pages 31--42, 2003. Google ScholarDigital Library
- H. Hu and D. L. Lee. Range Nearest-Neighbor Query. IEEE TKDE, 18(1):78--91, 2006. Google ScholarDigital Library
- H. V. Jagadish, B. C. Ooi, and Q. H. Vu. BATON: a Balanced Tree Structure for P2P networks. In Proc. of VLDB, pages 661--672, 2005. Google ScholarDigital Library
- P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias. Preventing Location-Based Identity Inference in Anonymous Spatial Queries. Technical Report TRB6/06, National Univ. of Singapore, 2006.Google Scholar
- K. LeFevre, D. J. DeWitt, and R. Ramakrishnan. Incognito: Efficient Full-Domain K-Anonymity. In Proc. of ACM SIGMOD, pages 49--60, 2005. Google ScholarDigital Library
- A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-Diversity: Privacy Beyond k-Anonymity. In Proc. of ICDE, pages 24--35, 2006. Google ScholarDigital Library
- A. Meyerson and R. Williams. On the Complexity of Optimal K-anonymity. In Proc. of ACM PODS, pages 223--228, 2004. Google ScholarDigital Library
- M. F. Mokbel, C. Y. Chow, and W. G. Aref. The New Casper: Query Processing for Location Services without Compromising Privacy. In Proc. of VLDB, pages 763--774, 2006. Google ScholarDigital Library
- D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Efficient OLAP Operations in Spatial Data Warehouses. In Proc. of SSTD, pages 443--459, 2001. Google ScholarDigital Library
- P. Samarati. Protecting Respondents' Identities in Microdata Release. IEEE TKDE, 13(6): 1010--1027, 2001. Google ScholarDigital Library
- I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: a Scalable Peer-to-Peer Lookup Protocol for Internet Applications. IEEE/ACM Transactions on Networking, 11(1):17--32, 2003. Google ScholarDigital Library
- L. Sweeney. k-Anonymity: A Model for Protecting Privacy. Int. J. of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557--570, 2002. Google ScholarDigital Library
- Y. Tao and X. Xiao. Personalized Privacy Preservation. In Proc. of ACM SIGMOD, pages 229--240, 2006. Google ScholarDigital Library
- B. Yang and H. Garcia-Molina. Improving Search in Peer-to-Peer Networks. In Proc. of ICDCS, pages 5--14, 2002. Google ScholarDigital Library
Index Terms
- PRIVE: anonymous location-based queries in distributed mobile systems
Recommendations
Location privacy protection with a semi-honest anonymizer in information centric networking
ICN '18: Proceedings of the 5th ACM Conference on Information-Centric NetworkingLocation-based services, which provide services based on locations of consumers' interests, are becoming essential for our daily lives. Since the location of a consumer's interest contains private information, several studies propose location privacy ...
Anonymity preserving framework for location-based information services
MEDES '10: Proceedings of the International Conference on Management of Emergent Digital EcoSystemsRecently, location based services (LBS) have become more important in today technology advancements. Privacy issue in LBS is one of the most important concerns. In this paper, we have proposed an anonymity preserving framework which can provide a user ...
PA-CTM: privacy aware collaborative traffic monitoring system using autonomous location update mechanism
SPRINGL '11: Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBSCollaborative Traffic Monitoring (CTM) systems exploit the location information continuously collected from vehicles. Users collaborate by providing their location information to have a global picture of the current traffic in real-time. However, ...
Comments