Transition-Entropy: A Novel Metric for Privacy Preservation in Location-Based Services

The advent of location-based services has created the need for preserving the location privacy of users. An adversary such as an untrusted location-based server can monitor the queried locations by a user to infer sensitive information such as the user’s home address, health conditions, shopping habits, etc. To address this issue, dummy-based algorithms have been developed to increase the anonymity of users, and thus, protecting their privacy. Unfortunately, the existing algorithms only consider a limited amount of side information known by the adversary whereas they may face more serious challenges in practice. In this paper, we consider a new type of side information based on consecutive location changes of users, and propose a new metric called transition-entropy to investigate the location privacy preservation. Furthermore, we develop a greedy algorithm to significantly improve the transition-entropy performance for a given dummy generation algorithm. Via experiments conducted on a real-life dataset, we evaluate the performance of the proposed metric and algorithm.