Spatial Noise Mechanisms

A city transport authority wants to publish a nightly dashboard of trip counts, average dwell times, and fleet-centroid positions per zone — numbers that are individually harmless but, released exactly, let an analyst difference two nights and recover whether one specific vehicle visited one specific address. Spatial noise mechanisms are the additive-perturbation layer that makes that release safe: before any aggregate leaves the trusted curator, calibrated random noise is added at a scale derived from the query’s sensitivity and the privacy parameter $\varepsilon$, so the published number is provably indistinguishable whether or not any single subject contributed. This guide covers the two workhorse mechanisms that back almost every differentially private spatial release — the Laplace mechanism and the Gaussian mechanism — how to compute the $L_1$ and $L_2$ sensitivity of real spatial queries, and how to pick, calibrate, sample, and validate the noise without silently voiding the guarantee.

Key concept. Noise magnitude is not a tuning dial you turn until the chart looks smooth — it is fixed by the query’s worst-case sensitivity and your $\varepsilon$. Get the sensitivity wrong and you either over-noise (destroying utility) or, far worse, under-noise and publish a release that carries no real guarantee. Every spatial noise mechanism is therefore a sensitivity computation first and a random draw second.

This page is the mechanism foundation for the Differential Privacy for Geospatial Data section. It stops at the additive-noise primitives; two child guides carry the specialisations forward. When the quantity you are protecting is a location rather than a scalar aggregate — a reported coordinate that must stay plausibly anywhere within a radius — the isotropic two-dimensional variant covered in planar Laplace noise for location privacy replaces the per-axis scalar draw here. When you are tuning the Gaussian $\sigma$ against a long composition schedule for map tiles or dashboards, calibrating Gaussian noise for spatial aggregates works through the accountant math in detail. Downstream, the noisy counts these mechanisms produce become the input to differentially private spatial aggregation.

Prerequisites & Environment

The reference code needs only numpy for sampling and math for the calibration constants; geopandas/shapely are assumed available for the coordinate-clamping helpers but are not required to run the mechanism itself. Three things must be in place before you draw a single sample:

• A canonical coordinate frame. All examples assume EPSG:4326 decimal degrees. Sensitivity of any coordinate-valued query depends on the range of the input, so the projection and its units must be fixed and known — a stray reprojection to Web Mercator metres silently multiplies every sensitivity by roughly $10^5$ and invalidates the calibration.
• A declared neighboring relation. Differential privacy is defined against a notion of neighboring datasets. You must decide up front whether “neighboring” means add-or-remove one record (unbounded DP) or replace one record with another (bounded DP); the two give different sensitivities for the same query, and mixing them is a common way to accidentally halve your noise.
• A privacy-budget accountant. A single release spends $(\varepsilon, \delta)$; a dashboard spends it repeatedly. Stand up a ledger — a basic-composition tracker at minimum, a Rényi-DP accountant for anything with many queries — and tie its ceiling to a concrete control before any release runs. The mechanics of that ledger, and what to do when it runs dry, live in privacy budget management.

Step 1: Define the Query and the Neighboring Relation

A mechanism protects a specific function $f$ evaluated against a specific neighboring relation. Pin both down as data before you reason about noise, because “the sensitivity of a count” is meaningless until you say what one person can change. Under unbounded DP a single subject can add or delete one row; under bounded DP they can swap one row’s value. The snippet below encodes the query and relation explicitly so the sensitivity step has no hidden assumptions.

from __future__ import annotations

from dataclasses import dataclass
from enum import Enum
from typing import Callable
import numpy as np


class Neighboring(Enum):
    """How one data subject may perturb the dataset."""
    UNBOUNDED = "add_remove_one"   # add or delete one record
    BOUNDED = "replace_one"        # substitute one record's value


@dataclass(frozen=True)
class SpatialQuery:
    """A vector-valued spatial aggregate and the assumptions its
    sensitivity depends on. `coord_bounds` is the clamped (min, max)
    range of each contributed value; it is what makes sums and means
    bounded-sensitivity rather than unbounded."""
    name: str
    fn: Callable[[np.ndarray], np.ndarray]   # dataset -> query answer(s)
    neighboring: Neighboring
    coord_bounds: tuple[float, float]        # (lo, hi) per contributed value
    n_records: int                           # denominator for mean-type queries


def zone_trip_count(rows: np.ndarray) -> np.ndarray:
    """Count of trip records in a zone; each record contributes 1."""
    return np.array([float(rows.shape[0])])


