Geo-Indistinguishability for Location Privacy

A ride-hailing app needs to answer “how many drivers are near me?” without ever learning where me actually is; a check-in feature wants to place a user “in this neighbourhood” without pinning them to a doorway. Neither problem is a database-aggregate problem — there is no dataset of neighbours to protect, just one person reporting one point from their own device. Geo-indistinguishability is the formal privacy definition built for exactly this local, single-point setting: it perturbs a coordinate so that any two true locations within a chosen radius produce reports an attacker cannot tell apart by more than a bounded factor. This guide develops the definition itself — the metric generalisation of differential privacy, the per-metre budget $\varepsilon$, the planar Laplace mechanism, and the truncation and accounting a production release needs — and hands the deep polar-sampling derivation to the implementing geo-indistinguishability in Python child guide.

Geo-indistinguishability sits inside the Differential Privacy for Geospatial Data section as the local-model, per-point member of the family. Where the spatial noise mechanisms guide calibrates noise to protect an aggregate against a neighbouring-dataset change, geo-indistinguishability protects a single individual’s coordinate against an attacker who already holds the exact output. It reuses the planar (2D) Laplace distribution that the planar Laplace noise for location privacy page treats as one mechanism among several, but here that distribution is the definition’s canonical mechanism rather than a calibration choice. The trust-model distinction — no trusted curator, the noise applied on-device — is the same fork examined in comparing central vs local differential privacy for GIS.

The definition: metric differential privacy

Standard $\varepsilon$-differential privacy is defined over neighbouring datasets — two databases differing in one record — and bounds how much any output’s probability can change when one person is added or removed. Geo-indistinguishability drops the dataset entirely. Its inputs are points in a metric space, and the neighbouring relation is replaced by a continuous distance. A randomised mechanism $K$ that maps a true location $x$ to a reported location $z$ satisfies $\varepsilon$-geo-indistinguishability when, for every pair of locations $x, x'$ and every output region $S$,

