Privacy-preserving nearest neighbor queries using geographical features of cellular networks

Although location-based services (LBSes), such as nearest neighbor query, have become popular, privacy remains a challenging issue for users. Many privacy preserving techniques have been proposed, but their complexity, insufficiency, and time consumption make them unattractive to users, who prefer accuracy and quickness. To address this limitation, we introduce a framework to protect user privacy for nearest neighbor queries by utilizing the basic geographical features of cellular networks. In the proposed framework, we provide two layers of spatial anonymity such that the user's location is not directly provided to a location service provider. Based on the features of the cellular network (e.g., LTE) at the first layer, the user's location is kept hidden under the cloaking of the base station (eNB) that provides a network connectivity to serve the user (SeNB). At the second layer, we anonymize SeNB in a group of dummy locations neighboring a central eNB (CeNB), all of which have the same query probability. Unlike most existing approaches with faked dummy locations, the proposed framework depends on real locations of eNBs to minimize the likelihood that side information might be exposed to an adversary. Moreover, our model is motivated by the practicality of employing the ubiquity of cellular networks and their geographical features. The simulation results show that the proposed scheme can achieve a decent degree of accuracy (> 98%) while providing strong privacy guarantees.