Privacy Preserving Nearest Neighbor Search based on Topologies in Cellular Networks

As the popularity of location-based services (LBSes) is increasing, the location privacy has become a main concern. Among the rich collection of location privacy techniques, the spatial cloaking is one of the most popular techniques. In this paper, we propose a new spatial cloaking technique to hide a user's location under a cloaking of the serving base station (SeNB) and anonymize SeNB with a group of dummy locations in the neighboring group of another base station as central eNB (CeNB). Unlike the most existing approaches for selecting a dummy location, such as the center of a virtual circle, we select a properly chosen dummy location from real locations of eNBs to minimize side information for an adversary. Our experimental results show that the proposed scheme can achieve a reasonable degree of accuracy (>96%) for nearest neighbor services while providing a high level of location privacy.