Messages in a Concealed Bottle: Achieving Query Content Privacy With Accurate Location-Based Services

Query privacy has led to a serious concern for location-based services (LBSs). Existing mainstream schemes preserve query privacy by either introducing a third party or degrading the accuracy of LBS. To address these deficiencies, we propose a scheme named the content sealed bottle in this paper for the users to get accurate LBSs while the server learns zero knowledge on the query content. To realize this objective, the Euclidean distance based on homomorphic encryption is used to signal the difference between the query attribute vector of a user and each database attribute vector of the server; then, a Boolean circuit is designed to identify the exact match for the query attribute vector. By optimizing the traditional subcircuits, the total number of non-XOR gates, which is the main cost during the matching process, can be reduced by a factor of l compared to that of the traditional M-to-1 MIN subcircuit, where l is the input bit length of the Boolean circuit. Finally, the computationally private information retrieval technique is employed to privately retrieve the points-of-interest set. To the best of our knowledge, our content sealed bottle is the first scheme that can achieve cost-effective query privacy preservation without the involvement of a third party or sacrificing the accuracy of LBSs. Our security analysis and extensive experimental results demonstrate the effectiveness of the proposed scheme.