A practical privacy-preserving nearest neighbor searching method over encrypted spatial data

To realize the great flexibility and cost savings for providing location-based service, data owners are incentivized to migrate their data to cloud servers. However, direct data outsourcing to untrusted servers may pose significant privacy risks. This paper proposes a practical privacy-preserving nearest neighbor searching method over encrypted spatial data. We simultaneously protect data and location privacy (access and pattern privacy) by encrypting data using asymmetric scalar-product-preserving encryption (ASPE) and performing computational private information retrieval (CPIR) on encrypted subspace datasets. To mitigate the performance degradation introduced by the combination of ASPE and CPIR, we propose a hierarchical index that enables users to safely obtain encrypted subspace datasets with configurable privacy, where different degrees of privacy can be traded off against query processing performance. Experiments demonstrate that our method outperforms the state-of-the-art method in efficiency while allowing for a flexible trade-off between performance and privacy.