TRIP_COUNT = SpatialQuery(
    name="nightly_zone_trip_count",
    fn=zone_trip_count,
    neighboring=Neighboring.UNBOUNDED,   # a subject adds/removes their trip
    coord_bounds=(0.0, 1.0),             # each record contributes exactly 1
    n_records=0,                         # unused for counts
)

For a count under unbounded DP, one added or removed record moves the answer by exactly 1 — the coord_bounds of (0, 1) encodes that unit contribution. The moment the query is a sum or a mean of coordinates, that contribution stops being 1 and starts depending on how wide the coordinate range is, which is exactly what Step 2 formalises.

Step 2: Compute the Sensitivity

Sensitivity is the maximum change in the query answer between any two neighboring datasets, measured in a norm. The Laplace mechanism uses $L_1$ sensitivity $\Delta_1 f = \max \lVert f(D) - f(D') \rVert_1$; the Gaussian mechanism uses $L_2$ sensitivity $\Delta_2 f = \max \lVert f(D) - f(D') \rVert_2$. For a scalar query the two coincide; for a vector query (a 2D centroid, a multi-cell histogram) they differ, and that difference is the whole reason to prefer one mechanism over the other.

The critical spatial subtlety is unbounded vs bounded sensitivity. A raw coordinate sum has unbounded sensitivity: nothing stops one record from sitting at longitude $-179.999$ and dominating the total, so a single subject can move the answer arbitrarily far and no finite noise suffices. You make it bounded by clamping every contributed coordinate into a declared box before aggregating — truncation is itself a legitimate, data-independent pre-processing step. After clamping to width $W = \text{hi} - \text{lo}$:

• Count — $\Delta_1 = \Delta_2 = 1$ (unbounded DP); $2$ under bounded DP if a replacement can flip membership of two cells.
• Bounded sum of a clamped attribute in $[\text{lo}, \text{hi}]$ — $\Delta_1 = W$ (unbounded); $\Delta_1 = W$ under bounded replace as well, since a swap changes the sum by at most the range.
• Coordinate mean over a fixed denominator $n$ of values clamped to width $W$ — $\Delta_1 = W / n$ per axis under bounded DP.
• Bounded-box centroid (2D mean of clamped lat/lon) — per-axis $\Delta_1 = W / n$, and because both axes can move at once the combined $\Delta_2 = \sqrt{2}\,W / n$.

def l1_l2_sensitivity(query: SpatialQuery, n_axes: int = 1) -> tuple[float, float]:
    """Return (L1, L2) sensitivity for a clamped spatial query.

    Clamping to `coord_bounds` is what bounds these values; without it
    a single extreme coordinate makes sum/mean sensitivity infinite.
    """
    lo, hi = query.coord_bounds
    width = hi - lo                       # per-value range after clamping
    if query.name.endswith("count"):
        per_axis = 1.0
    elif "sum" in query.name:
        per_axis = width                  # one record moves the sum by <= W
    elif "mean" in query.name or "centroid" in query.name:
        if query.n_records <= 0:
            raise ValueError("mean/centroid queries need n_records > 0")
        per_axis = width / query.n_records
    else:
        raise ValueError(f"unknown query family: {query.name}")
    # Bounded DP (replace) can move two cells at once for membership queries.
    if query.neighboring is Neighboring.BOUNDED and query.name.endswith("count"):
        per_axis *= 2.0
    l1 = per_axis * n_axes                 # axes can shift independently
    l2 = per_axis * (n_axes ** 0.5)        # L2 combines in quadrature
    return l1, l2

For the nightly trip count this returns (1.0, 1.0); for a two-axis bounded-box centroid over $n = 500$ clamped points spanning a $0.02°$ zone it returns roughly (8.0e-5, 5.66e-5), and the gap between those two numbers is precisely what the mechanism choice trades on.

Step 3: Choose Laplace vs Gaussian

The decision rests on two questions: can you tolerate a $\delta > 0$ failure probability, and how many queries will compose? The Laplace mechanism gives pure $\varepsilon$-DP ($\delta = 0$) and calibrates to $L_1$ — ideal for a single low-dimensional release where a hard guarantee matters. The Gaussian mechanism gives $(\varepsilon, \delta)$-DP, calibrates to $L_2$, and composes far more gracefully: over $k$ queries the $L_2$ sensitivity grows as $\sqrt{k}$ rather than the $k$ that $L_1$ suffers, so high-dimensional or repeatedly-queried releases end up quieter under Gaussian noise despite the $\delta$ concession. The relationship to central-vs-local regimes and the broader model choice is laid out in the privacy model comparison; here we decide purely between the two additive mechanisms.

