Visible to the public Limits of location privacy under anonymization and obfuscation

TitleLimits of location privacy under anonymization and obfuscation
Publication TypeConference Paper
Year of Publication2017
AuthorsTakbiri, N., Houmansadr, A., Goeckel, D. L., Pishro-Nik, H.
Conference Name2017 IEEE International Symposium on Information Theory (ISIT)
Date Publishedjun
Keywordsanonymization, anonymization-based LBS systems, Computing Theory, data privacy, general Markov Chain model, Human Behavior, human factor, Information Theoretic Privacy, Information theory, Location Based Service (LBS), location privacy, Location Privacy Protecting Mechanism (LPPM), location-based services, Markov chain, Markov processes, Measurement, mobile computing, mobile devices, obfuscation, privacy, pubcrawl, resilience, Resiliency, Scalability, statistical analysis, Time series analysis

The prevalence of mobile devices and location-based services (LBS) has generated great concerns regarding the LBS users' privacy, which can be compromised by statistical analysis of their movement patterns. A number of algorithms have been proposed to protect the privacy of users in such systems, but the fundamental underpinnings of such remain unexplored. Recently, the concept of perfect location privacy was introduced and its achievability was studied for anonymization-based LBS systems, where user identifiers are permuted at regular intervals to prevent identification based on statistical analysis of long time sequences. In this paper, we significantly extend that investigation by incorporating the other major tool commonly employed to obtain location privacy: obfuscation, where user locations are purposely obscured to protect their privacy. Since anonymization and obfuscation reduce user utility in LBS systems, we investigate how location privacy varies with the degree to which each of these two methods is employed. We provide: (1) achievability results for the case where the location of each user is governed by an i.i.d. process; (2) converse results for the i.i.d. case as well as the more general Markov Chain model. We show that, as the number of users in the network grows, the obfuscation-anonymization plane can be divided into two regions: in the first region, all users have perfect location privacy; and, in the second region, no user has location privacy.

Citation Keytakbiri_limits_2017