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

Abstract

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 <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -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 <inline-formula><tex-math notation="LaTeX">$_e$</tex-math></inline-formula> ) based on the Paillier cryptosystem to securely filter out redundant records generated by the <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -anonymity technique. Compared with existing solutions, our ORBF <inline-formula><tex-math notation="LaTeX">$_e$</tex-math></inline-formula> 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.