Local Differential Privacy for Mobile Clients

Local differential privacy (LDP) applies the randomization step on the device itself, so a mobile client perturbs its own location into a report that already satisfies a formal privacy guarantee before anything leaves the handset — the aggregator never receives, and never has to be trusted with, a true coordinate.

Central vs. Local: Where the Noise Lives # permalink

The defining choice in any differential privacy for location data deployment is where the randomization happens. In the central model a trusted curator holds every raw location and injects noise only at release time. In the local model each device is its own curator: it randomizes before upload, and the operator that runs the aggregation service is treated as untrusted. That single architectural difference changes the threat model, the noise magnitude, and the number of users you need.

The three techniques that make LDP practical for location data are randomized response over a discrete cell alphabet, RAPPOR-style unary encoding of the set of visited cells, and geo-indistinguishability, which calibrates noise to metric distance rather than to a discrete alphabet. This guide focuses on randomized response over an H3 cell index, because it is the simplest mechanism that composes cleanly and de-biases exactly.

Algorithmic Specification # permalink

Local differential privacy definition # permalink

A randomized mechanism $M$ satisfies $\varepsilon$-local differential privacy if, for every pair of possible client inputs $v, v'$ and every possible output $y$:

The crucial difference from the central definition is that the bound holds for the single client’s two possible true values, with no reference to a dataset of neighbours. Each device is self-contained: its report reveals its own value only up to the factor $e^{\varepsilon}$, so the aggregator learns nothing about any individual beyond that ratio, no matter how it behaves.

Binary randomized response # permalink

For a single yes/no fact — for example, “did this device visit cell $C$?” — the device reports the truth with probability $p$ and lies with probability $1-p$, where:

This is the classic randomized-response design. At $\varepsilon = \ln 3 \approx 1.099$, $p = 0.75$: the device tells the truth three times out of four, and any single answer is deniable.

Generalized randomized response over a cell alphabet # permalink

Location reporting is rarely a single bit. When the device must report which of $d$ H3 cells it occupies, generalized randomized response (GRR, also called direct encoding) keeps the true cell with probability $p$ and otherwise reports a uniformly chosen wrong cell with probability $q$:

The larger the alphabet $d$, the smaller $p$ becomes at fixed $\varepsilon$ — spreading the same privacy budget across more candidate cells is what makes large cell sets expensive. RAPPOR-style unary encoding (one bit per cell, each flipped independently) is an alternative that keeps per-cell cost constant and is preferable when $d$ is very large; GRR is optimal when $d < 3e^{\varepsilon} + 2$.

Geo-indistinguishability # permalink

Geo-indistinguishability generalizes LDP to continuous space by scaling the indistinguishability level to metric distance. A mechanism is $\varepsilon$-geo-indistinguishable if, for any two true locations $x, x'$ separated by distance $r$:

Here $\varepsilon$ has units of privacy per metre, and the effective protection within radius $r$ is $\varepsilon \cdot r$: nearby points are nearly indistinguishable while distant points are separable. The planar Laplace mechanism realizes this by drawing a displacement radius from the density $\propto \varepsilon^2 r\, e^{-\varepsilon r}$. Geo-indistinguishability is the right tool when the released quantity is a perturbed point rather than a cell histogram; the rest of this guide uses discrete randomized response because it de-biases exactly into frequency estimates.

Unbiased frequency estimation # permalink

Randomized reports are biased toward uniformity, so the server must invert the randomization. If $\tilde{c}_v$ is the raw count of reports naming cell $v$ across $n$ users, the unbiased estimate of the true count is:

and the estimated frequency is $\hat{f}_v = \hat{c}_v / n$. This estimator is exactly unbiased: $\mathbb{E}[\hat{c}_v] = c_v$, the true count. Its variance, for the low-frequency regime that dominates a large cell set, is:

so the standard error falls as $1/\sqrt{n}$ and grows with the alphabet size $d$.

Parameter reference # permalink

Prerequisites & Data Requirements # permalink

Before building an LDP pipeline, confirm the following:

• On-device cell encoding. The client must map its raw coordinate to a discrete cell index that both sides agree on in advance. Use the H3 hierarchical hex grid: h3.latlng_to_cell(lat, lng, res) returns a stable string index. The cell alphabet — the fixed, ordered list of candidate H3 cells the device may report — must be identical on client and server, versioned, and shipped with the app. Do not let the alphabet depend on live data.
• CRS. Encode from WGS84 (EPSG:4326) latitude/longitude, which is what device GPS emits; H3 handles the spherical geometry internally, so no projection to a metric CRS such as EPSG:3857 or a UTM zone is required before indexing. Reprojection only matters if you later render recovered frequencies onto a metric basemap.
• Minimum population. Because error scales as $1/\sqrt{n}$, LDP needs large $n$. As a rule of thumb, target at least $10^4$ reports per released cell for coarse heatmaps and $10^5$+ for fine-grained ones. Small pilots will produce estimates dominated by noise.
• Python dependencies. Client-side simulation needs numpy and h3 (v4 API). Server-side aggregation and de-biasing use pandas for the count table and numpy for the arithmetic. No geopandas is required for the core protocol, though it is useful for plotting recovered surfaces.
• Composition budget. Decide up front how many reports each device may send over the retention window, because privacy budgets compose — every additional report spends more $\varepsilon$ against the same person.

