Privacy-Preserving Spatial Query Protocol Based on the Moore Curve for Location-Based Service

Abstract The cloud computing has attracted a multitude of data owners to outsource computing to and acquire location-based services from cloud service providers. The privacy-preserving spatial query on outsourced data has become a research hotspot in the location-based service. The existing schemes may damage the confidentiality of data, or be trapped by the large computation and communication overhead. The majority of them focus on the protection of original data and location information, while ignoring the significance of query records. In order to find a balance between security, efficiency and accuracy, this paper proposes a spatial transformation scheme for location-based services in outsourced environment, and designs a privacy-preserving k-nearest neighbor (k-NN) protocol. We utilize the Moore curve to perform a one-way transformation of the original data, and adopt the encryption technology to prevent malicious access of the transformed data by untrusted entities. The proposed protocol accomplishes efficient and accurate k-NN query in the transformed space while guaranteeing the confidentiality of outsourced data and the user's location. In addition, we propose a security optimized approach based on the oblivious transfer to protect the privacy of query records. Performance analysis shows that the proposed protocol has considerable efficiency advantage over existing schemes without sacrificing security and accuracy.