Defining perfect location privacy using anonymization

The popularity of mobile devices and location-based services (LBS) has created great concerns regarding the location privacy of users of such devices and services. Anonymization is a common technique that is often being used to protect the location privacy of LBS users. In this paper, we provide a general information theoretic definition for location privacy. In particular, we define perfect location privacy. We show that under certain conditions, perfect privacy is achieved if the pseudonyms of users are changed before O(N(2/r-1)) observations by the adversary, where N is the number of users and r is the number of sub-regions or locations.