Geo-Indistinguishability

The foundational mathematical framework from which geo-indistinguishability is derived. It provides a provable guarantee that the output of a computation is nearly identical whether or not any single individual's data is included. In the geo-indistinguishability context, this is adapted to protect a user's precise location within a radius parameterized by ε.

• Privacy Loss Parameter (ε): Quantifies the indistinguishability; lower ε means stronger privacy.
• Neighboring Datasets: The definition hinges on outputs being indistinguishable on datasets differing by one record.
• Post-Processing Immunity: Any computation on a differentially private output cannot weaken the guarantee.

The primary noise-injection mechanism used to achieve pure ε-differential privacy for numerical queries, and the direct basis for planar Laplace noise in geo-indistinguishability. It adds random noise drawn from a Laplace distribution calibrated to the query's sensitivity.

• Sensitivity: The maximum change in a query's output when a single record changes. For location, this is the distance metric.
• Calibration: Noise scale is set to sensitivity / ε.
• Planar Laplace: Geo-indistinguishability uses a 2-dimensional Laplace distribution to perturb coordinates within a radius.

A finite, quantifiable resource representing the total allowable privacy loss across all location queries. Each time a user's location is obfuscated using geo-indistinguishability, a portion of this budget is consumed. The composition theorem governs how this loss accumulates.

• Sequential Composition: The total ε across multiple queries is the sum of individual ε values.
• Budget Depletion: Once the budget is exhausted, no further queries can be answered without violating the privacy guarantee.
• Utility-Privacy Trade-off: A larger budget (higher ε) allows more accurate location data but weaker privacy.

The trust model under which geo-indistinguishability typically operates. In LDP, each user perturbs their own location data on-device before transmitting it to a service provider. The aggregator never receives the raw, precise location.

• Untrusted Aggregator: The server collecting location data is assumed to be potentially malicious or compromised.
• Randomized Response: A classic LDP technique; geo-indistinguishability is its spatial generalization.
• Client-Side Noise: All obfuscation logic runs locally on the user's mobile device.

In standard differential privacy, sensitivity measures the maximum impact of a single record on a query. Geo-indistinguishability generalizes this to a distance metric (typically Euclidean). The guarantee ensures that locations within a radius r are indistinguishable, with the privacy loss scaling linearly with distance.

• Multiplicative Distance: The privacy loss between two locations x and x' is bounded by ε * d(x, x').
• Radius r: Locations within r have a privacy loss of at most ε * r.
• Calibration: The noise added is proportional to the chosen distance metric.

A fundamental property of differential privacy that applies directly to geo-indistinguishability. Any arbitrary computation applied to the obfuscated location output cannot weaken the privacy guarantee. A service provider cannot "de-noise" the location to recover the precise coordinates.

• Resilience to Auxiliary Information: Even if an attacker has side knowledge (e.g., map data), the guarantee holds.
• Safe Computation: Service providers can perform any analysis on the noisy location without compromising privacy.
• No Re-identification: The obfuscated output is safe for unlimited downstream processing.