Highly Efficient Privacy Preserving Location-Based Services with Enhanced One-Round Blind Filter

To take advantages of location-based services (LBS) while protecting user privacy against untrusted LBS providers, privacy preserving LBS have attracted increasing attention. Considering that users in an LBS system are often equipped with resource-constrained mobile devices, most existing privacy preserving LBS methods are based on anonymization techniques. However, these existing schemes still have some privacy and efficiency limitations. In this paper, we propose a novel privacy preserving LBS scheme, which simultaneously achieves user privacy protection and high query efficiency. Specifically, we utilize the k-anonymity technique and the pseudo random function to protect the location privacy and the query message privacy of users. We design an enhanced one-round blind filter protocol (ORBFe) based on the Paillier cryptosystem to securely filter out redundant records generated by the k-anonymity technique. Compared with existing solutions, our ORBFe protocol not only ensures that users receive exactly satisfying results but also incurs a low computation and communication cost on the server side. Through the theoretical analysis and extensive experiments, we demonstrate the security and efficiency of our proposed scheme.

Automated summary

This paper proposes a novel privacy preserving LBS scheme that utilizes k-anonymity technique and pseudo random function to protect user privacy, and designs an enhanced blind filter protocol based on the Paillier cryptosystem for secure filtering. The proposed scheme ensures user privacy protection and high query efficiency while incurring low computation and communication costs on the server side. Through theoretical analysis and extensive experiments, the security and efficiency of the proposed scheme are demonstrated.