Implementing Geo-Indistinguishability in Python

A location-based service that perturbs each request in isolation looks private and leaks anyway. This page is the engineering and operations complement to the parent guide on geo-indistinguishability for location privacy and the wider Differential Privacy for Geospatial Data section: instead of re-deriving the mechanism, it builds the production client that wraps it — the class an LBS actually calls per request. Three concerns dominate that wrapper and none of them are noise sampling. First, the privacy knob is a rate: geo-indistinguishability spends $\varepsilon$ per metre, so the operating pair you ship is a privacy level $\ell$ over a radius $r$, giving $\varepsilon = \ell / r$. Second, a perturbed point can land in the sea or outside your service polygon, and the naive fix — resample until it lands inside — quietly voids the guarantee. Third, perturbing the same location on every request lets an adversary average the reports back to the truth. The client below fixes the last two with data-independent remapping and a per-user cache tied to a privacy budget; the planar-Laplace sampler it calls is treated as a black box whose inverse-CDF derivation lives in planar Laplace noise for location privacy.

Parameter Configuration and Calibration

Geo-indistinguishability is metric differential privacy on the plane: the indistinguishability between two locations scales with the distance between them, $\varepsilon \cdot d(x, x')$. That makes $\varepsilon$ a quantity with units of $\text{nats}/\text{metre}$, which is awkward to reason about directly. The field convention — and the only configuration surface an operator should ever touch — is the $(\ell, r)$ pair: “any two points within $r$ metres are $\ell$-indistinguishable.” The client derives the raw rate internally as $\varepsilon = \ell / r$.

The radius is the parameter that actually moves privacy. Halving $r$ to $150$ m at fixed $\ell$ doubles $\varepsilon$ to $\approx 0.0092/\text{m}$, halving the noise scale and the median reported error — stronger utility, weaker protection at any given distance. Calibrate $r$ to the smallest region you are willing to have a report be confused across (a city block, not a county), then pick $\ell$ from the confusion factor $e^{\ell}$ your threat model tolerates. Because this is local DP applied on the client before anything leaves the device — the regime contrasted in comparing central vs local differential privacy for GIS — there is no trusted curator to fall back on, so the budget $B$ is the hard stop.

Why truncation breaks the guarantee and remapping does not

The metric-DP guarantee survives any post-processing that is a function of the released point alone. Projecting an out-of-bounds sample to the nearest valid cell is exactly such a function, so it is safe; it only piles probability mass on the boundary and biases utility there. The tempting alternative — rejection sampling, resampling the mechanism until the output falls inside $R$ — is not post-processing. Conditioning on “landed in $R$” renormalises the output distribution by the mass the mechanism placed in $R$, and that mass depends on the true location $x$. Two nearby truths near a coastline then produce output distributions whose ratio exceeds $e^{\varepsilon d}$, and the guarantee is void precisely where the coastline makes the prior most informative. The rule: never reject, always remap. To recover the utility that plain projection loses, upgrade to an optimal spatial remap (a data-independent function that maps each noisy point to the expected true location under the prior), which preserves the guarantee — it is still a function of the output only — while shrinking distortion.

Reference Implementation

GeoIndistinguishabilityClient is the per-request wrapper. Its constructor takes $\ell$, $r$, and the service bounds; report(lat, lon, user_id) perturbs through the injected planar mechanism, remaps into bounds, caches per user to defeat correlation, and debits the budget. The planar sampler is deliberately compact and black-boxed — its calibration is the sibling page’s job.

from __future__ import annotations

import math
import random
from dataclasses import dataclass, field
from typing import Dict, Tuple

from scipy.special import lambertw  # inverse-CDF only; see planar-Laplace page


class BudgetExhausted(RuntimeError):
    """Raised when a user's cumulative privacy level would exceed the cap."""


def planar_laplace(lat: float, lon: float, epsilon: float,
                   rng: random.Random) -> Tuple[float, float]:
    """Draw one planar-Laplace sample around (lat, lon). BLACK BOX.

    epsilon is nats-per-metre. Angle is uniform; radius comes from the
    inverse CDF via the Lambert W (branch -1). The derivation and its
    numerical edge cases are documented in the planar-Laplace guide;
    here it is a dependency the client calibrates but does not own.
    """
    theta = rng.uniform(0.0, 2.0 * math.pi)
    p = rng.random()                                  # p in [0, 1)
    # radius in metres; (p-1)/e keeps the W_-1 argument in [-1/e, 0)
    radius_m = -(1.0 / epsilon) * (float(lambertw((p - 1.0) / math.e, k=-1).real) + 1.0)
    dlat = (radius_m * math.sin(theta)) / 111_320.0   # metres -> degrees lat
    dlon = (radius_m * math.cos(theta)) / (111_320.0 * math.cos(math.radians(lat)))
    return lat + dlat, lon + dlon


@dataclass
class GeoIndistinguishabilityClient:
    """Production LBS client applying geo-indistinguishability per request.

    Config is the (privacy_level, radius_m) pair; the raw rate epsilon =
    privacy_level / radius_m is derived once. Every released point is
    remapped (never rejected) into `bounds`, and every (user, cell) pair
    is cached so repeated queries for the same location cannot be
    averaged back to the truth.
    """

    privacy_level: float                 # ell, in nats
    radius_m: float                      # r, in metres
    bounds: Tuple[float, float, float, float]   # (min_lat, min_lon, max_lat, max_lon)
    per_user_budget: float               # cap on cumulative privacy level
    anchor_cell_deg: float = 0.003       # ~300 m grid for correlation anchoring
    rng: random.Random = field(default_factory=lambda: random.Random())

    def __post_init__(self) -> None:
        if self.radius_m <= 0 or self.privacy_level <= 0:
            raise ValueError("privacy_level and radius_m must be positive")
        # metric-DP rate: nats spent per metre of confusion.
        self.epsilon: float = self.privacy_level / self.radius_m
        self._cache: Dict[Tuple[str, int, int], Tuple[float, float]] = {}
        self._spent: Dict[str, float] = {}

    def _cell(self, lat: float, lon: float) -> Tuple[int, int]:
        """Snap a true location to the anchor grid (the correlation key)."""
        return (round(lat / self.anchor_cell_deg),
                round(lon / self.anchor_cell_deg))

    def _in_bounds(self, lat: float, lon: float) -> bool:
        min_lat, min_lon, max_lat, max_lon = self.bounds
        return min_lat <= lat <= max_lat and min_lon <= lon <= max_lon

    def _remap(self, lat: float, lon: float) -> Tuple[float, float]:
        """Project a noisy point into bounds as a function of the OUTPUT only.

        This is legitimate post-processing (clamp to nearest valid edge),
        so it preserves metric-DP. Rejection sampling would not: its accept
        probability depends on the secret and voids the guarantee.
        """
        min_lat, min_lon, max_lat, max_lon = self.bounds
        return (min(max(lat, min_lat), max_lat),
                min(max(lon, min_lon), max_lon))

    def report(self, lat: float, lon: float, user_id: str) -> Tuple[float, float]:
        """Return a privacy-preserving report for (lat, lon) on behalf of user_id."""
        key = (user_id, *self._cell(lat, lon))
        if key in self._cache:
            # Anchoring: same location -> identical prior report, ZERO new leakage.
            return self._cache[key]

        spent = self._spent.get(user_id, 0.0)
        if spent + self.privacy_level > self.per_user_budget:
            # Fail closed: never emit a fresh perturbation past the cap.
            raise BudgetExhausted(f"user {user_id}: {spent:.3f} + "
                                  f"{self.privacy_level:.3f} > {self.per_user_budget:.3f}")

        noisy_lat, noisy_lon = planar_laplace(lat, lon, self.epsilon, self.rng)
        report = self._remap(noisy_lat, noisy_lon)     # remap, do not reject
        self._cache[key] = report                       # anchor for future requests
        self._spent[user_id] = spent + self.privacy_level
        return report

Caching does double duty. It is the correlation defence — a repeated request for the same anchor cell returns the byte-identical prior report rather than a fresh independent draw, so there is nothing to average — and it is what keeps the budget honest, because only distinct locations debit $\ell$. A user pinging their home address a thousand times spends the budget once.

Validation Checkpoint

These invariants belong in CI. They pin the three properties that silently rot in production: correct $\varepsilon$ derivation, in-bounds output, and cache-backed correlation resistance.

def _validate() -> None:
    rng = random.Random(7)
    client = GeoIndistinguishabilityClient(
        privacy_level=math.log(4), radius_m=300.0,
        bounds=(40.70, -74.02, 40.80, -73.93),   # lower Manhattan bbox
        per_user_budget=3 * math.log(4), rng=rng,
    )

    # 1. epsilon is derived as ell / r, not configured directly.
    assert abs(client.epsilon - math.log(4) / 300.0) < 1e-12

    # 2. every released point stays inside the service bounds.
    r1 = client.report(40.7484, -73.9857, "u1")
    assert client._in_bounds(*r1)

    # 3. repeating the SAME location returns the cached report verbatim
    #    (no fresh draw an adversary could average) and does not re-spend.
    for _ in range(50):
        assert client.report(40.7484, -73.9857, "u1") == r1
    assert abs(client._spent["u1"] - math.log(4)) < 1e-12

    # 4. remap is pure output post-processing: an out-of-bounds point clamps in.
    assert client._remap(41.5, -60.0) == (40.80, -73.93)

    # 5. budget fails closed after 3 distinct locations for one user.
    client.report(40.7100, -74.0100, "u2")
    client.report(40.7200, -74.0000, "u2")
    client.report(40.7300, -73.9900, "u2")
    try:
        client.report(40.7900, -73.9400, "u2")   # 4th distinct cell
    except BudgetExhausted:
        pass
    else:
        raise AssertionError("budget must halt the 4th fresh release")

    print("all geo-indistinguishability client invariants hold")


if __name__ == "__main__":
    _validate()

Assertion 3 is the one most implementations lack: without the cache, report would return 50 independent perturbations whose mean converges on the true coordinate as $1/\sqrt{n}$, and the $\ln 4$ guarantee would be worth a fraction of its nominal value after a busy afternoon.

Per-user cache hit / miss

Planar-Laplace perturb ε = ℓ / r

Remap into bounds project to valid cell never reject

Cache + debit store report spend ℓ of budget

Release to LBS noisy report only The true coordinate never leaves the client; only the remapped, budgeted report is released.

Incident Response and Edge Cases

• Reports drifting into the sea or a neighbouring jurisdiction. A large noise draw near a coastal or border cell projects onto the same boundary edge repeatedly, and analysts notice a suspicious line of points along the bbox. Detection: histogram released points against the bounds; a spike on an edge signals heavy clamping. Remediation: this is a utility problem, not a privacy breach — the projection is still valid post-processing. Upgrade _remap to an optimal spatial remap that redistributes boundary mass inward, or widen $r$ so fewer samples escape.
• A developer “fixes” out-of-bounds points with a resample loop. Someone replaces _remap with while not in_bounds: resample(). This silently reintroduces secret-dependent conditioning and voids the metric-DP guarantee near every boundary. Detection: code review for any resampling keyed on the region test; a property test near a boundary will show the likelihood ratio exceeding $e^{\varepsilon d}$. Remediation: revert to output-only remapping and add a lint rule forbidding rejection against the service region.
• Correlation leakage after a cache flush or across cell edges. A cache eviction, a process restart, or a user standing exactly on an anchor-cell boundary yields two independent perturbations of one location — the exact averaging attack the cache exists to stop. Detection: monitor per-user distinct-cell counts against expected mobility; a stationary user emitting many fresh reports is the tell. Remediation: persist the cache across restarts, and snap to cell centroids with hysteresis so jitter at an edge does not flip the anchor. Tie eviction TTL to the privacy budget window rather than to memory pressure.
• Budget exhaustion during an active session. A genuinely mobile user visits more than $B/\ell$ distinct cells and report starts raising BudgetExhausted. Remediation: fail closed — return the last cached report or a coarsened cell, never an un-noised coordinate. Reset the accountant on a fixed rolling window aligned to the retention policy, and coarsen the anchor grid (larger $c$) to spend less per journey.

Frequently Asked Questions

Related

• Geo-Indistinguishability for Location Privacy — the parent guide defining the mechanism this client operationalises.
• Planar Laplace Noise for Location Privacy — the inverse-CDF sampling math the client treats as a black box.
• Privacy Budget Management — how per-user budgets, windows, and exhaustion policy are accounted.
• Comparing Central vs Local Differential Privacy for GIS — why client-side geo-indistinguishability is a local-DP deployment with no trusted curator.
• Differential Privacy for Geospatial Data — the section tying spatial noise, aggregation, and trajectory privacy together.

Up: Geo-Indistinguishability for Location Privacy · Differential Privacy for Geospatial Data