Source-linked AI summary
Optimal Geo-Indistinguishable Mechanisms for Location Privacy
Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, Catuscia Palamidessi
TL;DR
The paper addresses how to balance geo-indistinguishability with service quality when location data must be protected. It uses linear programming to construct quality-optimal mechanisms, proves privacy optimality under matching distance notions, and introduces a spanning-graph approximation that reduces computational cost while preserving privacy guarantees. The approach is evaluated against existing mechanisms using real-user traces.
Problem
Location privacy mechanisms must balance a desired geo-indistinguishability guarantee against the service quality loss caused by perturbing reported locations.
Method
The paper formulates quality-loss minimization under geo-indistinguishability as a linear optimization problem and approximates it with spanning-graph constraints.
Results
The resulting mechanism minimizes QL under the specified privacy threshold and is also privacy-optimal under matching distance notions; the approximation preserves geo-indistinguishability with a small utility decrease.
Takeaways & Limitations
Spanning graphs reduce the optimization problem’s constraint count from cubic to quadratic, enabling substantially faster computation for larger location sets.
Takeaways & Limitations
The spanning-graph optimization is NP-hard, and the approximate mechanism is optimal only for the graph-induced metric rather than the original metric.
Abstract
from arXiv · showhide
We consider the geo-indistinguishability approach to location privacy, and the trade-off with respect to utility. We show that, given a desired degree of geo-indistinguishability, it is possible to construct a mechanism that minimizes the service quality loss, using linear programming techniques. In addition we show that, under certain conditions, such mechanism also provides optimal privacy in the sense of Shokri et al. Furthermore, we propose a method to reduce the number of constraints of the linear program from cubic to quadratic, maintaining the privacy guarantees and without affecting significantly the utility of the generated mechanism. This reduces considerably the time required to solve the linear program, thus enlarging significantly the location sets for which the optimal mechanisms can be computed.
1. INTRODUCTION
The paper studies the privacy–service-quality trade-off in location-based systems and constructs geo-indistinguishable mechanisms that optimize quality loss. It also establishes privacy optimality under matching distance notions and introduces a spanning-graph approximation that reduces computation while preserving geo-indistinguishability.
- Motivation: Location-based systems expose sensitive personal information, motivating mechanisms that perturb reported locations while preserving useful services.Location data can reveal home addresses, political views, and religious practices.
- Motivation: Perturbation creates a trade-off between the user’s privacy guarantee and service quality loss (QL).The paper frames optimizing this trade-off as an important research direction.
- Optimal mechanism: Given a geo-indistinguishability threshold and a prior, linear optimization constructs a mechanism K that minimizes QL.The privacy constraints are expressible as linear constraints, enabling standard linear-programming techniques.
- Optimal mechanism: When QL and AdvError use the same distance, the optimal mechanism is also optimal for adversarial privacy.Geo-indistinguishability is unaffected by remapping, so the adversary cannot improve the expected error through remapping.
- Efficient approximation: A spanning-graph approximation reduces geo-indistinguishability constraints from cubic to quadratic in the number of locations while retaining the privacy guarantee.Experiments report improved running time and only a nonsignificant increase in QL for a reasonably good approximation.
- Evaluation: The paper evaluates privacy and utility under priors generated from real traces and compares the proposed mechanisms with alternatives.The evaluation uses two widely used datasets and reports that the approach outperforms the mechanisms considered.
2. PRELIMINARIES
The preliminaries define location obfuscation, quality loss, adversarial error, and geo-indistinguishability. They distinguish prior-dependent adversarial privacy from metric-based guarantees and note that geo-indistinguishability does not ensure low leakage under every prior.
- Location obfuscation: A location obfuscation mechanism probabilistically maps a true location x to a reported location z sent to the service provider.For finite location sets, the mechanism is represented by a stochastic matrix whose entry k_xz is the probability of reporting z from x.
- Quality and privacy metrics: Quality loss (QL) is the expected distance between the real and reported locations under a quality metric, and acts as the inverse of utility.The Euclidean metric d2 is a typical choice for measuring service degradation.
- Quality and privacy metrics: A Bayesian adversary remaps the reported location using a stochastic matrix H, and privacy is measured by the best achievable expected error, AdvError.The quality and adversary metrics may differ, although Euclidean distance is canonical for both.
- Geo-indistinguishability: Geo-indistinguishability requires geographically close locations to produce similar reported-location probabilities under a distance-scaled privacy definition.It limits how much the reported location increases an adversary’s ability to distinguish nearby true locations.
- Geo-indistinguishability: Geo-indistinguishability does not guarantee small leakage under every prior when the mechanism must retain useful utility.An adversary who already knows the user is at one of several airports may infer the exact airport unless the noise is very large.
- Geo-indistinguishability: The standard Laplace mechanism provides practical, prior-independent geo-indistinguishability, but tailoring a mechanism to a user prior can improve utility for that prior.The tailored mechanism can retain the geo-indistinguishability guarantee while achieving better utility for the corresponding profile.
3. GEO-INDISTINGUISHABLE MECHANISMS OF OPTIMAL UTILITY
The paper formulates utility optimization under geo-indistinguishability as a linear program, then uses spanning graphs to reduce computational cost while preserving privacy guarantees. When quality and adversary metrics coincide, the resulting mechanism is also optimal for expected adversarial error, although approximation trades utility optimality for efficiency.
- Problem formulation: Given a privacy level, user profile, and quality metric, the goal is to find an ϵdX-private mechanism minimizing service quality loss.The mechanism operates on a finite location set with a prior distribution representing the user profile.
- Linear optimization: Linear constraints enforce ϵdX-privacy, allowing an optimal mechanism to be obtained by minimizing quality loss through linear programming.The resulting mechanism is ϵdX-OptQL for the specified prior and quality metric.
- Constraint reduction: The original privacy formulation introduces |X|3 constraints, while graph-induced metrics can require constraints only for adjacent location pairs.This adjacency reduction applies when dX is induced by a weighted graph.
- Constraint reduction: A δ-spanner replaces all-pairs privacy constraints with edge-based constraints for ϵδdG-privacy, yielding O(|X|2) constraints for fixed δ.The spanner approximation guarantees ϵdX-privacy, but the obtained mechanism is not necessarily utility-optimal for the original metric.
- Spanner construction: The greedy spanner algorithm processes location pairs by increasing dX distance and adds an edge when the current shortest path exceeds δ times the direct distance.For Euclidean locations, the constructed spanner has node degree O(1/(δ−1)); with linear edges, the algorithm runs in O(|X|3 log |X|).
- Practical considerations: The minimum-quality-loss problem for the exact metric is NP-hard to optimize through minimum-edge spanners under a fixed dilation bound.The paper establishes this by reducing the minimum-dilation, edge-bounded spanner problem to the minimum-edge problem at a fixed dilation.
- Adversarial error: When the quality and adversary metrics coincide, an ϵdX-OptQL mechanism also minimizes expected adversarial error, because geo-indistinguishability is preserved under remapping.This equivalence does not hold when the quality and adversary metrics differ.
4. EVALUATION
The evaluation compares OptQL with competing mechanisms on privacy, quality loss, approximation, and runtime using GeoLife and T-Drive traces. OptQL generally provides stronger privacy and utility, while spanning-graph approximation reduces constraints with a quality-loss trade-off.
- Mechanism comparison: The evaluation uses GeoLife and T-Drive traces, comparing OptQL with Shokri et al.’s mechanism and Planar Laplace under multiple priors.GeoLife results are presented in detail, while T-Drive results are summarized; priors represent all-day, morning, afternoon, and night periods.
- Mechanism comparison: Under GeoLife priors, OptQL generally provides better location privacy than the other mechanisms, except for the all-day prior used during construction.For that all-day prior, OptQL and OptPriv provide the same privacy.
- Mechanism comparison: With the same geo-indistinguishability level, OptQL provides better utility, meaning lower quality loss, than Planar Laplace.Figure 4 compares quality loss across different ϵ values using per-user utility points and median lines.
- Approximation performance: The spanning-graph approximation reduces the linear program’s constraints but generally increases quality loss relative to the exact optimum.Its purpose is to make optimization more tractable for large location sets by replacing all location-pair constraints with constraints on spanning-graph edges.
- Approximation performance: Between δ = 1.4 and δ = 1.45, both the number of constraints and quality loss decrease because the average-case approximation ratio improves despite a worse worst-case ratio.This shows that worst-case dilation alone does not determine observed quality loss.
- Runtime performance: The dual simplex and primal-dual interior-point methods applied to the primal program behave consistently, with interior-point performance depending strongly on dilation.Interior-point performs better for larger dilation but worse for very small dilation; the dual formulation offers no significant performance improvement over it.
- T-Drive results: On T-Drive, OptQL’s median privacy is always at least as high as the other mechanisms’ corresponding medians, while its quality loss is better than Planar Laplace’s.The all-day prior remains an exception for privacy because the relevant values coincide.
5. CONCLUSION AND RELATED WORK
The paper situates its mechanism among location-privacy approaches and combines geo-indistinguishability with optimized utility. Its spanning-graph approximation reduces computational burden while preserving privacy guarantees, and OptQL achieves lower quality loss than PL in T-Drive.
- CONCLUSION: OptQL has lower quality loss than PL for every tested ϵ value on the T-Drive dataset.
- RELATED WORK: The paper contrasts identity-hiding, pseudonym, cloaking, dummy-location, and aggregate-data differential-privacy approaches with its obfuscation-based mechanism.
- RELATED WORK: The closest prior work also uses linear programming, but its constraint-discarding approximation can affect geo-indistinguishability guarantees.
- CONCLUSION: The paper’s spanning-graph approximation reduces constraints from cubic to quadratic without jeopardizing privacy guarantees, at the cost of a small utility decrease.
A. PROOFS
The proofs establish privacy preservation under spanning-graph approximation and show that utility-optimal geo-indistinguishable mechanisms are also optimal for AdvError under matching metrics.
- Privacy preservation: A δ-spanner can support the privacy proof because pointwise metric domination transfers dX-privacy to the larger metric.
- Optimality proof: Remapping preserves dX-privacy, so applying a remapping cannot produce a mechanism with better quality loss while remaining within the same privacy class.
- Optimality theorem: If K is dX-OptQL(π, dQ), then it is also q-OptPriv(π, dQ, dQ), with q equal to QL(K, π, dQ).
- Optimality proof: The contradiction argument rules out any alternative remapping that would lower quality loss while preserving dX-privacy.
B. DUAL FORM OF THE OPTIMIZATION PROBLEM
The dual optimization problem is derived from the original linear program using standard linear-programming transformations. Its variables correspond to the original privacy and normalization constraints.
- Dual derivation: The dual form is obtained by applying the standard technique of linear programming to the original optimization problem.
- Dual variables: The dual program introduces one variable for each original constraint that is not imposed on a single variable.
- Dual variables: Variables a_xx′z correspond to the privacy constraints indexed by z and location pairs (x, x′) in E.
- Dual variables: Variables b_x correspond to the original normalization constraints indexed by locations x.
- Dual formulation: The resulting system of constraints and objective function constitutes the dual linear program.