Updatable privacy-preserving K-nearest neighbor query in location-based s-ervice

The K-nearest neighbor (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 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 K-NN query scheme to address the above two issues. Concretely, our scheme utilizes the KD-tree (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%.