Step-by-Step Implementation # permalink

Step 1 — Encode the location into an H3 cell on the device # permalink

The client converts its raw fix to an H3 index and finds that cell’s position in the shared alphabet. Only the index leaves the device — never the latitude/longitude.

import h3  # h3 v4 API
import numpy as np
from typing import Sequence

# WGS84 (EPSG:4326) input straight from the device GPS.
H3_RESOLUTION: int = 8  # ~0.46 km^2 cells; res drives the alphabet size d

def encode_location(lat: float, lon: float, alphabet: Sequence[str]) -> int:
    """Map a raw WGS84 fix to an index into the shared H3 cell alphabet.

    The raw coordinate is used only locally; the returned integer index is
    the sole quantity eligible to leave the device (after randomization).
    """
    cell: str = h3.latlng_to_cell(lat, lon, H3_RESOLUTION)
    # Cells outside the served region collapse to a sentinel "other" bucket
    # so the alphabet stays closed and the de-biasing math remains exact.
    return alphabet.index(cell) if cell in alphabet else len(alphabet) - 1

The alphabet is a fixed list; the final slot is an “other” bucket so that any real-world cell maps somewhere and the domain size $d$ stays constant.

Step 2 — Apply generalized randomized response on the device # permalink

The device now perturbs its true index. This is the step that spends the local $\varepsilon$; after it runs, the report is already private.

def randomize_report(true_index: int, epsilon: float, d: int,
                     rng: np.random.Generator) -> int:
    """Generalized randomized response over a d-cell alphabet.

    Keeps the true cell with probability p = e^eps / (e^eps + d - 1);
    otherwise reports a uniformly random *different* cell. After this call
    the output alone satisfies epsilon-local differential privacy, so the
    raw location is unrecoverable from any single report.
    """
    p_keep = np.exp(epsilon) / (np.exp(epsilon) + d - 1)
    if rng.random() < p_keep:
        return true_index  # tell the truth
    # Lie: pick uniformly among the d-1 other cells
    other = rng.integers(0, d - 1)
    return other if other < true_index else other + 1

Because randomization happens here, on the handset, the aggregator in Step 4 can be fully untrusted: it only ever sees the output of randomize_report.

Step 3 — Upload only the randomized index # permalink

The transport payload is a single integer (or its H3 string), never the coordinate. In a real client this is the only field written to the network; the raw fix is discarded. Keeping the raw coordinate on the device is what lets LDP support GDPR data-minimisation obligations — there is no central store of true locations to breach.

Step 4 — Aggregate and de-bias server-side # permalink

The server tallies the noisy reports, then inverts the randomization with the unbiased estimator. This is where pandas earns its place.

import pandas as pd

def estimate_frequencies(reports: np.ndarray, epsilon: float, d: int) -> pd.DataFrame:
    """Recover unbiased per-cell frequencies from randomized reports.

    reports: 1-D array of randomized cell indices from n devices.
    Returns a DataFrame with the raw (biased) and de-biased frequencies.
    The de-biasing uses c_hat = (observed - n*q) / (p - q), which is
    exactly unbiased for the true per-cell count.
    """
    n = reports.size
    p = np.exp(epsilon) / (np.exp(epsilon) + d - 1)
    q = 1.0 / (np.exp(epsilon) + d - 1)

    observed = np.bincount(reports, minlength=d).astype(float)
    debiased_count = (observed - n * q) / (p - q)          # unbiased counts
    debiased_freq = np.clip(debiased_count / n, 0.0, None)  # frequencies >= 0

    return pd.DataFrame({
        "cell_index": np.arange(d),
        "raw_freq": observed / n,
        "debiased_freq": debiased_freq,
    })

The clip to non-negative values is a cosmetic post-processing step — de-biased counts for genuinely empty cells fluctuate around zero and can come out slightly negative. Post-processing a DP output never weakens the guarantee, so clamping is safe.

Validation & Re-identification Testing # permalink

Two checks matter: that recovery is unbiased, and that the error matches the $1/\sqrt{n}$ theory. Simulate a known ground-truth distribution, run the full pipeline, and compare.

def validate_recovery(true_freq: np.ndarray, epsilon: float,
                      n_users: int, seed: int = 0) -> dict:
    """Simulate n_users under a known distribution and check recovery.

    Confirms the estimator is unbiased and that the mean absolute error
    tracks the theoretical standard error sqrt((d-2+e^eps)/(n (e^eps-1)^2)).
    """
    rng = np.random.default_rng(seed)
    d = true_freq.size

    # Draw each user's true cell from the ground-truth distribution,
    # then randomize on-device.
    true_cells = rng.choice(d, size=n_users, p=true_freq)
    reports = np.array([randomize_report(int(c), epsilon, d, rng)
                        for c in true_cells])

    est = estimate_frequencies(reports, epsilon, d)["debiased_freq"].to_numpy()

    theo_se = np.sqrt((d - 2 + np.exp(epsilon)) /
                      (n_users * (np.exp(epsilon) - 1) ** 2))
    return {
        "max_abs_error": float(np.max(np.abs(est - true_freq))),
        "mean_abs_error": float(np.mean(np.abs(est - true_freq))),
        "theoretical_se": float(theo_se),
    }

