Privacy games along location traces: a game-theoretic framework for optimizing location privacy

The mainstream approach to protecting the privacy of mobile users in location-based services (LBSs) is to alter (e.g., perturb, hide, etc.) the users' actual locations in order to reduce the exposed sensitive information. In order to be effective, a location-privacy preserving mechanism must consider both the privacy and utility requirements of each user, as well as their overall exposed locations (which contribute to the adversary's background knowledge). In this paper, we propose a methodology that enables the design of optimal user-centric location obfuscation mechanisms respecting each individual user's service quality requirements, while maximizing the expected error that the optimal adversary incurs in reconstructing the user's actual trace. A key advantage of a user-centric mechanism is that it does not depend on third party proxies or anonymizers, and so it can be directly integrated in the mobile devices that users use to access LBSs. Our methodology is based on the mutual optimization of user/adversary objectives (maximizing location privacy vs. minimizing localization error) formalized as a Stackelberg Bayesian game. This formalization makes our solution robust against any location inference attack, i.e., the adversary cannot decrease the user's privacy by designing a better inference algorithm as long as the obfuscation mechanism is designed according to our privacy games. We develop two linear programs that solve the location privacy game and output the optimal obfuscation strategy and its corresponding optimal inference attack. These linear programs are used to design location privacy-preserving mechanisms that consider the correlation between past, current and future locations of the user, thus can be tuned to protect different privacy objectives along the user's location trace. We illustrate the efficacy of the optimal location privacy-preserving mechanisms obtained with our approach against real location traces, showing their performance in protecting users' different location privacy objectives