Source-linked AI summary
Protecting Locations with Differential Privacy under Temporal Correlations
Yonghui Xiao, Li Xiong
TL;DR
The paper targets continual location sharing, where existing protections may lack rigorous guarantees and fail to account for temporal correlations. It introduces δ-location set differential privacy, sensitivity hull geometry, and the planar isotropic mechanism, reporting optimality and improved utility while addressing model drift with surrogate releases.
Problem
Continual location sharing requires on-the-fly protection for a single user while accounting for temporal correlations that existing approaches may omit.
Method
The paper combines δ-location set differential privacy, sensitivity-hull-based error analysis, and the planar isotropic mechanism for location perturbation.
Results
PIM achieves the lower bound of differential privacy, while the paper’s conclusion reports high efficiency and utility.
Takeaways & Limitations
The framework provides a systematic approach to differentially private location release under temporal correlations, with PIM designed for optimal two-dimensional utility.
Takeaways & Limitations
When the Markov or mobility model is inaccurate, the framework still guarantees differential privacy but may generate more error and lower utility, especially for distant new places.
Abstract
from arXiv · showhide
Concerns on location privacy frequently arise with the rapid development of GPS enabled devices and location-based applications. While spatial transformation techniques such as location perturbation or generalization have been studied extensively, most techniques rely on syntactic privacy models without rigorous privacy guarantee. Many of them only consider static scenarios or perturb the location at single timestamps without considering temporal correlations of a moving user's locations, and hence are vulnerable to various inference attacks. While differential privacy has been accepted as a standard for privacy protection, applying differential privacy in location based applications presents new challenges, as the protection needs to be enforced on the fly for a single user and needs to incorporate temporal correlations between a user's locations. In this paper, we propose a systematic solution to preserve location privacy with rigorous privacy guarantee. First, we propose a new definition, "$δ$-location set" based differential privacy, to account for the temporal correlations in location data. Second, we show that the well known $\ell_1$-norm sensitivity fails to capture the geometric sensitivity in multidimensional space and propose a new notion, sensitivity hull, based on which the error of differential privacy is bounded. Third, to obtain the optimal utility we present a planar isotropic mechanism (PIM) for location perturbation, which is the first mechanism achieving the lower bound of differential privacy. Experiments on real-world datasets also demonstrate that PIM significantly outperforms baseline approaches in data utility.
1. INTRODUCTION
The paper addresses location privacy for continual sharing, where temporal correlations can defeat single-timestamp obfuscation and existing methods often lack rigorous guarantees. It proposes a differential-privacy framework with a δ-location set, sensitivity hull, and planar isotropic mechanism, whose real-world evaluation shows improved utility over Laplace baselines.
- Problem: Existing location obfuscation methods often use syntactic or ad-hoc privacy models and overlook temporal correlations, leaving them vulnerable to inference attacks.Single-timestamp protection can fail when released locations are considered jointly with road constraints or movement patterns.
- Problem: Continual location sharing must protect a single user’s stream on the fly while accounting for temporal correlations in movement.These correlations may arise from road networks or moving patterns and are assumed public to adversaries.
- Approach: The δ-location set extends differential privacy by hiding each true location among probable locations determined by temporal correlations.The probable locations are modeled through a Markov chain, and pairs within the set are intended to be indistinguishable.
- Approach: The sensitivity hull captures geometric sensitivity in multidimensional space, where ℓ1-norm sensitivity can exaggerate real sensitivity and determine the error lower bound.The paper uses this geometric notion to derive the lower bound for δ-location set based differential privacy.
- Approach: PIM is an efficient planar location-perturbation mechanism designed to achieve the differential-privacy lower bound.It transforms the two-dimensional sensitivity hull to isotropic position to guarantee optimality.
- Evaluation: Real-world experiments report that PIM preserves utility for location-based queries and significantly outperforms the baseline Laplace mechanism.The evaluation includes location-based query utility.
2. PRELIMINARIES
The preliminaries formulate locations and temporal movement with state and map coordinates, then represent adversarial observation as a hidden Markov process. They define differential privacy, ℓ1 sensitivity, Laplace perturbation, convex-hull geometry, and utility metrics for distance and location queries.
- Location representation: Locations are represented either as one-hot state-coordinate vectors over cells or as two-dimensional map-coordinate vectors.A user trace is a sequence of locations in either coordinate system.
- Temporal model: The Markov transition matrix M maps the location distribution at one timestamp to the next through pt = pt−1M.Each matrix entry represents the probability of moving from one cell to another.
- Temporal model: In the adversarial view, true locations are hidden while sanitized releases are observable, forming a Hidden Markov Model with transparent emission probabilities.The framework uses prior and posterior location probabilities around each released observation.
- Differential privacy: Standard differential privacy bounds output distributions on neighboring databases, and the Laplace mechanism adds independent Laplace noise scaled by ℓ1-norm sensitivity.The preliminaries use the unbounded neighboring-database definition and define sensitivity as a maximum ℓ1 distance.
- Utility: The paper measures location utility by expected distance and evaluates location-based query utility with precision and recall.Expected distance is also called correctness in the cited analysis.
- Geometric preliminaries: A convex hull is the smallest convex set containing a point set, represented in two dimensions as a convex polygon.The paper uses convex-hull computation as the geometric basis for the sensitivity hull.
3. PRIVACY DEFINITION
The paper extends differential privacy to continual location sharing by hiding each true location among probable, temporally correlated locations. It formalizes privacy and discusses adversarial guarantees, surrogate handling, and scope limitations.
- Motivation: Hiding the true location among impossible locations is ineffective because the adversary already knows the user cannot be there.The construction therefore focuses on locations with positive probability under the temporal model.
- δ-Location Set: The δ-location set contains the minimum number of probable locations whose prior probability sums to at least 1 − δ.It excludes low-probability locations while emphasizing locations predicted by the Markov model.
- Drift and Surrogate: When the true location falls outside the δ-location set, the mechanism substitutes the nearest cell in the set as a surrogate.The surrogate approach is designed not to reveal whether the true location was inside the set.
- Differential Privacy on δ-Location Set: At each timestamp, δ-location-set differential privacy requires indistinguishable release probabilities for any two locations in the set.This protects the true location within the δ-location set during continual sharing under temporal correlations.
- Adversarial Knowledge: For continual location sharing, δ-location-set differential privacy is equivalent to adversarial privacy, and weaker adversaries’ knowledge does not exceed that of standard adversaries.The framework bounds adversarial knowledge across standard, weak, and strong adversary settings, subject to the stated assumptions.
- Discussion and Limitations: The framework may generate more error when the Markov model is inaccurate, and protecting an entire released trace remains future work.Drift can occur with previously unseen destinations, while large δ-location sets can reduce utility and too-large δ can preserve little privacy.
4. SENSITIVITY HULL
The sensitivity hull captures the geometric sensitivity of a query in multidimensional space, correcting the overestimate produced by ℓ1-norm sensitivity. It also determines the differential privacy error lower bound.
- Geometric Motivation: ℓ1-norm sensitivity can exaggerate real sensitivity because it encloses differences that are not attainable query-output changes.In Example 4.1, the dashed set has ||∆f||1 = 2, while ∆f contains only the attainable points.
- Sensitivity Hull Definition: The sensitivity hull is the convex hull of output differences over all pairs of locations in the δ-location set.
- Geometric Properties: A sensitivity hull is centrally symmetric, so every vector in K has its negative in K.
- Geometric Properties: For a discrete domain, the sensitivity hull is a polytope in the output space.
- Error Bound: The lower bound for dynamic differential privacy is determined by the sensitivity hull and, in two dimensions, by its area.The construction represents the polygonal hull as a linear image of a unit ℓ1 ball, reducing the mechanism problem to locating a point from K.
5. LOCATION RELEASE ALGORITHM
The location release algorithm repeatedly models temporal state transitions, constructs a δ-location set, and releases a perturbed location while updating posterior and prior probabilities. Its planar isotropic mechanism provides differential privacy and achieves the sensitivity-hull error lower bound.
- Framework: At each timestamp, the framework constructs a δ-location set, perturbs the location with a private mechanism, and uses the release to update the posterior for the next timestamp.If the true location is excluded from the δ-location set, a surrogate replaces it before release.
- Framework: Algorithm 1 is ε_t-differentially private on the 0-location set at any timestamp t.
- Planar Isotropic Mechanism: PIM computes the sensitivity hull, transforms it to isotropic position, samples K-norm noise there, and transforms the result back to the original space.The mechanism releases z = x* + rT^-1z′ after sampling z′ uniformly from the isotropic hull and r from Γ(3, ε^-1).
- Privacy and Performance: PIM is ε-differentially private on the δ-location set ∆X.The proof uses the isotropic transformation and the resulting distribution in isotropic space.
- Complexity: Algorithm 2 takes O(nlog(h) + h2log(h)) time, where n is the δ-location-set size and h is the number of convex-hull vertices.
- Privacy and Performance: PIM achieves the differential privacy lower bound for error and is therefore optimal.The error analysis transforms the isotropic-space bound back to the original space, where the relevant volume becomes Area(K).
6. EXPERIMENTAL EVALUATION
The evaluation measures privacy-set behavior, drift, location accuracy, and kNN utility on GeoLife and Gowalla trajectories. Across these experiments, PIM generally provides better utility than LM while parameter choices trade privacy against accuracy.
- Experimental setup: Experiments use GeoLife and Gowalla datasets, with size of ∆X, drift ratio, distance, precision, and recall as evaluation metrics.PIM released most locations within 0.3 second, so runtime was omitted.
- Performance over time: The size of ∆X stabilizes after a few timestamps because probabilities outside the selected δ-location set gradually decay.This supports maintaining a stable candidate set during continual release.
- Performance over time: Drift peaks around timestamps 200–300 when the trajectory turns and the Markov model assigns a relatively small transition probability to that turn.After drift, surrogate-based release produces a lagged catch-up in subsequent timestamps.
- Performance over time: PIM releases locations closer to the true trajectory than LM, supported by more accurate posterior distributions and Bayesian inference for subsequent timestamps.The comparison uses a 500-timestamp GeoLife trajectory with ϵ = 1 and δ = 0.01, averaging 20 runs.
- Impact of parameters: Larger δ reduces ∆X and distance but raises drift ratio, while larger ϵ generally shrinks ∆X and lowers drift ratio.The authors use δ = 0.01 by default because larger values can sharply reduce privacy; δ > 0.03 is not recommended as a privacy–utility trade-off.
- Utility comparison: PIM consistently outperforms LM in distance, kNN precision, and recall across the reported comparisons.With k = k′, precision equals recall and both increase with k; when k = 5, precision decreases and recall increases as k′ grows.
- Impact of parameters: A more accurate personal Markov model improves size of ∆X, drift ratio, and distance without changing the same ϵ-differential privacy level.The privacy level is maintained over different candidate sets regardless of the mobility model M.
7. RELATED WORKS
Prior location privacy work relies largely on obfuscation, cryptography, suppression, or aggregate publication, with limited treatment of continual sharing under temporal correlations. This paper extends differential privacy to that single-user setting and designs an optimal two-dimensional mechanism.
- Location privacy mechanisms: Location privacy mechanisms commonly use spatial cloaking, cell merging, reduced precision, or dummy cells to provide anonymity- or uncertainty-based privacy.These approaches do not always provide sufficient protection and often omit temporal correlations.
- Temporal correlations: Markov models have been used to model mobility and infer locations, while related work has provided provable privacy through suppression rather than perturbation.Formal privacy under temporal correlations for continual sharing remains challenging.
- Differential privacy: Existing differential privacy studies mainly publish aggregate location, trajectory, or spatiotemporal information, whereas this paper addresses continual sharing by one user.The contribution changes the protection setting from trusted publication or aggregation to on-the-fly release.
- Differential privacy: The paper extends K-norm ideas to a two-dimensional sensitivity hull and isotropic transformation to achieve optimal utility for location data.The related mechanisms were approximately log(d)-optimal, while this work targets the lower bound.
8. CONCLUSION AND FUTURE WORK
The paper introduces δ-location-set differential privacy for protecting locations under temporal correlations, then uses sensitivity hulls and PIM to attain the corresponding lower bound. The framework is not limited to Markov mobility models.
- Contributions: δ-location-set differential privacy protects a user’s true location at every timestamp while accounting for temporal correlations.It generalizes the neighboring-database notion for continual location sharing.
- Contributions: Sensitivity hulls replace ℓ1-norm sensitivity to capture geometric sensitivity and derive the error lower bound.The construction addresses the multidimensional geometry of location data.
- Contributions: The planar isotropic mechanism achieves the lower bound while releasing differentially private locations with high efficiency and utility.PIM is the mechanism designed from the sensitivity-hull analysis.
- Future work: The δ-location-set framework can work with mobility models beyond Markov chains, but instantiating and studying more advanced models remains future work.The stated future direction is to examine how different mobility models affect the framework.
11. ADDITIONAL MATERIAL
The additional material develops a Laplace baseline and explains why coordinate-wise sensitivity can waste utility. It motivates sensitivity-hull analysis as a way to choose a better geometric transformation.
- Laplace mechanism: The location query asks for the true two-dimensional location x at a timestamp, with sensitivity computed from the indistinguishable set ∆X.The baseline projects ∆X onto each coordinate axis before calculating sensitivities.
- Laplace mechanism: The baseline Laplace mechanism adds independent Laplace noise to both coordinates using the combined sensitivity (∆1 + ∆2)/ϵ.Algorithm 3 returns the perturbed two-coordinate location.
- Laplace mechanism: Algorithm 3 is ϵ-differentially private and takes O(n) time when n is the number of points in ∆X.The privacy theorem and runtime bound are stated separately for the baseline algorithm.
- Utility analysis: Coordinate-wise Laplace noise can place high probability on points far from the true location and far from the convex hull of ∆X.The example motivates allocating perturbation probability according to the set’s geometry rather than independent axis projections.
- Utility analysis: Rotating the coordinate axes can reduce summed sensitivity and error, prompting the search for an optimal rotation through sensitivity-hull analysis.The passage states that error is proportional to the coordinate-sensitivity sum in the rotated space.