Nearest neighbor search with strong location privacy
Open Access
- 1 September 2010
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 3 (1-2) , 619-629
Abstract
The tremendous growth of the Internet has significantly reduced the cost of obtaining and sharing information about individuals, raising many concerns about user privacy. Spatial queries pose an additional threat to privacy because the location of a query may be sufficient to reveal sensitive information about the querier. In this paper we focus on k nearest neighbor ( k NN) queries and define the notion of strong location privacy , which renders a query indistinguishable from any location in the data space. We argue that previous work fails to support this property for arbitrary k NN search. Towards this end, we introduce methods that offer strong location privacy, by integrating private information retrieval (PIR) functionality. Specifically, we employ secure hardware-aided PIR, which has been proven very efficient and is currently considered as a practical mechanism for PIR. Initially, we devise a benchmark solution building upon an existing PIR-based technique. Subsequently, we identify its drawbacks and present a novel scheme called AHG to tackle them. Finally, we demonstrate the performance superiority of AHG over our competitor, and its viability in applications demanding the highest level of privacy.Keywords
This publication has 18 references indexed in Scilit:
- Location privacy: going beyond K-anonymity, cloaking and anonymizersKnowledge and Information Systems, 2010
- Private queries in location based services2008
- Private Information Retrieval Using Trusted Hardware2006
- Preserving User Location Privacy in Mobile Data Management Infrastructures2006
- An anonymous communication technique using dummies for location-based services2005
- Location Privacy in Mobile Systems: A Personalized Anonymization Model2005
- A Formal Model of Obfuscation and Negotiation for Location Privacy2005
- Single-Database Private Information Retrieval with Constant Communication Rate2005
- Simulation of Obfuscation and Negotiation for Location PrivacyLecture Notes in Computer Science, 2005
- Analysis of the clustering properties of the Hilbert space-filling curveIEEE Transactions on Knowledge and Data Engineering, 2001