TL;DR
This paper introduces a new framework, PriSTE, to protect "spatiotemporal event privacy" in location-based services. It addresses the limitations of existing methods that only protect individual locations or trajectories, by defining and quantifying privacy for complex user activities over space and time, and provides a method to adapt existing location privacy mechanisms to achieve this new goal.
What Problem Does This Paper Address?
Location-Based Services (LBS) rely on users sharing their location data, which raises significant privacy concerns. While existing Location Privacy-Preserving Mechanisms (LPPMs) aim to protect users' location privacy, they often focus on safeguarding individual points or entire trajectories. However, users' sensitive information often lies in their spatiotemporal events – patterns of activity that combine location and time. Examples include "visiting the hospital last week" or "regularly commuting between home and work." Current LPPMs may fail to protect these complex events, even if they adequately anonymize individual locations or trajectories. This paper tackles this gap by formally defining spatiotemporal events and proposing a robust privacy metric and a framework to ensure their privacy.
Methods
The authors introduce several key methodological contributions:
- Formal Definition of Spatiotemporal Events: They define spatiotemporal events as Boolean expressions of location-time predicates (e.g., "user is at location X at time T"). This allows for flexible and customizable privacy specifications.
- ε-Spatiotemporal Event Privacy Metric: Inspired by differential privacy, they define a new privacy metric that quantifies the indistinguishability between a spatiotemporal event occurring and not occurring, given observations. This metric is independent of adversaries' prior knowledge.
- Efficient Quantification Algorithms: A significant challenge is the computational complexity of quantifying privacy for complex events. The authors propose a novel "two-possible-world" method to efficiently compute prior and joint probabilities of spatiotemporal events, overcoming exponential complexity. This involves modeling the system with augmented transition matrices that encode the event's presence or absence.
- PriSTE Framework: This framework acts as a wrapper around existing LPPMs. It quantifies the privacy leakage of an LPPM for a given spatiotemporal event and, if privacy is insufficient, calibrates the LPPM's parameters (specifically, the emission matrix) to meet the desired privacy level. This calibration is done greedily by adjusting the privacy budget.
- Privacy Checking with Arbitrary Initial Probability: They extend their framework to guarantee privacy against adversaries with any prior knowledge of the user's initial location distribution by formulating the problem as a quadratic programming problem.
Datasets
- Geolife Dataset: A real-life dataset collected from 182 users over three years, containing latitude, longitude, and timestamp information. This dataset was used to train transition matrices.
- Synthetic Datasets: Generated datasets were used to simulate user trajectories and transition probability matrices, allowing for controlled experiments with varying parameters like map size, distance-based transition probabilities, and event characteristics.
Key Insights and Ideas
- Spatiotemporal Events are a Crucial Privacy Concern: The paper highlights that protecting individual locations or trajectories is insufficient; the privacy of complex spatiotemporal activities is equally, if not more, important.
- Orthogonality of Privacy Goals: Spatiotemporal event privacy is shown to be orthogonal to traditional location or trajectory privacy. An LPPM good for one might not be good for the other, necessitating specific solutions.
- "Two-Possible-World" Method is Key: This technique is central to overcoming the computational intractability of quantifying privacy for complex Boolean expressions of events.
- LPPM Calibration is Necessary: Existing LPPMs, while useful for location privacy, often require calibration (e.g., reducing their privacy budget) to adequately protect spatiotemporal events.
- Trade-offs Exist: Achieving higher spatiotemporal event privacy often comes at the cost of reduced data utility (e.g., more perturbed locations, higher Euclidean distance) or increased computation time.
Key Results
- Quantification of Privacy Leakage: The paper demonstrates that state-of-the-art LPPMs often provide inadequate protection for spatiotemporal events.
- PriSTE Framework Effectiveness: Experiments show that the PriSTE framework can successfully adapt existing LPPMs (like Laplace Planar Mechanism) to achieve ε-spatiotemporal event privacy.
- Efficiency: The proposed quantification algorithms have linear or polynomial complexity with respect to event length and width, respectively, making them practical.
- Runtime Performance: PriSTE's runtime scales linearly with event length and polynomially with event width, significantly outperforming baseline methods that exhibit exponential scaling.
- Utility vs. Privacy Trade-off: The experiments illustrate the inherent trade-off between privacy protection (lower ε, smaller privacy budget) and data utility (higher accuracy, smaller Euclidean distance).
Limitations and Future Work
- Local Model Assumption: The PriSTE framework assumes a local model where adversaries cannot access internal states of the algorithm. Relaxing this assumption could lead to privacy leakage.
- Given Transition Matrix: The framework assumes the user's mobility (transition matrix) is known and accurate. The impact of an inaccurate or unknown transition matrix on privacy guarantee is an area for future work.
- Generic Mechanism: The paper focuses on adapting existing LPPMs. Designing a generic mechanism that inherently provides spatiotemporal event privacy without relying on specific LPPMs is suggested as future work.
- Optimal Trade-off: Finding the optimal balance between location privacy and spatiotemporal event privacy simultaneously is an open research question.
- More Complex Events: While PRESENCE and PATTERN events are covered, exploring privacy for even more complex spatiotemporal event definitions could be beneficial.
Summary updated