Protecting Location Privacy Through Path Confusion

TLDR

The work focuses on applications that continuously collect location samples from many users, noting that simply removing identifiers is insufficient because trajectory data can still be used to track individuals. The study presents a path perturbation algorithm designed to maximize users’ location privacy while respecting a quality‑of‑service constraint. The algorithm cross‑paths users in shared locations, formulates the privacy problem as a constrained optimization, and applies heuristics to efficiently compute perturbations. Simulations with randomized movement models show that the algorithm increases path confusion, improving privacy while keeping location perturbation minimal.

Abstract

We present a path perturbation algorithm which can maximize users’ location privacy given a quality of service constraint. This work concentrates on a class of applications that continuously collect location samples from a large group of users, where just removing user identifiers from all samples is insufficient because an adversary could use trajectory information to track paths and follow users’ footsteps home. The key idea underlying the perturbation algorithm is to cross paths in areas where at least two users meet. This increases the chances that an adversary would confuse the paths of different users. We first formulate this privacy problem as a constrained optimization problem and then develop heuristics for an efficient privacy algorithm. Using simulations with randomized movement models we verify that the algorithm improves privacy while minimizing the perturbation of location samples.