Enabling Privacy-Preserving Boolean <i>k</i>NN Query Over Cloud-Based Spatial Data

With the rapid development of IoT technology, a vast quantity of spatial data with text information is generated, because of the explosive growth of the spatial data, users usually encrypt these data and outsource them to the cloud for enjoying the storage and computing capability. Privacy-preserving Boolean k Nearest Neighbor (kNN) query is a typical query technique over the spatial data. It finds k objects that exactly match the query keyword and are nearest to the query point upon encrypted spatial data. We propose a scheme which supports the privacy-preserving Boolean kNN query over the cloud-based spatial data in this article. In order to efficiently obtain the spatial objects containing the query keywords, we ask the cloud to pick the objects containing the query keyword with the lowest frequency. Then, the cloud filters out the objects that do not contain other query keywords. Since the number of objects containing the query keyword with the lowest frequency is minimal, the number of objects to filter is also minimal. In this way, the query efficiency is improved. In order to realize convenient and safe distance comparison over the encrypted spatial data, we convert the coordinates to the vectors. The distance between the two points can be expressed as the inner product of the two vectors. Furthermore, we use the enhanced asymmetric scalar-product-preserving encryption algorithm to protect the data privacy. We prove that the proposed scheme satisfies the CQA2-security. Meanwhile, we conduct experiments using the real data sets to show the performance of the proposed scheme.