def choose_mechanism(
    l1: float,
    l2: float,
    delta_tolerance: float,
    composed_queries: int,
) -> str:
    """Pick 'laplace' or 'gaussian' from the delta budget and the
    composition plan. High-dimensional or heavily-composed releases
    favour Gaussian because L2 sensitivity grows as sqrt(k), not k."""
    if delta_tolerance <= 0.0:
        return "laplace"                  # pure epsilon-DP is mandatory
    # Where L1 >> L2 (many independently-moving output dimensions),
    # Gaussian's quadrature scaling wins under composition.
    high_dimensional = l1 > (2.0 ** 0.5) * l2 + 1e-12
    if high_dimensional and composed_queries >= 2:
        return "gaussian"
    return "laplace" if composed_queries == 1 else "gaussian"

A single scalar count with $\delta = 0$ always routes to Laplace; a 256-cell density grid queried nightly for a month routes to Gaussian, where the $\sqrt{k}$ composition saving is large enough to matter.

Step 4: Calibrate the Scale and Sigma

With sensitivity and mechanism chosen, calibration is arithmetic. The Laplace scale is $b = \Delta_1 f / \varepsilon$. The Gaussian standard deviation must satisfy the classic analytic bound $\sigma \ge \Delta_2 f \sqrt{2 \ln(1.25/\delta)} / \varepsilon$, valid for $\varepsilon \le 1$; outside that range use an analytic-Gaussian or RDP calibration instead of the closed form. The SpatialNoiseMechanism class below holds both draws plus a sensitivity helper, and every call refuses to run without a positive $\varepsilon$ so a misconfigured budget cannot silently produce zero noise.

import math
from typing import Optional


class SpatialNoiseMechanism:
    """Additive-noise mechanisms for differentially private spatial
    releases. Laplace calibrates to L1 sensitivity and gives pure
    epsilon-DP; Gaussian calibrates to L2 and gives (epsilon, delta)-DP.
    A single RNG is threaded through so releases are reproducible in
    tests but seeded from the OS CSPRNG in production."""

    def __init__(self, rng: Optional[np.random.Generator] = None) -> None:
        # Default to a CSPRNG-seeded generator; injectable for tests.
        self.rng: np.random.Generator = rng or np.random.default_rng()

    @staticmethod
    def sensitivity(query: SpatialQuery, n_axes: int = 1) -> tuple[float, float]:
        """Thin wrapper so callers get (L1, L2) from the query object."""
        return l1_l2_sensitivity(query, n_axes=n_axes)

    def laplace(self, answer: np.ndarray, l1: float, epsilon: float) -> np.ndarray:
        """Add Laplace(0, b) noise with b = L1 / epsilon -> epsilon-DP."""
        if epsilon <= 0.0:
            raise ValueError("epsilon must be > 0")
        if l1 <= 0.0:
            raise ValueError("L1 sensitivity must be > 0; clamp inputs first")
        scale: float = l1 / epsilon                       # b = Δ₁f / ε
        noise = self.rng.laplace(loc=0.0, scale=scale, size=np.shape(answer))
        return np.asarray(answer, dtype=float) + noise

    def gaussian(
        self, answer: np.ndarray, l2: float, epsilon: float, delta: float
    ) -> np.ndarray:
        """Add N(0, sigma^2) noise meeting the analytic (eps, delta)
        bound sigma >= L2 * sqrt(2 ln(1.25/delta)) / epsilon."""
        if epsilon <= 0.0 or not (0.0 < delta < 1.0):
            raise ValueError("require epsilon > 0 and 0 < delta < 1")
        if epsilon > 1.0:
            # The closed form is only proven for eps <= 1; fail loud
            # rather than under-noise on a bound that no longer holds.
            raise ValueError("analytic bound needs epsilon <= 1; use RDP calibration")
        if l2 <= 0.0:
            raise ValueError("L2 sensitivity must be > 0; clamp inputs first")
        sigma: float = l2 * math.sqrt(2.0 * math.log(1.25 / delta)) / epsilon
        noise = self.rng.normal(loc=0.0, scale=sigma, size=np.shape(answer))
        return np.asarray(answer, dtype=float) + noise