# Example: 200-cell alphabet, eps=2, 200k users
rng = np.random.default_rng(1)
tf = rng.dirichlet(np.ones(200))
print(validate_recovery(tf, epsilon=2.0, n_users=200_000))
# mean_abs_error should sit within ~1x of theoretical_se

If mean_abs_error is close to theoretical_se, the estimator is calibrated. If it is many times larger, either $n$ is too small for the chosen alphabet or the alphabet drifted between client and server. Because raw locations never leave the device, there is no auxiliary-join surface to test on the client side; residual re-identification risk lives entirely in the released aggregate, so the linkage test is: can any published cell frequency be tied back to a small, identifiable population? Suppress released cells whose de-biased count is below a documented floor before publishing.

Common Failure Modes & Gotchas # permalink

Underpowered populations. LDP’s cardinal failure is deploying it with too few users. At $\varepsilon = 1$ over a 1 000-cell alphabet, the per-cell standard error only drops below one percentage point somewhere north of $10^6$ users. Pilots with a few thousand devices produce histograms that are almost pure noise. Size $n$ against the variance formula before shipping.

Longitudinal composition. A single report is $\varepsilon$-LDP, but a device that reports every hour spends $\varepsilon$ each time. Under basic composition, 24 daily reports at $\varepsilon = 1$ leak at $\varepsilon = 24$ — effectively no privacy. Mitigate with memoization (report a persistent randomized answer for a stable location rather than re-randomizing), a per-device daily budget, or Rényi/zCDP accounting. This is the single most common way real LDP deployments quietly lose their guarantee.

Oversized alphabets. Because variance grows with $d$, pushing H3 resolution higher to get prettier maps inflates error quadratically in the standard error. If you need resolution 9 detail, either move to RAPPOR-style unary encoding or use a hierarchical scheme that reports coarse cells first and refines only well-populated regions.

Alphabet skew between client and server. The de-biasing math assumes both sides share the exact same ordered alphabet and domain size $d$. A mismatched build — a client shipping an older cell list — silently corrupts $q$ and biases every estimate. Version the alphabet and reject reports tagged with an unknown version.

Treating clipped negatives as real absences. De-biased counts near zero are noisy; a slightly negative value clipped to zero does not mean the cell is empty. Do not publish per-cell presence/absence from a single LDP release.

Compliance Alignment # permalink

Because the untrusted-aggregator model removes the trusted curator, an LDP deployment’s audit trail centres on two artefacts: the per-report $\varepsilon$ and the composition policy that bounds cumulative exposure per device over the retention window. Document both alongside the shared alphabet version, and map the released aggregate against your standard GDPR/CCPA compliance record.

FAQ # permalink

How is local differential privacy different from central differential privacy?

In the central model a trusted curator collects raw locations and applies noise at release time, so the true data physically exists in one place and the curator must be trusted. In the local model each device randomizes its own report before upload, so no true location is ever centralized and the aggregator can be untrusted. The price is noise: for the same $\varepsilon$, local DP is far noisier, which is why it needs many more users than a central budget allocation.

Why does local differential privacy need so many users?

Every report carries its own independent randomization, so estimation error shrinks only as $1/\sqrt{n}$. The central model adds a single noise draw per released statistic — using the Laplace mechanism for coordinate data, for instance — so its error is roughly constant in $n$. Matching central accuracy under LDP typically takes tens of thousands to millions of reports per cell.

Can I use randomized response and geo-indistinguishability together?

Yes. Geo-indistinguishability is the natural choice when the device must emit a perturbed point (continuous space, metric distance), while randomized response fits cell histograms that de-bias into frequencies. Many deployments use geo-indistinguishability for point queries and randomized response over H3 for aggregate heatmaps, budgeting $\varepsilon$ separately for each.

How much does keeping data on the device help with utility loss?

It does not reduce utility loss — LDP is strictly noisier than central DP for the same $\varepsilon$ — but it removes the trusted-curator risk entirely. The utility cost is real: study the accuracy vs. utility tradeoffs in geospatial DP before committing to the local model, and reserve it for cases where you genuinely cannot trust a central aggregator.

Related # permalink

• Privacy Budget Allocation for Spatial Queries — the central-model counterpart and how ε composes across reports
• Laplace & Gaussian Noise for Coordinate Data — the noise mechanism used when a trusted curator adds noise centrally
• Accuracy vs. Utility Tradeoffs in Geospatial DP — quantifying the utility cost the local model pays
• Implementing Randomized Response for Location Check-ins — a focused, worked walkthrough of the encode-randomize-debias loop
• Compliance Mapping for GDPR & CCPA Location Data — documenting the on-device guarantee for regulators

← Back to Differential Privacy for Location Data