LPCQP: Lightweight private circular query protocol with divided POI-table and somewhat homomorphic encryption for privacy-preserving k-NN search

With the recent growth of mobile communication, the location-based k-nearest neighbor (k-NN) search is getting much attention. While the k-NN search provides beneficial information about points of interest (POIs) near users, users’ locations could be revealed to the server. Lien et al. have recently proposed a highly-accurate privacypreserving k-NN search protocol with the additive homomorphism. However, it requires a heavy computation load due to the unnecessary multiplication on the server in the encryption domain. In this paper, we propose a lightweight private circular query protocol (LPCQP) with divided POI-table and the somewhat homomorphic encryption for privacypreserving k-NN search. Our proposed scheme removes unnecessary POI information for the request user by dividing and aggregating a POI-table, and this reduces both the computational and the communication costs. In addition, we use both additive and multiplicative homomorphisms to perform the above process in the encryption domain. We evaluate the performance of our proposed scheme and show that our scheme reduces both the computational and the communication costs while maintaining high security and high accuracy.