Keeping the RNG injectable is what lets the validation harness assert distributional properties deterministically while production still seeds from os.urandom via NumPy’s default. The scale and $\sigma$ are never rounded or floored “to be safe” — rounding down weakens the guarantee, and rounding up is wasted utility you should instead spend by lowering $\varepsilon$.

Step 5: Sample and Post-Process

Drawing the noise is one line; the discipline is in what you do after. A raw noisy count can come out negative or fractional, which is nonsensical for a trip tally. Clamping to non-negativity and rounding are post-processing — they operate only on the already-private release and touch no raw data, so by the post-processing immunity theorem they consume zero additional budget. That is why the clamp sits after the mechanism in the diagram, not inside it.

def release_zone_counts(
    raw_counts: np.ndarray,
    mech: SpatialNoiseMechanism,
    epsilon: float,
) -> np.ndarray:
    """Full single-query path: noise -> non-negativity clamp -> round.

    Every step after `mech.laplace` is post-processing and spends no
    further epsilon, so the clamp and round are 'free'."""
    l1, _ = mech.sensitivity(TRIP_COUNT)            # (1.0, 1.0) for a count
    noisy = mech.laplace(raw_counts, l1=l1, epsilon=epsilon)
    non_negative = np.maximum(noisy, 0.0)           # free post-processing
    return np.rint(non_negative).astype(int)        # integer counts, still DP


if __name__ == "__main__":
    m = SpatialNoiseMechanism(rng=np.random.default_rng(7))
    published = release_zone_counts(np.array([12.0, 3.0, 0.0, 47.0]), m, epsilon=0.5)
    print("published nightly counts:", published)   # non-negative integers

Post-processing does not let you re-noise or re-query the same raw data for free — that is a fresh mechanism invocation and a fresh budget debit. The clamp is free precisely because it never looks at the underlying dataset again.

Threat Model Considerations

Additive noise defends against a specific adversary, and it is worth naming what it does and does not stop:

• Differencing / composition attacks. The primary threat: an analyst issues overlapping spatial queries and subtracts answers to cancel noise and isolate one subject. A single well-calibrated release is safe, but the cumulative $\varepsilon$ across queries is what actually bounds this — track it in a ledger and refuse queries past the ceiling, exactly as privacy budget management prescribes.
• Under-clamped sensitivity. If raw coordinates reach a sum or mean without clamping, one adversarial record with an extreme coordinate inflates the true sensitivity above what you calibrated to, and the released noise no longer covers it. The clamp is a security control, not a data-cleaning nicety.
• Neighboring-relation confusion. Calibrating to unbounded-DP sensitivity while an auditor assumes bounded-DP (or vice versa) can silently halve or double the effective noise. Declare the relation once and derive every sensitivity from it.
• Insecure RNG. Noise seeded from a predictable PRNG (a fixed seed shipped to production, or a low-entropy source) is reconstructable, letting an adversary subtract the exact noise. Seed from a CSPRNG; the deterministic RNG is for tests only.
• Floating-point noise leakage. Naive laplace implementations leak low-order bits that break the guarantee near the sampling boundary. For high-assurance releases use a snapping or discrete-Laplace mechanism rather than a raw double draw — a concern shared with the geo-indistinguishability samplers in geo-indistinguishability.

Validation & Compliance Checklist

Wire each invariant into CI with a measurable pass criterion rather than trusting a visual check of the output:

1. Sensitivity is bounded — PASS if every sum/mean/centroid query clamps inputs to coord_bounds before aggregation, and an injected extreme-coordinate record does not change the computed $\Delta f$. An unbounded sensitivity is a build-breaker.
2. Scale matches the formula — PASS if the realised Laplace scale equals $\Delta_1 f / \varepsilon$ and the Gaussian $\sigma$ equals $\Delta_2 f \sqrt{2\ln(1.25/\delta)}/\varepsilon$ to floating tolerance, for a grid of $(\varepsilon, \delta)$ values with $\varepsilon \le 1$.
3. Empirical noise distribution — PASS if the sample variance of a large Laplace draw is within tolerance of $2b^2$ and the Gaussian draw within tolerance of $\sigma^2$; a mis-scaled draw is caught here.
4. Post-processing is free — PASS if the non-negativity clamp and rounding are applied only to mechanism output and the budget ledger records exactly one debit per raw-data query, never one per post-processing step.
5. Guard rails fire — PASS if $\varepsilon \le 0$, $\delta \notin (0,1)$, $\varepsilon > 1$ on the analytic Gaussian, and zero sensitivity each raise rather than silently producing a degenerate (noiseless) release.
6. Budget accounting — PASS if composed spend stays under the $(\varepsilon, \delta)$ ceiling tied to a concrete control in the compliance mapping, cross-checked against spatial sensitivity scoring models so tighter tiers get smaller $\varepsilon$.

