Quantifying the Effect of Co-location Information on Location Privacy

Alexandra-Mihaela Olteanu, Kévin Huguenin, Reza Shokri, Jean-Pierre HubauxPrivacy Enhancing Technologies 2014 · DOI

TL;DR

This paper introduces a framework to quantify how sharing co-location information (e.g., tagging friends in photos or check-ins) on social networks degrades users' location privacy. They develop and evaluate methods for adversaries to exploit this information, showing that even partial co-location data can significantly reduce privacy.

What Problem Does This Paper Address?

In today's world, mobile devices and location-based services are ubiquitous. While these services offer convenience, they also raise significant privacy concerns. Users often share their locations, and increasingly, they also share information about who they are with (co-location). This co-location data, whether explicitly shared (e.g., tagging friends) or implicitly inferred (e.g., from shared Wi-Fi or photo metadata), can be a powerful tool for adversaries to infer a user's true location. Existing research has focused on location privacy in isolation or on social network privacy separately. This paper bridges this gap by specifically investigating how co-location information, derived from social relationships, impacts location privacy, even when users employ standard location obfuscation techniques.

Methods

The authors formalize the problem of location privacy in the presence of co-location information. They model an adversary (e.g., a social network operator) who has access to users' reported locations and co-locations, as well as their mobility profiles.

  • Optimal Localization Attack: They first develop an optimal inference algorithm that jointly considers the locations of all users connected through co-locations. This approach, based on a Hidden Markov Model (HMM) and the forward-backward algorithm, is computationally intractable for more than a few users due to the exponential growth of the state space (MN, where N is the number of users and M is the number of regions).
  • Approximate Localization Attacks (Heuristics): To address the complexity issue, they propose two polynomial-time heuristics:
  • Heuristic 1: Limited User Set Approximation: This method focuses on a small subset of users (the "co-targets") who have the most reported co-locations with the target user. An optimal attack is then performed on this reduced set.
  • Heuristic 2: Independence Approximation: This heuristic ignores the mobility profiles of co-located users and treats their reported locations as if the target user had reported them. This simplifies the inference by decoupling the temporal dependencies.

Datasets

The evaluation uses a real-world mobility dataset from the Microsoft Research Asia GeoLife project. This dataset consists of GPS traces from 182 users over three years, with a significant portion concentrated in Beijing, China. The authors processed this data by:

  • Space Discretization: Partitioning a ~4.4 km x 4.4 km area in Beijing into a 5x5 grid of 25 regions.
  • Time Discretization: Splitting continuous time into one-hour intervals.

Since the dataset did not contain explicit co-location information, they generated synthetic co-locations by considering users to be co-located if their discretized actual locations were the same. They then used a proportion (w) of these synthetic co-locations in their experiments.

Key Insights and Ideas

  • Co-location is a significant privacy threat: Even when users attempt to protect their privacy through obfuscation, sharing co-location information with even a single friend can drastically reduce their location privacy.
  • Loss of control: A user's privacy is no longer solely in their hands. Information disclosed by others, particularly through co-locations, can significantly compromise an individual's privacy, even if the individual reveals nothing about themselves.
  • Social context matters: The paper highlights the crucial link between social relationships and location privacy, demonstrating that understanding these social connections is vital for effective privacy protection.
  • Heuristics offer a practical trade-off: While the optimal attack is computationally infeasible, the proposed heuristics provide a practical way to quantify and exploit co-location information for localization attacks, offering a good balance between accuracy and computational cost.

Key Results

  • Significant Privacy Loss: Even when an adversary considers co-locations with only a single friend, a user's location privacy can decrease by up to 75% in typical settings.
  • Indirect Privacy Impact: If a user does not disclose any location information, their privacy can still decrease by up to 16% due to information reported by other users.
  • Heuristic Performance: The second heuristic (Independence Approximation), which considers all co-locations, generally outperforms the first heuristic (Limited User Set Approximation) in terms of privacy loss for the adversary, despite having a lower computational cost for larger N.
  • Obfuscation Effectiveness: While obfuscation helps, it does not fully mitigate the privacy loss caused by co-location information. The privacy loss is generally higher when users do not obfuscate their locations.

Limitations and Future Work

  • Synthetic Co-locations: The use of synthetic co-locations, rather than real-world reported co-locations, means the experimental results might not perfectly reflect real-world scenarios.
  • Small User Set: The evaluation was conducted on a small set of 5 users, which may not be representative of larger populations.
  • Limited Grid Size: The 5x5 grid for space discretization is relatively small.

The authors suggest future work including:

  • Collecting large-scale datasets from actual social networks.
  • Running experiments on larger grids.
  • Designing social-aware location-privacy protection mechanisms that generalize information about co-located users (e.g., by indicating social ties rather than specific names) or generalize time and location information to mitigate these attacks.

Summary updated

BibTeX
@inproceedings{olteanu2014quantifying,
  author = {Alexandra-Mihaela Olteanu and Kévin Huguenin and Reza Shokri and Jean-Pierre Hubaux},
  title = {{Quantifying the Effect of Co-location Information on Location Privacy}},
  booktitle = {Privacy Enhancing Technologies},
  year = {2014},
  doi = {10.1007/978-3-319-08506-7\_10},
}
Figure