Source-linked AI summary
Geo-Indistinguishability: Differential Privacy for Location-Based Systems
Miguel E. Andrés, Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, Catuscia Palamidessi
TL;DR
Location-based systems raise privacy concerns because precise location can reveal sensitive personal information, while standard differential privacy is poorly suited to protecting a single user’s location. The paper formalizes geo-indistinguishability, develops planar Laplacian perturbation, and applies it to LBSs; it reports the best privacy guarantees for the same utility among mechanisms independent of prior knowledge.
Problem
Standard differential privacy is poorly suited to single-user location because preventing effects from location changes would block useful information, while existing notions may depend on adversary side information.
Method
The paper defines geo-indistinguishability as distance-aware generalized differential privacy and achieves it by perturbing locations with a planar Laplacian mechanism.
Results
The mechanism is applied to LBS applications and offers the best privacy guarantees for the same utility among mechanisms that do not depend on prior knowledge.
Takeaways & Limitations
Geo-indistinguishability provides a framework for releasing approximate location information while protecting exact location and abstracting from the attacker’s prior knowledge.
Takeaways & Limitations
The mechanism’s discretization introduces a trade-off among ϵ′, rmax, precision, and achievable geo-indistinguishability, potentially preventing arbitrary privacy levels.
Abstract
from arXiv · showhide
The growing popularity of location-based systems, allowing unknown/untrusted servers to easily collect huge amounts of information regarding users' location, has recently started raising serious privacy concerns. In this paper we study geo-indistinguishability, a formal notion of privacy for location-based systems that protects the user's exact location, while allowing approximate information - typically needed to obtain a certain desired service - to be released. Our privacy definition formalizes the intuitive notion of protecting the user's location within a radius r with a level of privacy that depends on r, and corresponds to a generalized version of the well-known concept of differential privacy. Furthermore, we present a perturbation technique for achieving geo-indistinguishability by adding controlled random noise to the user's location. We demonstrate the applicability of our technique on a LBS application. Finally, we compare our mechanism with other ones in the literature. It turns our that our mechanism offers the best privacy guarantees, for the same utility, among all those which do not depend on the prior.
1. INTRODUCTION
Location-based systems create serious privacy risks because precise location can reveal sensitive personal information. The paper proposes geo-indistinguishability, a distance-aware privacy notion and perturbation mechanism that preserve useful approximate location information.
- Location-based systems include LBSs and location-data mining systems that record and process users’ location information.
- Accurate, regularly collected location data can reveal users’ homes, workplaces, sexual preferences, political views, and religious inclinations.
- Geo-indistinguishability protects locations within radius r using a privacy level ℓ=ϵr, while allowing weaker protection and greater distinguishability at larger distances.
- The proposed mechanism perturbs the user’s location with planar Laplacian noise, uses polar-coordinate sampling, and adds discretization for finite location representations.
- The mechanism supports configurable privacy and accuracy in LBS applications, though these guarantees require additional bandwidth that the paper evaluates using Google Places API.
- Compared with prior mechanisms, the proposal offers the best privacy guarantees for the same utility among mechanisms independent of the adversary’s prior knowledge.
2. EXISTING NOTIONS OF PRIVACY
Existing location-privacy notions often depend on assumptions about adversary knowledge or protect the wrong target. The paper motivates a prior-independent framework that applies generalized differential privacy to a single user’s location.
- Expectation of distance error measures how accurately an adversary can guess the user’s true location from an obfuscated observation and available side information.
- Transformation-based approaches: Many transformation-based mechanisms explicitly depend on the adversary’s prior knowledge, limiting use when that prior is unknown or varies across users.
- K-anonymity approaches protect locations by making them indistinguishable among multiple points, using techniques such as dummy locations or cloaking regions.
- Side information can invalidate k-anonymity because an attacker may identify implausible dummy points or locations, requiring additional realism assumptions and data.
- Standard differential privacy suits aggregate data but is poorly suited to a single user’s location because hiding every location change would prevent useful disclosure.
- Geo-indistinguishability uses generalized differential privacy to justify Laplace-based location perturbation without fixing an anonymity set.
3. GEO-INDISTINGUISHABILITY
Geo-indistinguishability defines location privacy through distance, protecting nearby locations more strongly while permitting approximate information needed for useful services. The paper formalizes this prior-independent notion, relates it to differential privacy, and discusses its guarantees, composition, and limitations for location sets and aggregate data.
- Definition: Geo-indistinguishability requires ϵr-privacy within every radius r, making the privacy level proportional to distance.The parameter ϵ specifies the privacy level at one unit of distance.
- Definition: For locations x and x′ within distance r, the output distributions K(x) and K(x′) must have multiplicative distance at most ϵr.The definition uses Euclidean distance between locations and constrains the distributions produced by the mechanism.
- Relation to differential privacy: The framework generalizes differential privacy by replacing database Hamming distance with an arbitrary metric, here the Euclidean metric for spatial data.This metric choice supports partial protection of location while allowing approximate information to be released for service utility.
- Prior independence: Geo-indistinguishability abstracts from the adversary’s prior: it limits leakage from the observation without guaranteeing that the location cannot already be inferred from side information.The paper also provides characterizations that quantify how priors affect the resulting privacy guarantees.
- Limitations: No location-privacy definition can ensure low leakage under every prior while retaining reasonable utility in LBSs.For example, knowing that a user is at an airport can make a useful city-level query reveal the exact airport.
- Location sets and aggregates: Independent protection of n locations scales privacy loss linearly to nϵ, limiting that technique to small location sets, while aggregate data may require different sensitivity analyses.For a centroid, distance-based sensitivity can permit much less noise than standard differential privacy.
4. A MECHANISM TO ACHIEVE GEO-IN-DISTINGUISHABILITY
The paper constructs geo-indistinguishable location noise through a planar Laplace mechanism, then adapts it to discrete grids while addressing implementation and privacy degradation from discretization.
- Construction: The mechanism models locations on a discrete Cartesian plane, beginning with continuous-plane noise, discretization, and truncation to the area of interest.The discrete-plane model approximates the Earth’s surface for sufficiently small areas.
- Continuous plane: The planar Laplace distribution assigns probability density that decreases exponentially with distance from the actual location and satisfies ϵ-geo-indistinguishability.Its normalization factor is ϵ^2/2π, and its projections onto vertical planes are scaled linear Laplacians.
- Discretization: The discretized mechanism samples polar Laplacian noise and remaps each generated point to the closest point on the discrete grid.Finite machine precision makes the generated polar points discrete, producing regions whose shapes and areas vary with their position relative to the actual location.
- Discretization: Discretization preserves geo-indistinguishability only with a degraded privacy parameter and within a bounded distance range.The additional noise compensates for discretization; increasing the guaranteed range can require a larger gap between ϵ′ and ϵ.
- Truncation: The truncated Planar Laplace mechanism PLϵ restricts reported locations to a finite region and fully satisfies geo-indistinguishability there.This addresses finite digital representations and the practical need to report locations within a bounded area.
5. ENHANCING LBSS WITH PRIVACY
The paper enhances location-based services by perturbing locations, expanding retrieval areas, and filtering results to balance geo-indistinguishability, accuracy, and bandwidth. The approach quantifies containment accuracy and shows that overhead depends strongly on privacy and confidence settings.
- LBS enhancement: The client reports an obfuscated location, expands the retrieval area, and filters returned points of interest to approximate the desired service.The retrieval area is enlarged because the server searches around the perturbed location rather than the true one.
- Accuracy: The area of interest cannot always be contained in the area of retrieval, so accuracy measures the probability that containment occurs.The AOR radius must remain independent of the randomly generated location to preserve geo-indistinguishability.
- Accuracy: The Planar Laplace mechanism is geo-indistinguishable, and the application is accurate when rad R ≥ rad I + C^-1_ϵ(c).This condition provides the minimum retrieval radius needed for a chosen confidence and privacy configuration.
- Accuracy: For the running example, c = 0.95 yields a 0.69 useful mechanism, while c = 0.99 gives both geo-indistinguishability and (0.95, 0.3)-accuracy.The example uses ϵ = ln(4)/0.2 and rad I = 0.3.
- Bandwidth: Bandwidth overhead rises slowly through confidence 0.95 but sharply afterward, reaching about 50 times the AOI at highest privacy and confidence.For the running example, the estimated bandwidth overhead is approximately 318 KB; the worst case reaches up to 1.7MB.
- Bandwidth: The authors conclude that the overhead is not prohibitive even in high-overhead scenarios, though repeated or bandwidth-sensitive cases can remain problematic.They compare 1.7MB with approximately 35 seconds of YouTube streaming or 80 seconds of standard Facebook usage.
6. COMPARISON WITH OTHER METHODS
The paper compares its mechanism with a prior-dependent obfuscation method and deterministic cloaking using Bayesian location privacy and service quality. Under matched settings, its mechanism outperforms cloaking, while the comparison under accuracy is not available for the prior-dependent method.
- Compared mechanisms: The prior-dependent mechanism is designed for a given adversary, whereas cloaking reports the zone containing the user’s location.The evaluation uses a 9 × 9 grid of 100 m regions and a 3 × 3 overlay of larger zones.
- Metrics: The comparison uses Location Privacy, defined through a Bayesian adversary’s expected estimation error, and Service Quality Loss, defined through expected distance from the reported location.The adversary combines the report with a prior and may optimally remap it before estimating the true location.
- Metrics: For the optimal prior-dependent mechanism, Location Privacy and Service Quality Loss coincide when it is used against the adversary for which it was designed.The optimal remapping is then the identity.
- Accuracy comparison: The accuracy-based comparison cannot include the mechanism from, because the required comparison criterion is unavailable for it.The paper instead fixes rad I = 200 m and c = 0.99 and compares against cloaking.
- Accuracy comparison: For rad I = 200 m, rad R = 200 m + 2 · 150 m, and c = 0.99, the paper obtains ϵ = 0.016 for its mechanism.The cloaking mechanism’s accuracy is independent of c, while the proposed mechanism’s accuracy depends on c and ϵ.
- Results: Across three priors, the proposed mechanism outperforms cloaking in Location Privacy.The mechanisms are compared at matched quality-of-service settings.
- Results: As confidence decreases, the proposed method becomes more favorable relative to cloaking because its ϵ decreases while cloaking’s accuracy remains unchanged.This comparison holds fixed r = rad R − rad I.
7. RELATED WORK
The related work covers location-privacy mechanisms, privacy metrics, and implementation concerns. It includes methods based on unobservability, fake locations, finite-region cloaking, and discretized Laplacian noise.
- Location privacy methods: LISA prevents attackers from relating a particular point of interest to the user’s location and evaluates privacy with m-unobservability.The condition requires that the attacker usually cannot relate the estimate to at least m nearby POIs.
- Metrics: The paper also situates its comparison around Bayesian Location Privacy and Service Quality Loss metrics.These metrics evaluate adversarial estimation error and reported-location accuracy, respectively.
- Location privacy methods: SpaceTwist reports a fake anchor and incrementally queries nearest neighbors until it obtains the real location’s k-nearest neighbors.Its procedure uses the geolocation server around the fake location.
- Implementation concerns: Prior work shows that finite precision and floating-point rounding can make standard and planar Laplacian implementations irregular and break differential privacy.A proposed remedy addresses a truncated planar Laplacian using a snapping mechanism.
8. CONCLUSION AND FUTURE WORK
The paper presents geo-indistinguishability and a planar Laplace perturbation framework, proves its privacy properties, demonstrates an LBS application, and compares it with prior-independent alternatives. Future work targets sanitizing multiple correlated locations while preserving composability.
- Conclusion: The framework protects location privacy while accounting for desired protection levels and an attacker’s side information.Its core components are geo-indistinguishability and location perturbation based on a bivariate Laplace function.
- Conclusion: The paper formally defines and proves geo-indistinguishability, relates it to differential privacy, and demonstrates the method on POI retrieval.It also compares the mechanism with other methods in the literature.
- Conclusion: The proposed mechanism outperforms compared mechanisms that do not depend on the adversary’s prior.This conclusion is based on the paper’s comparison of privacy guarantees.
- Future work: Future work will address sanitizing several potentially related locations, whose correlation may degrade protection, and controlling the resulting privacy loss.The authors also aim to allow composability of the method.
APPENDIX
The appendix supplies technical details for proving that K_ϵ′ achieves ϵ-geo-indistinguishability within a bounded range, accounting for finite-precision remapping and boundary effects.
- Theorem 4.1 assumes rmax < u/δθ and defines q = u/rmaxδθ for the bounded-range guarantee.
- For locations within rmax of both inputs, Kϵ′ provides ϵ-geo-indistinguishability.
- The proof bounds probabilities by analyzing points for which x is the closest point in G and comparing remapped regions around x.
- Finite machine precision replaces the ideal remapped set S with RW(x), whose discrepancy is represented by small boundary rectangles.
- The appendix concludes the result by combining the preceding inequalities, with the trivial equal-input case excluded from the nontrivial analysis.
- When R(x) lies on the border of A, the proof additionally accounts for probability from a cone portion outside A before applying the same reasoning.