The harness below exercises invariants 2, 3, and 5 directly and is safe to run in CI:

def _validate() -> None:
    rng = np.random.default_rng(2024)
    mech = SpatialNoiseMechanism(rng=rng)

    # Invariant 5: guard rails must raise, not under-noise.
    for bad in (lambda: mech.laplace(np.zeros(1), l1=1.0, epsilon=0.0),
                lambda: mech.gaussian(np.zeros(1), l2=1.0, epsilon=2.0, delta=1e-5),
                lambda: mech.gaussian(np.zeros(1), l2=1.0, epsilon=0.5, delta=1.5)):
        try:
            bad()
        except ValueError:
            pass
        else:
            raise AssertionError("invalid parameters must raise")

    # Invariant 3: empirical spread matches the calibrated scale.
    l1, l2 = 2.0, 2.0
    eps, delta = 0.5, 1e-5
    big = np.zeros(400_000)
    lap = mech.laplace(big, l1=l1, epsilon=eps)
    b = l1 / eps                                   # expected Laplace scale
    assert abs(lap.var() - 2.0 * b ** 2) / (2.0 * b ** 2) < 0.05

    gau = mech.gaussian(big, l2=l2, epsilon=eps, delta=delta)
    sigma = l2 * math.sqrt(2.0 * math.log(1.25 / delta)) / eps
    assert abs(gau.var() - sigma ** 2) / (sigma ** 2) < 0.05   # Invariant 2 + 3

    # Invariant 4 spot-check: clamp never makes a count negative.
    counts = release_zone_counts(np.array([0.0, 1.0, 9.0]), mech, epsilon=0.5)
    assert (counts >= 0).all()

    print("all spatial-noise-mechanism invariants hold")


if __name__ == "__main__":
    _validate()

Failure Modes & Remediation

Noise mechanisms fail quietly — a mis-scaled release still returns plausible numbers — so the failures below are the ones that surface only under audit or attack:

• Unbounded sensitivity from unclamped coordinates. A sum or mean runs on raw lat/lon, so one extreme record dwarfs the calibrated noise. Detection: assert coord_bounds are applied before aggregation and that computed $\Delta f$ is finite. Remediation: clamp/truncate every contributed coordinate to the declared box before the query, and re-derive sensitivity.
• Wrong norm for the mechanism. Feeding $L_1$ sensitivity to the Gaussian $\sigma$ (or $L_2$ to the Laplace scale) mis-calibrates a vector release. Detection: type/route the sensitivity through choose_mechanism so the norm and mechanism always match. Remediation: recompute with the norm the chosen mechanism requires.
• Analytic Gaussian used with $\varepsilon > 1$. The closed-form bound is unproven there and under-noises. Detection: the guard raises. Remediation: switch to an analytic-Gaussian or RDP calibration and re-run the composition accounting.
• Budget double-spend or omission. Post-processing steps get charged (wasting budget) or raw-data queries go unlogged (silently blowing the ceiling). Detection: reconcile ledger debits against distinct raw-data invocations. Remediation: debit once per mechanism call, never per clamp/round; halt releases when the ceiling is reached — the exhaustion-recovery playbook is in privacy budget management.
• Seed reuse across releases. A fixed RNG seed shipped to production makes noise subtractable. Detection: assert the production path uses np.random.default_rng() with no explicit seed. Remediation: seed from the OS CSPRNG and reserve deterministic seeds for tests.

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 compose into one release pipeline.

• Planar Laplace Noise for Location Privacy — the isotropic 2D variant for perturbing a location rather than a scalar aggregate.
• Calibrating Gaussian Noise for Spatial Aggregates — tuning sigma against a long composition schedule with an RDP accountant.
• Differentially Private Spatial Aggregation — where these noisy counts become heatmaps and histograms.
• Geo-Indistinguishability for Location Privacy — the metric-DP framing that generalises planar Laplace.
• Privacy Budget Management — tracking cumulative epsilon and delta across composed releases.
• Spatial Sensitivity Scoring Models — mapping a measured risk tier onto the epsilon each release may spend.

Up: Differential Privacy for Geospatial Data