Geo-Indistinguishability & the Planar Laplace Mechanism

Geo-indistinguishability is differential privacy rewritten for a metric space: instead of protecting the presence of one record in a database, it guarantees that two locations $r$ metres apart produce report distributions no further than a factor of $e^{\varepsilon r}$ apart. The planar Laplace mechanism is the standard way to realize it, and it is the right tool whenever the thing you publish is a perturbed point rather than an aggregate.

When Geo-Indistinguishability Is the Right Guarantee # permalink

Central differential privacy for location data protects a record’s membership in a dataset. That is exactly what you want for a count query, and exactly the wrong shape for a single user asking “what is near me?”. There is no dataset in that interaction and no neighbouring dataset to quantify over — there is one person, one coordinate, and one request that must not reveal where they are standing.

Geo-indistinguishability fixes the mismatch by replacing the neighbouring-dataset relation with a metric. Two locations count as “neighbours” to the degree that they are close together, and the indistinguishability requirement relaxes smoothly with distance. A café and the flat above it are almost perfectly indistinguishable; the same café and one in the next city are not, and that asymmetry is what makes the released point still useful for finding nearby restaurants.

Three properties follow directly and are worth stating before any code:

It composes like differential privacy, because it is differential privacy. The definition is a differential-privacy guarantee on the metric $d(x, x')$ rather than the Hamming metric, so every composition theorem carries over. Repeated queries from the same device spend budget exactly as they do under privacy budget allocation for spatial queries, which is what makes it a formal guarantee rather than a masking heuristic.

It needs no trusted curator. The perturbation happens on the device, before anything is transmitted, which places it in the same family as local differential privacy for mobile clients. The server never sees the true coordinate, so a server compromise reveals only what was already published.

Its parameter has units. $\varepsilon$ here is a privacy rate per metre, not a dimensionless budget. This trips people up constantly and is the single most common source of misconfiguration in a geo-indistinguishability deployment, because a number that looks reasonable at $\varepsilon = 1$ in the central model is catastrophic at $\varepsilon = 1$ per metre.

Algorithmic Specification # permalink

The definition # permalink

A mechanism $M$ mapping a true location $x$ to a reported location $z$ satisfies $\varepsilon$-geo-indistinguishability if for every pair of true locations $x, x'$ and every measurable output set $S$:

where $d$ is Euclidean distance in a projected metric CRS. Setting $d(x,x') = 1$ for all distinct pairs recovers ordinary $\varepsilon$-differential privacy, so this is a strict generalization rather than a different framework.

The quantity $\varepsilon \cdot r$ is what an adversary’s posterior can shift by when comparing two hypotheses $r$ metres apart. Practitioners therefore speak of a privacy radius $r^{*}$: the distance within which locations remain acceptably confusable, defined by fixing a tolerable factor $\ell$ and solving

A common design choice is $\ell = e$, giving $r^{*} = 1/\varepsilon$ — the radius at which the adversary’s belief ratio reaches $e \approx 2.72$.

The planar Laplace mechanism # permalink

The canonical mechanism draws a displacement whose density decays exponentially in distance, normalized over the plane:

Sampling is done in polar coordinates. The angle $\theta$ is uniform on $[0, 2\pi)$, and the radius follows a Gamma(2, $1/\varepsilon$) distribution, which can be drawn by inverting its CDF using the Lambert $W$ function:

The $W_{-1}$ branch is the one that yields non-negative radii. Getting this branch wrong is the classic implementation bug and produces a mechanism that hugs the origin far too tightly — it looks like it is working and provides a fraction of the intended protection.

The expected displacement of the planar Laplace mechanism is

which is a useful sanity check: at $\varepsilon = 0.005\,\mathrm{m}^{-1}$, points move 400 m on average.

Parameter reference # permalink

Prerequisites & Data Requirements # permalink

• A projected metric CRS. Every quantity above is in metres. Sampling the displacement in EPSG:4326 degrees applies a privacy rate roughly $10^{5}$ times weaker than intended, and the error is silent because both units are plain floats. Project first, perturb, then reproject only for transport.
• A stable per-device budget window. Because the guarantee composes, a device reporting continuously needs a policy: a total rate per hour or per day, and a rule for what happens when it is exhausted. Without one, the guarantee decays exactly as described under local differential privacy for mobile clients.
• A high-quality random source. The mechanism is only as good as the entropy behind the uniform draw. A seeded generator that reaches production allows an adversary who observes two reports to subtract the noise, which removes the guarantee entirely rather than weakening it.
• A plausibility post-filter, applied deliberately. Reports can land in the sea or outside the service area. Truncating or resampling is post-processing and does not break the guarantee, but it does bias the distribution, and the bias must be documented.
• Python dependencies. numpy for sampling, scipy.special.lambertw for the radius inversion, pyproj or geopandas for the projection step, and shapely if you apply a plausibility filter.

Step-by-Step Implementation # permalink

Step 1 — Fix the privacy radius, then derive ε # permalink

Do not choose $\varepsilon$ directly. Decide the distance within which two locations must remain confusable — the block, the neighbourhood, the town — and invert. This keeps the conversation with reviewers in units everyone understands.

import math

def epsilon_from_radius(privacy_radius_m: float, tolerable_factor: float = math.e) -> float:
    """Privacy rate (per metre) that keeps two points within `privacy_radius_m`
    indistinguishable up to `tolerable_factor`."""
    if privacy_radius_m <= 0:
        raise ValueError("privacy radius must be positive")
    return math.log(tolerable_factor) / privacy_radius_m

# A 200 m radius at a factor of e:
eps = epsilon_from_radius(200.0)      # 0.005 per metre
mean_shift = 2.0 / eps                # 400 m expected displacement

The mean displacement is always twice the privacy radius at $\ell = e$. If 400 m of typical error is unacceptable for the application, the honest response is that the application cannot have a 200 m privacy radius — not that ε should be quietly raised.

Step 2 — Project into metres # permalink

import geopandas as gpd

def to_metric(gdf: gpd.GeoDataFrame) -> tuple[gpd.GeoDataFrame, int]:
    """Reproject WGS84 points into the local UTM zone so displacement is metric."""
    if gdf.crs is None:
        raise ValueError("input has no CRS")
    utm = gdf.estimate_utm_crs()
    return gdf.to_crs(utm), utm.to_epsg()

Step 3 — Sample the planar Laplace displacement # permalink

import numpy as np
from scipy.special import lambertw

def planar_laplace(xs: np.ndarray, ys: np.ndarray, eps: float,
                   rng: np.random.Generator) -> tuple[np.ndarray, np.ndarray]:
    """Perturb projected coordinates under epsilon-geo-indistinguishability."""
    n = xs.size
    theta = rng.uniform(0.0, 2.0 * np.pi, n)
    p = rng.uniform(0.0, 1.0, n)
    # The W_{-1} branch is required; W_0 yields radii clustered at zero.
    w = lambertw((p - 1.0) / np.e, k=-1).real
    r = -(w + 1.0) / eps
    return xs + r * np.cos(theta), ys + r * np.sin(theta)

Step 4 — Apply a plausibility filter and record its effect # permalink

from shapely.geometry import Point

def clamp_to_service_area(x: float, y: float, area, eps: float,
                          rng: np.random.Generator, max_tries: int = 8):
    """Resample until the report lands inside the service area. Post-processing,
    so the guarantee holds — but it biases displacement inward, so count it."""
    for _ in range(max_tries):
        if area.contains(Point(x, y)):
            return x, y, False
        x, y = planar_laplace(np.array([x]), np.array([y]), eps, rng)
        x, y = float(x[0]), float(y[0])
    return x, y, True      # exhausted: flag for the audit record

Step 5 — Track the cumulative rate per device # permalink

from dataclasses import dataclass, field

@dataclass
class GeoIndBudget:
    """Sequential composition over one device's reporting window."""
    rate_ceiling: float                     # total epsilon-metres allowed
    spent: float = field(default=0.0)

    def charge(self, eps: float, radius_m: float) -> None:
        cost = eps * radius_m
        if self.spent + cost > self.rate_ceiling:
            raise RuntimeError("geo-indistinguishability budget exhausted")
        self.spent += cost

Validation & Re-identification Testing # permalink

The first check is distributional: the empirical displacement should match the Gamma(2, $1/\varepsilon$) shape, with mean $2/\varepsilon$ and a long tail. A histogram that peaks at zero indicates the Lambert branch bug; one with a hard outer edge indicates that a clamp was applied without being recorded.

def verify_planar_laplace(dx: np.ndarray, dy: np.ndarray, eps: float) -> dict:
    r = np.hypot(dx, dy)
    return {
        "mean_m": float(r.mean()),
        "expected_mean_m": 2.0 / eps,
        "median_m": float(np.median(r)),
        "frac_under_10m": float((r < 10.0).mean()),   # should be small
        "max_m": float(r.max()),
    }

The second check is adversarial and matters more. Simulate a Bayesian attacker who holds a prior over plausible true locations — a population raster, a building-footprint layer — and computes a posterior from the reported point. The quantity to report is the attacker’s expected error: the distance between their maximum-a-posteriori guess and the truth. A mechanism can be correctly implemented and still leave a small expected error if the prior is concentrated, which is the situation a re-identification risk assessment exists to surface.

The third check is repetition. Report the same true location $n$ times and measure how fast the attacker’s expected error falls. Because the noise is zero-mean and independent, averaging shrinks the error as $1/\sqrt{n}$, and the budget accounting has to make that visible before it happens in production.

Common Failure Modes & Gotchas # permalink

Treating ε as dimensionless. A value of 0.5 is a sensible central-model budget and an absurd privacy rate: at $\varepsilon = 0.5\,\mathrm{m}^{-1}$ the privacy radius is 2 m. Always carry the unit in the variable name and the config key.

The wrong Lambert branch. lambertw(z) defaults to the principal branch, which returns radii concentrated near zero. The resulting mechanism looks superficially correct — points move, the mean is finite — while delivering a small fraction of the intended displacement.

Perturbing in degrees. The most expensive version of the CRS mistake on this site, because the guarantee is stated in metres and the failure is silent. Assert crs.is_projected immediately before the sampling call.

Ignoring repetition. A single report is protected; a device reporting every minute is not. Geo-indistinguishability composes, so a continuous stream needs either memoization of the report for a stationary user or an explicit budget window.

Assuming the released point is inside the service area. Roughly a third of reports at a 200 m radius land more than 400 m away, which is enough to leave a small municipality. Handling this is required, and the handling biases the output.

Comparing ε across mechanisms. An $\varepsilon$ from this page and an $\varepsilon$ from Laplace and Gaussian noise for coordinate data are different quantities with different units. Never sum them into one ledger column without converting through a common $\rho$ under zero-concentrated accounting.

Compliance Alignment # permalink

The documentation burden is smaller than for a central-model release because there is no curator holding raw coordinates. What replaces it is a client-side attestation problem: the assessment has to describe how you know the shipped client actually applies the mechanism, and how a tampered client would be detected.

FAQ # permalink

Is geo-indistinguishability the same as differential privacy?

It is differential privacy instantiated on a metric other than the Hamming distance between datasets. Every theorem — post-processing immunity, sequential composition, the conversion to zero-concentrated accounting — carries over unchanged. The practical differences are that ε has units of inverse metres and that the guarantee is about one user’s location rather than one record’s membership.

How do I pick ε without guessing?

Pick the privacy radius instead. Decide the distance within which two locations must stay confusable, choose a tolerable posterior factor (e is a defensible default), and compute $\varepsilon = \ln \ell / r^{*}$. This makes the parameter reviewable by people who do not work in privacy, because it is stated as a distance.

Why planar Laplace rather than adding Laplace noise to each axis independently?

Per-axis Laplace noise is not rotationally symmetric — it produces a diamond-shaped density that leaks the axis alignment and gives different protection along a road than across it. The planar mechanism’s density depends only on radial distance, which is what the metric definition requires.

Does clamping reports to land or to a service area break the guarantee?

No. Any function of the mechanism’s output is post-processing and cannot weaken the bound. It does bias the reported distribution toward the interior of the allowed region, so record the resampled fraction and account for the bias in any utility metric computed downstream.

Related # permalink

• Implementing Planar Laplace Noise in Python — the sampling code and its verification, in full
• Converting Epsilon per Metre to a Privacy Radius — the unit conversions and a parameter table you can review with a DPO
• Local Differential Privacy for Mobile Clients — the discrete counterpart, for cell histograms rather than points
• Privacy Budget Allocation for Spatial Queries — how repeated reports compose
• Donut Masking vs. Gaussian Displacement — the heuristic alternatives this mechanism replaces when a formal bound is required

← Back to Differential Privacy for Location Data