Location Privacy amidst Local Eavesdroppers

Mobile social networks and location-aware applications are becoming more and more widespread in current wireless networks. Thanks to WiFi or Bluetooth-enabled devices, everyday mobile users can enjoy new services. However, the deployment of these mobile technologies leads to many concerns for privacy, especially location privacy. In wireless networks, external malicious parties can monitor pseudonyms used for identification to learn mobile users' location and track their movements. A common technique for protecting location privacy consists in changing pseudonyms in regions called mix zones. In this report, we present a game-theoretic approach to evaluate the interaction and behaviors of an attacker aiming to jeopardize mobile nodes' location privacy and nodes willing to thwart adversary's spiteful plans. Assuming that such an attacker is armed with local eavesdropping devices, he must deploy them in an efficient way to track as many nodes as possible. On the other hand, mobile users have to define where are the best places to locate their mix zones. In order to evaluate their potential benefit, mobile nodes need to know the mixing effectiveness of possible mix zone locations. We propose a simplified metric based on the mobility profiles to determine the location privacy achieved with mix zones. We also build a payoff model to deal with costs, as well as benefits, led by this extended hide-and-seek game. By means of analytical and numerical results, we show the existence of Nash equilibria for all values of players' costs and mobility parameters. We prove that the adversary's best behavior evolves regarding the benefit he gets from traffic sniffing and the cost led by deployment of eavesdropping stations. On the other hand, we show that, when the mobility profile is homogeneous, the mobile nodes' best response is independent of the adversary's deployment of sniffing stations. Furthermore, the nodes' best response is only dependent on the number of mix zones they deploy, not on their particular locations.

On Non-cooperative Location Privacy: A Game-theoretic Analysis

Julien Freudiger, Jean-Pierre Hubaux, David C. Parkes

In mobile networks, authentication is a required primitive of the majority of security protocols. However, an adversary can track the location of mobile nodes by monitoring pseudonyms used for authentication. A frequently proposed solution to protect location privacy suggests that mobile nodes collectively change their pseudonyms in regions called mix zones. Because this approach is costly, self-interested mobile nodes might decide not to cooperate and could thus jeopardize the achievable location privacy. In this paper, we analyze the non-cooperative behavior of mobile nodes with a game-theoretic model, where each player aims at maximizing its location privacy at a minimum cost. We first analyze the Nash equilibria in

n

-player complete information games. Because mobile nodes in a privacy-sensitive system do not know their opponents' payoffs, we then consider incomplete information games. We establish that symmetric Bayesian-Nash equilibria exist with simple threshold strategies in

n

-player games and derive the equilibrium strategies. By means of numerical results, we show that mobile nodes become selfish when the cost of changing pseudonym is small, whereas they cooperate more when the cost of changing pseudonym increases. Finally, we design a protocol - the PseudoGame protocol - based on the results of our analysis.

2009

When Whereabouts is No Longer Thereabouts

Julien Freudiger

Modern mobile devices are fast, programmable and feature localization and wireless capabilities. These technological advances notably facilitate mobile access to Internet, development of mobile applications and sharing of personal information, such as location information. Cell phone users can for example share their whereabouts with friends on online social networks. Following this trend, the field of ubiquitous computing foresees communication networks composed of increasingly inter-connected wireless devices offering new ways to collect and share information in the future. It also becomes harder to control the spread of personal information. Privacy is a critical challenge of ubiquitous computing as sharing personal information exposes users' private lives. Traditional techniques to protect privacy in wired networks may be inadequate in mobile networks because users are mobile, have short-lived encounters and their communications can be easily eavesdropped upon. These characteristics introduce new privacy threats related to location information: a malicious entity can track users' whereabouts and learn aspects of users' private lives that may not be apparent at first. In this dissertation, we focus on three important aspects of location privacy: location privacy threats, location-privacy preserving mechanisms, and privacy-preservation in pervasive social networks. Considering the recent surge of mobile applications, we begin by investigating location privacy threats of location-based services. We push further the understanding of the privacy risk by identifying the type and quantity of location information that statistically reveals users' identities and points of interest to third parties. Our results indicate that users are at risk even if they access location-based services episodically. This highlights the need to design privacy into location-based services. In the second part of this thesis, we delve into the subject of privacy-preserving mechanisms for mobile ad hoc networks. First, we evaluate a privacy architecture that relies on the concept of mix zones to engineer anonymity sets. Second, we identify the need for protocols to coordinate the establishment of mix zones and design centralized and distributed approaches. Because individuals may have different privacy requirements, we craft a game-theoretic model of location privacy to analyze distributed protocols. This model predicts strategic behavior of rational devices that protects their privacy at a minimum cost. This prediction leads to the design of efficient privacy-preserving protocols. Finally, we develop a dynamic model of interactions between mobile devices in order to analytically evaluate the level of privacy provided by mix zones. Our results indicate the feasibility and limitations of privacy protection based on mix zones. In the third part, we extend the communication model of mobile ad hoc networks to explore social aspects: users form groups called "communities" based on interests, proximity, or social relations and rely on these communities to communicate and discover their context. We analyze using challenge-response methodology the privacy implications of this new communication primitive. Our results indicate that, although repeated interactions between members of the same community leak community memberships, it is possible to design efficient schemes to preserve privacy in this setting. This work is part of the recent trend of designing privacy protocols to protect individuals. In this context, the author hopes that the results obtained, with both their limitations and their promises, will inspire future work on the preservation of privacy.

EPFL2011

Collaborative Location Privacy with Rational Users

Francisco De Meneses Neves Ramos Dos Santos, Jean-Pierre Hubaux, Mathias Jacques Jean-Marc Humbert, Reza Shokri

Recent smartphones incorporate embedded GPS devices that enable users to obtain geographic information about their surroundings by providing a location-based service (LBS) with their current coordinates. However, LBS providers collect a significant amount of data from mobile users and could be tempted to misuse it, by compromising a customer's location privacy (her ability to control the information about her past and present location). Many solutions to mitigate this privacy threat focus on changing both the architecture of location-based systems and the business models of LBS providers. MobiCrowd does not introduce changes to the existing business practices of LBS providers, rather it requires mobile devices to communicate wirelessly in a peer-to-peer fashion. To lessen the privacy loss, users seeking geographic information try to obtain this data by querying neighboring nodes, instead of connecting to the LBS. However, such a solution will only function if users are willing to share regional data obtained from the LBS provider. We model this collaborative location-data sharing problem with rational agents following threshold strategies. Initially, we study agent cooperation by using pure game theory and then by combining game theory with an epidemic model that is enhanced to support threshold strategies to address a complex multi-agent scenario. From our game-theoretic analysis, we derive cooperative and non-cooperative Nash equilibria and the optimal threshold that maximizes agents' expected utility.

Springer-Verlag Berlin2011