ABSTRACT
Despite increasing popularity, Location-based Services (LBS) (e.g., searching nearby points-of-interest on map) on mobile handheld devices have been subject to major privacy concerns for users. The existing third-party privacy protection methods hide the exact location of users from service providers by sending cloaking regions (CR) that contain several other user locations in the vicinity. However, this has not ensured LBS full immunity from the privacy concerns. In this paper, we describe a serious privacy problem of LBS called multi-query attack. In this attack, the exact location of the service requester can be inferred by the adversary through obtaining cloaking regions that are shrunk or extended in subsequent queries. This problem can be addressed by judiciously retaining, over a period of time, the cloaking regions for the same set of users. Most methods in the literature are weakened for considering only a static snapshot of users during evaluation. Thus, any update due to user movements in real time becomes very costly. Our proposed approach, ANNC (Adaptive Nearest Neighborhood Cloaking) ,emphasizes developing disjoint sets of users dynamically over time in order to share the common CRs. The CRs are organized in balanced binary trees with restricted height. Thus ANNC achieves the balance between search efficiency and quality of cloaking with higher anonymity levels. The experimental evaluation demonstrates that ANNC will be more efficient in practice than other well-known approaches.
- Beresford, A., and Stajano, F. 2003. Location Privacy in Pervasive Computing. IEEE PERVASIVE computing: Volume 2 Issue 1, 2003, 46--55. Google ScholarDigital Library
- Sweeney, L. 2002. K-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 557--570. Google ScholarDigital Library
- Bettini, C., Mascetti, S., Wang, X.S., and Jajodia, S. 2007. Anonymity in Location-based Services: Towards a General Framework. In Proceedings of Mobile Data Managment, 2007, 69--76. Google ScholarDigital Library
- Gruteser, M., and Grunwald, D. 2003. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. In Proceedings of MobiSys 2003, 31--42. Google ScholarDigital Library
- Gedik, B., and Liu, L. 2005. Location-Privacy in Mobile Systems: A Personalized Anonymization Model. In Proceedings of ICDCS 2005, 620--629. Google ScholarDigital Library
- Mokbel, M.F., Chow, C. and Aref, W.G. 2006. The new casper: query processing for location services without compromising privacy. In Proceedings of VLDB 2006, 763--774. Google ScholarDigital Library
- Kalnis, P., Ghinita, G., Mouratidis, K., and Papadias, D. 2007. Preventing Location-Based Identity Inference in Anonymous Spatial Queries. IEEE Transactions on Knowledge and Data Engineering, Vol 19 No. 12 (Dec 2007), 1719--1733. Google ScholarDigital Library
- Ghinita, G., Kalnis, P., and Skiadopoulos, S. 2007. PRIVÉ: Anonymous Location-Based Queries in Distributed Mobile Systems. In Proceedings of WWW 2007, 371--380. Google ScholarDigital Library
- Smart phone leads market growth: http://www.pcworld.com/businesscenter/article/158697/smart_phones_lead_market_growth.htmlGoogle Scholar
- Zhong, G., and Hengartner, U. 2008. Toward a Distributed k-Anonymity Protocol for Location Privacy. In Proceedings of WPES 2008, 33--37. Google ScholarDigital Library
- Xiong, X., Mokbel, M.F., and Aref, W.G. 2005. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-Temporal Databases. In Proceedings of ICDE 2005, 643--654. Google ScholarDigital Library
- Theodoridis, Y. The R-Tree-Portal. http://ww.rtreeportal.org.Google Scholar
- Chow, C., Mokbel, M., and Liu, X. 2006. A peer-to-peer Spatial Cloaking Algorithm for Anonymous Location-based Services. In Proceedings of ACM-GIS 2006, 171--178. Google ScholarDigital Library
- Krumm, J. 2007. Inference Attacks on Location Tracks. In Proceedings of Pervasive, 2007, 127--143. Google ScholarDigital Library
- Hashem, T., and Kulik, L. 2007. Safeguarding Location Privacy in Wireless Ad-hoc Networks. In Proceedings of Ubicomp, 2007, 372--390. Google ScholarDigital Library
- Ghinita, G., Kalnis, P., Khoshgozraran, A., Shahabi, C., and Tan, K. 2008. Private Queries in Location Based Services: Anonymizers are not Necessary. In Proceedings of SIGMOD 2008, 121--132. Google ScholarDigital Library
- Haque, M., and Ahamed, S.I. 2007. An Omnipresent Formal Trust Model (FTM) for Pervasive Computing Environment. In Proceedings of COMPSAC 2007, 49--56. Google ScholarDigital Library
- Bamba, B., Liu, L., Pesti, P., and Wang, T. 2008. Supporting Anonymous Location Queries in Mobile Environments with PrivacyGrid. In Proceedings of WWW 2008, 327--246. Google ScholarDigital Library
- Hilbert Curve: http://en.wikipedia.org/wiki/Hilbert_curveGoogle Scholar
- Hoh, B., and Gruteser, M. 2005. Protecting Location Privacy Through PathConfusion. In Proceedings of SecureComm 2005, 194--205. Google ScholarDigital Library
- Hengartner, U. 2008. Location Privacy based on Trusted Computing and Secure Logging. In Proceedings of SecureComm 2008. Google ScholarDigital Library
Recommendations
Feeling-based location privacy protection for location-based services
CCS '09: Proceedings of the 16th ACM conference on Computer and communications securityAnonymous location information may be correlated with restricted spaces such as home and office for subject re-identification. This makes it a great challenge to provide location privacy protection for users of location-based services. Existing work ...
An Approach for Ensuring Robust Safeguard against Location Privacy Violation
COMPSAC '10: Proceedings of the 2010 IEEE 34th Annual Computer Software and Applications ConferenceThe challenge of preserving user’s location privacy is more important now than ever before with the proliferation of handheld devices and the pervasive use of location based services. To protect location privacy, we must ensure k-anonymity so that the ...
Resilient Privacy Protection for Location-Based Services through Decentralization
Location-Based Services (LBSs) provide valuable services, with convenient features for mobile users. However, the location and other information disclosed through each query to the LBS erodes user privacy. This is a concern especially because LBS ...
Comments