Highly Efficient Privacy Preserving Location-Based Services with Enhanced One-Round Blind Filter
Xingxin Li, Youwen Zhu, Jian Wang · IEEE Transactions on Emerging Topics in Computing · 2019
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 (ORBF$_e$) based on the Paillier cryptosystem to securely filter out redundant records generated by the$k$-anonymity technique. Compared with existing solutions, our ORBF$_e$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.