Practical k nearest neighbor queries with location privacy
- 1 March 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 640-651
Abstract
In mobile communication, spatial queries pose a serious threat to user location privacy because the location of a query may reveal sensitive information about the mobile user. In this paper, we study k nearest neighbor (kNN) queries where the mobile user queries the location-based service (LBS) provider about k nearest points of interest (POIs) on the basis of his current location. We propose a solution for the mobile user to preserve his location privacy in kNN queries. The proposed solution is built on the Paillier public-key cryptosystem and can provide both location privacy and data privacy. In particular, our solution allows the mobile user to retrieve one type of POIs, for example, k nearest car parks, without revealing to the LBS provider what type of points is retrieved. For a cloaking region with n×n cells and m types of points, the total communication complexity for the mobile user to retrieve a type of k nearest POIs is O(n+m) while the computation complexities of the mobile user and the LBS provider are O(n + m) and O(n 2 m), respectively. Compared with existing solutions for kNN queries with location privacy, our solutions are more efficient. Experiments have shown that our solutions are practical for kNN queries.Keywords
This publication has 17 references indexed in Scilit:
- Nearest neighbor search with strong location privacyProceedings of the VLDB Endowment, 2010
- Private queries in location based services2008
- Supporting anonymous location queries in mobile environments with privacygrid2008
- A Survey of Single-Database Private Information Retrieval: Techniques and Applications2007
- An anonymous communication technique using dummies for location-based services2005
- Preserving mobile customer privacy2005
- Preserving privacy in environments with location-based applicationsIEEE Pervasive Computing, 2003
- Location privacy in pervasive computingIEEE Pervasive Computing, 2003
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACYInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002
- Public-Key Cryptosystems Based on Composite Degree Residuosity Classes1999