Messages in a Concealed Bottle: Achieving Query Content Privacy With Accurate Location-Based Services
Qin Hu, Shengling Wang, Chunqiang Hu, Jianhui Huang, Wei Li, Xiuzhen Cheng · IEEE Transactions on Vehicular Technology · 2018
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 namedthe content sealed bottlein 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 oflcompared to that of the traditionalM-to-1 MIN subcircuit, wherelis 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, ourcontent sealed bottleis 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.