$$\frac{\Pr[K(x) \in S]}{\Pr[K(x') \in S]} \;\le\; e^{\varepsilon \, d(x, x')},$$

where $d(x, x')$ is the Euclidean ground distance in metres. This is an instance of the broader $d_\mathcal{X}$-privacy (metric, or $\ell$-privacy) framework: the privacy loss between two inputs is not a flat $\varepsilon$ but scales with how far apart they are. Two locations one metre apart are almost perfectly confusable; two locations a kilometre apart are allowed to be very distinguishable. That graceful degradation with distance is the whole point — it is what lets a report be useful (“somewhere in this district”) while still hiding the exact address.

Key concept. Geo-indistinguishability protects a single point, not a dataset. There is no “add or remove one record” — the adversary is assumed to see the exact output and to know the mechanism, and the guarantee is that the output looks nearly identical for any nearby true location. The privacy loss grows linearly with distance, so $\varepsilon$ carries units of inverse metres, not the dimensionless $\varepsilon$ of aggregate DP.

Three consequences follow immediately, and they are the reasons this definition is not interchangeable with the aggregate mechanisms in the sibling guide:

• No trusted curator. Perturbation happens on the user’s own device before the coordinate is transmitted, so the definition holds in the local model — the server, the network, and any downstream analyst are all untrusted. This is the same trust posture dissected in comparing central vs local differential privacy for GIS.
• The unit of protection is a metre, not a record. You do not tune $\varepsilon$ against a query’s sensitivity $\Delta f$. You tune it against the physical radius within which you want locations to be confusable, which is why the calibration in Step 1 is a geometry problem.
• Composition is spatial. Two independent releases of the same person’s location compose to $2\varepsilon$-geo-indistinguishability, which halves the effective protection radius. Tracking that spend is privacy budget management applied to a per-subject, per-metre ledger rather than a per-query one.

Prerequisites

The reference mechanism needs only numpy for vectorised sampling and scipy.special.lambertw for the radius inverse-CDF; everything else is standard library. Assume the following are in place before you perturb a single coordinate:

• Canonical CRS. Inputs are EPSG:4326 decimal degrees. Because the metric $d$ is a ground distance in metres, you convert the sampled planar displacement to a degree offset using $\approx 111{,}320$ m per degree of latitude and $111{,}320 \cos(\text{lat})$ m per degree of longitude. Feeding projected metres (EPSG:3857) straight in distorts the metric near the poles and silently weakens the guarantee.
• A declared privacy level and radius. You must fix the two policy inputs up front: the privacy level $\ell$ (the log-likelihood-ratio ceiling you will tolerate) and the protection radius $r$ over which it applies. These map to a regulatory control — for example, CCPA/CPRA treats geolocation finer than roughly 564 m as “precise”, so a report that must not be precise should use $r \gtrsim 564$ m.
• A per-subject budget accountant. Geo-indistinguishability is exact for a single release. The moment the same subject’s location is released more than once, spend accumulates and the accountant must debit it, exactly as a Rényi accountant would for aggregate DP.

Step 1: Set the privacy level ℓ and radius r, then derive ε

The two knobs a policy owner actually reasons about are the protection radius $r$ (how far apart two locations must be before an attacker is allowed to distinguish them) and the privacy level $\ell$ (how much distinguishability you permit at exactly that radius). They combine into the per-metre budget by the defining identity

$$\ell \;=\; \varepsilon \, r \quad\Longrightarrow\quad \varepsilon \;=\; \frac{\ell}{r}.$$

Read $\ell$ as a log-likelihood ratio: $\ell = \ln 4 \approx 1.386$ means an attacker’s odds in favour of the true location over any other point within radius $r$ improve by at most a factor of four. The value of $\varepsilon$ that falls out has units of inverse metres, and the mechanism’s expected reported displacement is $2/\varepsilon$ — a useful sanity anchor when you explain the setting to a product team.

from __future__ import annotations
import math

def epsilon_per_metre(privacy_level: float, radius_m: float) -> float:
    """Derive the geo-indistinguishability budget epsilon (units: 1/metre).

    privacy_level (ell): the tolerated log-likelihood ratio *at* radius r.
        ell = ln(k) means an attacker's odds for the true location over any
        point within r improve by at most a factor of k.
    radius_m (r): the physical radius over which locations must be confusable.
    """
    if privacy_level <= 0 or radius_m <= 0:
        raise ValueError("privacy_level and radius_m must be positive")
    epsilon = privacy_level / radius_m          # ell = eps * r  ->  eps = ell / r
    return epsilon

if __name__ == "__main__":
    eps = epsilon_per_metre(math.log(4), 564.0)  # 4x odds cap at the CCPA radius
    assert math.isclose(eps, math.log(4) / 564.0)
    print(f"eps = {eps:.6f} /m   mean displacement = {2/eps:.0f} m")

The table exposes the core tension: a larger $r$ (hide more) at a fixed $\ell$ forces a smaller $\varepsilon$, which enlarges the mean displacement and destroys utility for anything that needs street-level accuracy. Choosing the pair is the whole design decision; the mechanism below is mechanical once it is fixed.

Step 2: Construct the planar Laplace mechanism

The canonical mechanism for geo-indistinguishability is the planar (2D) Laplace centred on the true location, with density

$$D_\varepsilon(x_0)(z) \;=\; \frac{\varepsilon^2}{2\pi}\, e^{-\varepsilon\, d(x_0, z)}.$$

Because that density depends on the output only through the distance $d(x_0, z)$, plugging any two candidate sources $x_0, x_0'$ into the ratio yields $e^{-\varepsilon(d(x_0,z) - d(x_0',z))}$, and the triangle inequality bounds the exponent by $\varepsilon\, d(x_0, x_0')$ — which is precisely the $e^{\varepsilon d}$ guarantee, proved directly from the density. Sampling from it is a polar problem: draw the angle uniformly and the radius from the marginal $C_\varepsilon(r) = 1 - (1 + \varepsilon r)\,e^{-\varepsilon r}$, whose inverse uses the $-1$ branch of the Lambert $W$ function. The class below wires that up; the full derivation of the radius CDF lives in the implementing geo-indistinguishability in Python child guide.

from __future__ import annotations
import math
from dataclasses import dataclass
from typing import Optional, Tuple
import numpy as np
from scipy.special import lambertw

M_PER_DEG: float = 111_320.0   # metres per degree of latitude (WGS84 mean)

@dataclass
class GeoIndistinguishability:
    """epsilon-geo-indistinguishability via the planar (2D) Laplace mechanism.

    Two true locations x0, x0' are e^{eps * d(x0, x0')}-indistinguishable in
    the reported output, where d is Euclidean ground distance in metres and
    eps has units of 1/metre. The mechanism runs on-device (local model): the
    raw coordinate is never transmitted, only the perturbed report.
    """
    epsilon: float                                   # per-metre budget (1/m)
    bounds: Tuple[float, float, float, float] = (    # valid region, lat/lon
        -90.0, 90.0, -180.0, 180.0)

    def __post_init__(self) -> None:
        if self.epsilon <= 0:
            raise ValueError("epsilon must be positive (units 1/metre)")

    def _sample_radius(self, p: float) -> float:
        """Inverse-CDF of the planar-Laplace radial marginal via Lambert W.

        C(r) = 1 - (1 + eps*r) e^{-eps*r};  invert with the k=-1 branch so the
        drawn radius reproduces the exact e^{-eps*r} tail that the guarantee
        depends on. Under-dispersed radii would silently break the bound.
        """
        w = lambertw((p - 1.0) / math.e, k=-1).real
        return -(w + 1.0) / self.epsilon

Step 3: Perturb a location

Perturbation composes three independent draws: a uniform angle, a Lambert-W radius, and the conversion of that planar displacement into a latitude/longitude offset that respects the local metric (longitude degrees shrink by $\cos(\text{lat})$ away from the equator). The raw coordinate is consumed only inside this method and never leaves the device.

    def perturb(self, lat: float, lon: float,
                rng: Optional[np.random.Generator] = None) -> Tuple[float, float]:
        """Return an epsilon-geo-indistinguishable report for (lat, lon)."""
        if not (-90.0 <= lat <= 90.0 and -180.0 <= lon <= 180.0):
            raise ValueError(f"coordinate out of WGS84 range: ({lat}, {lon})")
        rng = rng or np.random.default_rng()
        theta: float = rng.uniform(0.0, 2.0 * math.pi)     # angle: uniform
        p: float = rng.uniform(1e-12, 1.0 - 1e-12)         # avoid CDF endpoints
        radius_m: float = self._sample_radius(p)           # planar-Laplace radius
        d_north_m: float = radius_m * math.sin(theta)
        d_east_m: float = radius_m * math.cos(theta)
        # metric-aware conversion back to degrees; longitude scaled by cos(lat)
        d_lat: float = d_north_m / M_PER_DEG
        d_lon: float = d_east_m / (M_PER_DEG * math.cos(math.radians(lat)))
        return self._remap(lat + d_lat, lon + d_lon)

Step 4: Truncate and remap to a valid region

The planar Laplace has infinite support: a sampled radius can, with vanishing but non-zero probability, land a report in the ocean, across the antimeridian, or outside the polygon your product is allowed to serve. Truncation fixes that, but it must be done as post-processing on the report only — the remap function may look at the noisy output and at a fixed valid region, but never at the true location. Any dependence on the true point re-opens a channel that leaks it and voids the guarantee. A clamp to a bounding box, or a projection to the nearest point of a service polygon, both satisfy this because they are deterministic functions of $z$ alone.

    def _remap(self, lat: float, lon: float) -> Tuple[float, float]:
        """Clamp a report into the valid region. Post-processing on z ONLY.

        Depends solely on the noisy output and the fixed bounds, never on the
        true location, so it composes with DP for free and leaks nothing.
        """
        lat_lo, lat_hi, lon_lo, lon_hi = self.bounds
        clamped_lat = min(max(lat, lat_lo), lat_hi)
        clamped_lon = min(max(lon, lon_lo), lon_hi)
        return clamped_lat, clamped_lon

Clamping does bias the reported distribution toward the boundary, which costs utility near an edge but never privacy — a report pinned to the boundary is consistent with every true location that could have produced it. If a use case genuinely cannot tolerate that mass at the edge (a coastal city where clamping crowds reports onto the shoreline), the remedy is a bounded mechanism designed jointly with truncation, not a remap that peeks at the true point.

Step 5: Account for budget per query

A single report is $\varepsilon$-geo-indistinguishable. The instant the same subject is released a second time, the two reports compose: an attacker who sees both faces $2\varepsilon$-geo-indistinguishability, which is a halved protection radius at the original privacy level. Any product that reports a user’s position repeatedly — a live map, a periodic check-in — must therefore debit a per-subject ledger and refuse releases that would push cumulative spend past the policy ceiling, the local-model twin of the composition defence in privacy budget management.

class GeoIndBudgetLedger:
    """Per-subject accountant for repeated geo-indistinguishable releases.

    Sequential releases of one subject compose additively in epsilon, so the
    effective protection radius at a fixed privacy level ell shrinks as
    r_eff = ell / eps_spent. The ledger refuses any release that would push a
    subject past the configured epsilon ceiling.
    """
    def __init__(self, epsilon_ceiling: float) -> None:
        if epsilon_ceiling <= 0:
            raise ValueError("epsilon_ceiling must be positive")
        self.ceiling: float = epsilon_ceiling
        self._spent: dict[str, float] = {}

    def charge(self, subject_id: str, epsilon: float) -> float:
        """Debit one release; raise if it would exceed the subject's ceiling."""
        prior: float = self._spent.get(subject_id, 0.0)
        if prior + epsilon > self.ceiling + 1e-12:
            raise RuntimeError(
                f"budget exhausted for {subject_id}: "
                f"{prior + epsilon:.5f} > {self.ceiling:.5f} /m")
        self._spent[subject_id] = prior + epsilon
        return self._spent[subject_id]

    def effective_radius(self, subject_id: str, privacy_level: float) -> float:
        """Protection radius still in force after cumulative spend: ell / eps."""
        spent = self._spent.get(subject_id, 0.0)
        return math.inf if spent == 0.0 else privacy_level / spent

The ledger makes the erosion legible: a subject reported ten times at $\varepsilon = 0.0025$/m has spent $0.025$/m, and the radius over which they enjoy a $\ln 4$ privacy level has collapsed from 564 m to about 56 m. Correlated releases (a smooth trajectory rather than independent snapshots) compose worse than this additive bound, which is why streaming positions belong to the dedicated w-event trajectory machinery rather than naive re-perturbation.

Step 6: Validate the e^{εr} bound empirically

Two things can silently break: the sampler can draw radii from the wrong distribution (under-dispersed noise that fails the tail), and the metric conversion can distort distances so the effective $\varepsilon$ drifts. The harness below checks both. First it confirms the empirical mean displacement matches the theoretical $2/\varepsilon$, which certifies the Lambert-W radius sampler. Then it verifies the definition itself by histogramming reports from two true sources a known distance apart and asserting that no output cell’s likelihood ratio exceeds $e^{\varepsilon d}$ beyond sampling tolerance.

def _validate() -> None:
    eps = epsilon_per_metre(math.log(4), 564.0)      # ~0.00246 /m
    mech = GeoIndistinguishability(epsilon=eps)
    rng = np.random.default_rng(7)
    lat0, lon0 = 40.7484, -73.9857                   # a Manhattan point

    # 1. Sampler correctness: empirical mean radius ~ 2 / eps.
    n = 60_000
    radii = np.empty(n)
    for i in range(n):
        la, lo = mech.perturb(lat0, lon0, rng=rng)
        d_north = (la - lat0) * M_PER_DEG
        d_east = (lo - lon0) * M_PER_DEG * math.cos(math.radians(lat0))
        radii[i] = math.hypot(d_north, d_east)
    assert abs(radii.mean() - 2.0 / eps) / (2.0 / eps) < 0.05, "radius sampler off"

    # 2. The e^{eps*d} bound: two sources D metres apart, compare report
    #    histograms; no bin's density ratio may exceed e^{eps*D} (+ sampling
    #    slack). This tests the *definition*, not just the sampler.
    d_m = 300.0
    lat1 = lat0 + d_m / M_PER_DEG                     # a source 300 m north
    edges = np.linspace(-4000, 4000, 41)             # metre-grid on each axis

    def report_grid(src_lat: float, src_lon: float) -> np.ndarray:
        xs = np.empty(n); ys = np.empty(n)
        for i in range(n):
            la, lo = mech.perturb(src_lat, src_lon, rng=rng)
            ys[i] = (la - lat0) * M_PER_DEG
            xs[i] = (lo - lon0) * M_PER_DEG * math.cos(math.radians(lat0))
        h, _, _ = np.histogram2d(xs, ys, bins=[edges, edges])
        return h + 1.0                               # Laplace-smooth empty bins

    ratio = report_grid(lat0, lon0) / report_grid(lat1, lon0)
    bound = math.exp(eps * d_m)                       # theoretical ceiling
    assert ratio.max() <= bound * 1.25, "e^{eps*d} bound violated beyond slack"
    print(f"OK  mean radius {radii.mean():.0f} m (theory {2/eps:.0f} m); "
          f"max ratio {ratio.max():.3f} <= e^(eps*d) {bound:.3f}")

if __name__ == "__main__":
    _validate()

Threat Model Considerations

Geo-indistinguishability assumes a strong adversary — one who sees the exact report and knows the mechanism and its parameters — so the residual risks are about the edges of the definition, not the core bound:

• Persistent identity across releases. The definition protects one release. An attacker who links many reports of the same pseudonymous ID composes the budget (Step 5) and, worse, exploits correlation between successive true positions. Rotate identifiers and cap per-subject $\varepsilon$; never let a live feed re-perturb independently.
• Prior-knowledge sharpening. Geo-indistinguishability bounds the multiplicative likelihood change but says nothing about an attacker’s prior. If a prior already places a user at home with high probability, a noisy report still concentrates there. The definition guarantees confusability, not that the posterior mode moves — communicate this honestly rather than promising “anonymity”.
• Map-matching and feasibility priors. A report that lands in a river or on a runway is implausible; an attacker who intersects the noisy point with a road or building footprint shrinks the feasible set, recovering resolution the noise was meant to add. This is the same map-matching vector catalogued in the section threat model, and it is why truncation to a service polygon (Step 4) is a privacy feature, not only a utility one.
• Parameter disclosure and metric mismatch. If the deployed $\varepsilon$ differs from the advertised one — because a projection distorted the metric near the poles, or floating-point clamped the Lambert-W radius — the real guarantee is weaker than claimed. Treat $\varepsilon$ as a security parameter and validate it empirically (Step 6) in every region you serve.
• Low-entropy angle or radius source. The angle must be genuinely uniform and the radius drawn from the exact marginal. A weak PRNG, or the p = 0/p = 1 CDF endpoints, produces degenerate reports that an attacker can invert. Clamp $p$ away from the endpoints and seed from a cryptographic source in production.

Validation & Compliance Checklist

Wire each control into CI or a release gate with a measurable pass criterion rather than reviewing it by eye:

1. Budget derivation — PASS if every deployed mechanism records the $(\ell, r)$ pair it was built from and $\varepsilon = \ell / r$ is recomputed and asserted at load, so a hand-edited $\varepsilon$ cannot drift from the stated policy.
2. Sampler fidelity — PASS if the empirical mean displacement over $\ge 5\times10^4$ perturbations is within 5% of $2/\varepsilon$ in every served region, catching metric distortion far from the equator.
3. Metric-DP bound — PASS if the two-source histogram test (Step 6) shows no output cell exceeding $e^{\varepsilon d}$ beyond the documented sampling slack, for at least one $d$ near the protection radius.
4. Remap purity — PASS if a static analysis or unit test confirms _remap reads only the report and the fixed bounds — never the true coordinate — so truncation stays post-processing.
5. Per-subject accounting — PASS if repeated releases of one subject debit the ledger and the release path refuses any query past the $\varepsilon$ ceiling; assert effective_radius shrinks as $\ell / \varepsilon_\text{spent}$.
6. Compliance binding — PASS if the protection radius maps to a named obligation — e.g. $r \ge 564$ m to keep reports outside the CCPA/CPRA precise-geolocation threshold — and the mapping is recorded in the release log, not left implicit.

Failure Modes & Remediation

• Under-dispersed radius from a naive sampler. Substituting a 1D Laplace or a Gaussian for the planar-Laplace marginal produces reports whose tail decays too fast, so the true $\varepsilon$ is larger than claimed and the $e^{\varepsilon d}$ bound is violated. Detection: the mean-radius assertion in Step 6 fails. Remediation: use the Lambert-W inverse-CDF for the radius; verify against $2/\varepsilon$.
• Longitude scaling omitted. Converting the east displacement with a flat $111{,}320$ m/deg instead of $111{,}320\cos(\text{lat})$ under-perturbs longitude at high latitude, collapsing the protection into an ellipse. Detection: per-region mean-radius test drifts with latitude. Remediation: always scale longitude by $\cos(\text{lat})$; re-validate in northern and southern service areas.
• Remap that reads the true location. “Snap to the nearest valid point to the user” is the classic mistake — it makes the output depend on the secret and leaks it. Detection: code review flags a true-coordinate argument to the remap. Remediation: remap on $z$ and fixed bounds only; if edge mass is unacceptable, adopt a bounded mechanism.
• Silent budget exhaustion on a live feed. A map that re-perturbs a moving user every few seconds burns budget until the effective radius is metres. Detection: the ledger’s effective_radius drops below the policy floor. Remediation: cap releases per subject per window, or switch streaming positions to w-event trajectory privacy.
• CDF endpoint blow-up. Sampling $p = 0$ or $p = 1$ sends the Lambert-W radius to zero or infinity, producing a degenerate report. Detection: NaN/inf displacements, or reports exactly on the true point. Remediation: clamp $p$ into $(\delta, 1-\delta)$ as the reference perturb does.

Frequently Asked Questions

Related

This guide is part of the Differential Privacy for Geospatial Data section — start there for how noise mechanisms, aggregation, geo-indistinguishability, and trajectory privacy fit together.

• Implementing Geo-Indistinguishability in Python — the deep polar-sampling derivation, the Lambert W radius CDF, and a production-hardened sampler.
• Spatial Noise Mechanisms — the sibling guide that calibrates noise for aggregate releases rather than single points.
• Planar Laplace Noise for Location Privacy — the 2D Laplace distribution treated as one mechanism among several.
• Comparing Central vs Local Differential Privacy for GIS — the trusted-curator versus on-device trust fork this definition lives on the local side of.
• Privacy Budget Management — tracking cumulative per-subject spend so repeated releases do not silently erode the protection radius.

Up: Differential Privacy for Geospatial Data