Updatable privacy-preserving $\textit{K}$-nearest neighbor query in location-based s-ervice
- 7 January 2022
- journal article
- research article
- Published by Springer Nature in Peer-to-Peer Networking and Applications
- Vol. 15 (2) , 1076-1089
Abstract
The \(\textit{K}\)-nearest neighbor (\(\textit{K}\)-NN) query is an important query in location-based service (LBS), which can query the nearest k points to a given point, and provide some convenient services such as interest recommendations. Hence the privacy protection issue of \(\textit{K}\)-NN query has been a popular research area, protecting the information of queries and the queried results, especially in the information era. However, most of existing schemes fail to consider the privacy protection of location points already stored on servers. Or some schemes support no update of location points. In this paper, we present an updatable and privacy-preserving \(\textit{K}\)-NN query scheme to address the above two issues. Concretely, our scheme utilizes the \(\textit{K}\)D-tree (\(\textit{K}\)-Dimensional tree) to store the location points of data owners in location service provider and encrypts the points with a distributed double-trapdoor public-key cryptosystem. Then, based on the Ciphertext Comparison Protocol and Ciphertext Euclidean Distance Calculation Protocol, our scheme can protect the privacy of location and query contents. Experimental analyses show our proposal supports some new location points for a fixed location service provider. Moreover, the queried results show a high accuracy of more than 95%.
Keywords
Funding Information
- National Natural Science Foundation of China (U19B2021, 61972457)
- Key Research and Development Program of Shaanxi (2020ZDLGY08-04)
This publication has 21 references indexed in Scilit:
- A Novel Privacy Preserving Location-Based Service Protocol With Secret Circular Shift for $k$-NN SearchIEEE Transactions on Information Forensics and Security, 2013
- Supporting anonymous location queries in mobile environments with privacygrid2008
- AnonySense: Opportunistic and Privacy-Preserving Context Collection2008
- Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy2007
- Inference Attacks on Location Tracks2007
- Polylogarithmic Private Approximations and Efficient Matching2006
- Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking2003
- A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications2003
- Location privacy in pervasive computingIEEE Pervasive Computing, 2003
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACYInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002