An Effective Privacy Architecture to Preserve User Trajectories in Reward-Based LBS Applications

A. S. M. Touhidul Hasan, Qiang Qu, Chengming Li, Lifei Chen, Qingshan Jiang

TL;DR

This paper introduces a novel client-server privacy architecture and a "bounded perturbation" technique to anonymize user trajectories in reward-based Location-Based Services (LBS) applications. This approach effectively protects user privacy by preventing inference and linking attacks while preserving the utility of the trajectory data for applications like targeted advertising.

What Problem Does This Paper Address?

Reward-based LBS applications, which incentivize users for activities like fitness tracking, collect detailed user trajectories (sequences of locations over time). While beneficial for employers and insurance companies (e.g., reducing healthcare costs), this data poses a significant privacy risk. Identified trajectories can reveal sensitive information like points of interest, daily routines, and social connections, making users vulnerable to inference and linking attacks. Existing privacy mechanisms often fail to preserve data utility when anonymizing trajectories, creating a trade-off between privacy and usefulness. This paper aims to bridge this gap by proposing a method that anonymizes trajectories effectively without sacrificing their practical value.

Methods

The core of the proposed solution is a client-server privacy architecture. The anonymization process occurs at the client-side (intermediary device) before data is sent to the central server. The key innovation is the bounded perturbation technique. Unlike traditional perturbation methods that add random noise which can result in unrealistic locations (e.g., in a lake), bounded perturbation incorporates a Global Location Set (GLS). The GLS, derived from OpenStreetMap, represents all valid points of interest in a region. When generating anonymized locations, the perturbation is bounded within this GLS, ensuring that the generated points are plausible and maintain data utility. The process involves:

  1. Generating a Global Location Set (GLS): This is done by the central server, defining valid locations within a specified geographical area.
  2. Anonymizing Trajectories: At the client-side, identified trajectory points are perturbed by adding random noise. However, this noise is constrained such that the resulting points fall within the GLS. Map matching techniques are used to ensure the generated points are valid.
  3. Excluding Original Locations: The anonymization process also aims to remove original visited locations from the perturbed trajectory to further obscure user patterns.

Datasets

The experiments were conducted using the Geolife dataset [36,37]. This dataset comprises 17,621 identified trajectories from 182 users over three years, collected at five-second intervals when the user's speed exceeded 3.0 miles per hour. The authors also utilized OpenStreetMap API [34] to construct the Global Location Set.

Key Insights and Ideas

  • The "bounded" aspect is crucial: Simply adding random noise to trajectories can create unrealistic locations, severely impacting data utility. By constraining the perturbation within a predefined set of valid locations (GLS), the authors ensure that the anonymized data remains meaningful for analysis.
  • Client-side anonymization is key: Performing anonymization on the user's device before data transmission enhances privacy by preventing raw trajectory data from ever reaching the central server.
  • GLS as a privacy-utility bridge: The Global Location Set acts as a critical component, defining the "space of possibility" for anonymized locations, thus balancing privacy guarantees with the need for data utility.
  • Beyond identity: trajectory privacy matters: The paper emphasizes that for LBS applications, protecting the trajectory itself (points of interest, routes) is as important as protecting the user's identity.

Key Results

  • The proposed bounded perturbation method successfully anonymizes trajectory points, preventing privacy breaches through inference and linking attacks.
  • Experimental results demonstrated that the bounded perturbation method preserves more data utility compared to traditional perturbation methods.
  • Specifically, the average relative distortion for individual Points of Interest (Pols) was significantly lower with bounded perturbation (0.206) compared to perturbation (0.486).
  • Similarly, the average relative distortion for visiting users was better in the morning (0.241 vs. 0.561) and evening (0.280 vs. 0.527) sessions for bounded perturbation.
  • The anonymized trajectories could still be used by advertising companies to identify crowded spots for billboard placement, indicating preserved utility.

Limitations and Future Work

  • Local Anonymization: The authors acknowledge that the current anonymization process is client-server based. They aim to improve this by completing the anonymization process locally in the future.
  • Other Data Properties: The collected data from reward-based LBS applications may contain properties beyond trajectories that could also raise privacy concerns. Future work will involve extending the privacy protection to these various data attributes.

Summary updated

Abstract

How can training performance data (e.g., running or walking routes) be collected, measured, and published in a mobile program while preserving user privacy? This question is becoming important in the context of the growing use of reward-based location-based service (LBS) applications, which aim to promote employee training activities and to share such data with insurance companies in order to reduce the healthcare insurance costs of an organization. One of the main concerns of such applications is the privacy of user trajectories, because the applications normally collect user locations over time with identities. The leak of the identified trajectories often results in personal privacy breaches. For instance, a trajectory would expose user interest in places and behaviors in time by inference and linking attacks. This information can be used for spam advertisements or individual-based assaults. To the best of our knowledge, no existing studies can be directly applied to solve the problem while keeping data utility. In this paper, we identify the personal privacy problem in a reward-based LBS application and propose privacy architecture with a bounded perturbation technique to protect user’s trajectory from the privacy breaches. Bounded perturbation uses global location set (GLS) to anonymize the trajectory data. In addition, the bounded perturbation will not generate any visiting points that are not possible to visit in real time. The experimental results on real-world datasets demonstrate that the proposed bounded perturbation can effectively anonymize location information while preserving data utility compared to the existing methods.
BibTeX
@article{hasan2018effective,
  author = {A. S. M. Touhidul Hasan and Qiang Qu and Chengming Li and Lifei Chen and Qingshan Jiang},
  title = {{An Effective Privacy Architecture to Preserve User Trajectories in Reward-Based LBS Applications}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2018},
  doi = {10.3390/ijgi7020053},
}
Figure