One-Time, Oblivious, and Unlinkable Query Processing Over Encrypted Data on Cloud

Location-based services (LBSs) are widely deployed in commercial services. These services always depend on a service provider, e.g., a cloud server, to store the enormous amounts of geospatial data and to process various queries. For example, a Yelp user can retrieve a list of recommended cafés by submitting her/his current location to the service provider. While LBSs offer tremendous benefits, it is vital to safeguard users’ privacy against untrusted service providers. However, no prior secure k nearest neighbor query processing schemes satisfy the three security requirements of one-time, oblivious, and unlinkable. In particular, we are concerned with the problem of item exclusion: how to match one data query with each item on the cloud no more than once in an oblivious and unlinkable manner. In this paper, we propose the first secure k nearest neighbor query processing scheme, Obaq, that satisfies the above requirements. Obaq first introduces an item identifier into an existing secure k nearest neighbor query processing scheme. Each data owner inserts an item identifier and her/his location information into a secure index, and each data user transfers the identifier of a previously received data item and location information into a specific range. Then, Obaq excludes corresponding items via privacy-preserving range querying. We define strong index privacy and strong token privacy and formally prove the security of Obaq in the random oracle model. We further evaluate the performance of Obaq using a prototype and a real-world dataset. The experimental results show that Obaq is highly efficient and practical in terms of computational cost, communication overhead, and response delay.