Local Differential Privacy for Mobile Clients

Central differential privacy assumes a collector that sees raw coordinates and is trusted to add noise honestly. Local differential privacy (LDP) removes that assumption: every device perturbs its own report before it leaves the handset, so the server never holds a true location for anyone. The price is steep and unavoidable — error grows with the square root of the reporting population rather than staying constant — and the engineering problem is entirely about paying that price where it is affordable and refusing to deploy LDP where it is not. This guide sits under Differential Privacy for Geospatial Data and should be read alongside the trade worked through in comparing central vs local differential privacy for GIS.

The scenario throughout: a navigation app with several million installs wants to know which grid cells are congested, without ever learning where any individual device was.

Prerequisites

• A population large enough to absorb $\sqrt{n}$ error. LDP is a large-numbers technique. For a per-cell count to be useful within a few percent at $\varepsilon = 2$, the cell needs tens of thousands of reporting devices. If your busiest cell has 300, stop here and use a central or federated design.
• Client-side execution you control. The randomiser runs on the device, so the guarantee is only as good as the client build. A web client whose JavaScript can be swapped by an intermediary provides no guarantee at all.
• A per-client budget store on the device. The budget is spent by the client, so the ledger has to live there too. Server-side accounting cannot see how many times a device reported.
• numpy server-side for the de-biasing estimator; the client side is a few dozen lines of integer arithmetic and a CSPRNG, deliberately, so it can be audited.

Step 1: Discretise before you randomise

LDP mechanisms operate on a finite domain. The domain here is the set of grid cells the client might report, and choosing it is the highest-leverage decision in the whole design, because both the variance and the client’s bandwidth scale with the domain size $d$.

Take the H3 cells covering the service area at the publishing resolution. A metro at resolution 8 is roughly 2,000 cells — a workable domain. The same metro at resolution 10 is nearly 100,000 cells, where a naive randomiser sends 100,000 bits per report and the estimator’s variance is an order of magnitude worse. The right move is almost always to run LDP at a coarse resolution and accept that fine structure is not available under this model at all.

Step 2: Choose the randomiser to match the domain size

Three mechanisms cover nearly every mobile deployment, and they differ in what they send and how the variance scales.

• Direct (generalised) randomised response. The client reports its true cell with probability $p = e^\varepsilon/(e^\varepsilon + d - 1)$ and a uniformly random other cell otherwise. Sends one cell id. Variance grows with $d$, so it is the right choice only for small domains — a few dozen cells, such as districts rather than blocks.
• Unary encoding (RAPPOR-style). The client holds a $d$-bit vector, sets the bit for its cell, then flips every bit independently with a probability derived from $\varepsilon$. Sends $d$ bits. Variance is independent of $d$, which is why it dominates for the medium domains most spatial deployments have — at the cost of bandwidth.
• Local hashing. The client hashes its cell into a much smaller range, reports the hashed value under randomised response, and the server aggregates across the hash family. Sends a hash index and a small value. This is the practical choice once $d$ passes a few thousand, trading a small variance penalty for a large bandwidth saving.

The estimator is the part teams forget. Every one of these mechanisms produces biased raw counts — in unary encoding, an empty cell still accumulates roughly $q \cdot n$ set bits from the flipping — so the server must invert the randomisation before publishing. Publishing raw perturbed counts is the single most common LDP implementation bug, and it produces a map where every cell looks moderately busy.

from __future__ import annotations

import math
import secrets
from dataclasses import dataclass
from typing import Sequence

import numpy as np


@dataclass(frozen=True)
class UnaryParams:
    """Optimised unary encoding: p for the true bit, q for every other bit."""

    epsilon: float
    domain: int

    @property
    def p(self) -> float:
        return 0.5

    @property
    def q(self) -> float:
        # The variance-optimal choice under pure epsilon-LDP for unary encoding.
        return 1.0 / (math.exp(self.epsilon) + 1.0)

    def variance_per_client(self) -> float:
        p, q = self.p, self.q
        return q * (1.0 - q) / ((p - q) ** 2)


def randomise_on_device(cell_index: int, params: UnaryParams) -> bytes:
    """Perturb one report. Runs on the handset; the server never sees the input.

    Uses `secrets` rather than `random` deliberately: a predictable RNG here does
    not degrade the guarantee gracefully, it removes it, because an adversary who
    can replay the stream recovers the true bit exactly.
    """
    if not 0 <= cell_index < params.domain:
        raise ValueError("cell index outside the declared domain")
    bits = bytearray((params.domain + 7) // 8)
    for i in range(params.domain):
        true_bit = i == cell_index
        keep = params.p if true_bit else params.q
        if secrets.randbelow(1_000_000) < int(keep * 1_000_000):
            bits[i // 8] |= 1 << (i % 8)
    return bytes(bits)


def aggregate(reports: Sequence[bytes], params: UnaryParams) -> np.ndarray:
    """Invert the randomisation to get unbiased per-cell frequency estimates."""
    n = len(reports)
    if n == 0:
        return np.zeros(params.domain)
    observed = np.zeros(params.domain)
    for report in reports:
        for i in range(params.domain):
            if report[i // 8] >> (i % 8) & 1:
                observed[i] += 1.0
    p, q = params.p, params.q
    # Unbiased estimator: subtract the expected noise floor, rescale by (p - q).
    return (observed - n * q) / (p - q)


def standard_error(n: int, params: UnaryParams) -> float:
    """Expected standard error of one cell's estimated count."""
    return math.sqrt(n * params.variance_per_client())

Step 3: Budget on the device, not on the server

Under LDP the privacy loss is incurred by the client at the moment it reports, so the ledger belongs on the client. A device that reports its cell every five minutes for a day has made 288 releases; under sequential composition at $\varepsilon = 1$ per release it has spent 288, which is not a privacy guarantee in any meaningful sense.

Two mechanisms make a realistic cadence affordable, and both must be implemented on the device:

• Memoisation. The client randomises a given value once and reuses that same randomised output every time it would report the same value. Repeated reports of an unchanged cell then cost nothing additional, because the adversary sees no new randomness. This is what makes “report every five minutes” viable, and it is the reason the client must store its randomised outputs rather than re-randomising.
• A hard per-epoch cap on distinct values reported. Memoisation protects repetition, not movement: a device that visits 40 distinct cells in a day has made 40 distinct releases. Cap the number of distinct cells a client will report per epoch, and have the client stop reporting when it hits the cap — silently and without signalling, since “this device stopped reporting” is itself an observation.

Step 4: Decide honestly whether LDP is affordable here

The decision to deploy local differential privacy is a sizing calculation, not a preference, and it is worth doing before any code is written because the answer is frequently “no”.

Start from the smallest count the release must distinguish. For a congestion map that is typically a few hundred devices in a cell; for a coverage map it might be a few thousand. The standard error of an LDP estimate scales as $\sqrt{n \cdot \mathrm{Var}}$ where the per-client variance depends only on $\varepsilon$ and the mechanism, so the relative error of a cell holding $c$ of $n$ reporters is roughly $\sqrt{n\,\mathrm{Var}}/c$. Two consequences follow immediately, and both surprise people.

First, adding reporters helps the aggregate and hurts each individual cell’s relative precision unless the cell’s own share grows with it. A national deployment whose reporters are spread across 40,000 cells is worse per cell than a metro deployment with a tenth of the reporters spread across 400. LDP rewards concentration, so the domain must be chosen to keep counts per cell high — which is the same argument for a coarse grid, arriving from a different direction.

Second, the epsilon that makes the estimator usable is often larger than the epsilon a privacy review would accept for a central release, and that is not a contradiction. In the local model the guarantee protects each report individually against a server that is trusted with nothing, so an $\varepsilon$ of 2 or 3 per distinct value is a materially stronger operational posture than an $\varepsilon$ of 0.5 in a central model where the server holds raw coordinates. Comparing the two numbers directly is the most common analytical error in this area; they are guarantees against different adversaries.

The third input is engineering cost, and it is not small. Local differential privacy moves privacy machinery into the client: a randomiser that must be audited, a memo store that must be persisted and encrypted, a cap that must be enforced, an epoch that must rotate deterministically, and a parameter version that must be transmitted with every report. All of that ships on a release cycle measured in weeks, on devices you cannot patch synchronously, and a bug in any of it is invisible from the server. A central or federated design with secure aggregation keeps the machinery on infrastructure you control and can fix in an afternoon.

The practical rule that falls out: adopt LDP when there is genuinely no party permitted to hold raw coordinates and the per-cell reporter count is in the tens of thousands and the client is one you build, ship and can attest. When any of the three fails, the shuffle model — clients randomise lightly, a trusted shuffler strips identifiers and batches, and the server adds central noise — gives a comparable end-to-end guarantee at a fraction of the utility cost, and it is where most production deployments have converged.

Threat model considerations

• The client build is the trust boundary. An adversary who can modify the client can disable the randomiser, and no server-side check can distinguish a truthful report from a randomised one that happened to keep its true value. Attest the client where the platform allows it, and treat LDP as providing no guarantee against a compromised device — only against a curious server.
• Longitudinal linkage across epochs. A device reporting the same home cell across many epochs gives the server repeated noisy observations of one value, and averaging them recovers the truth. Memoisation is what prevents this, and a deployment without it degrades to no privacy within days regardless of the per-report $\varepsilon$.
• Small domains leak more than they look like they do. With a domain of ten districts, a report under randomised response at $\varepsilon = 2$ is correct roughly 45% of the time. That is a strong posterior for an adversary with any prior at all — for example, one who already knows the device’s home district.
• The report schedule is metadata. Even a perfectly randomised payload arrives at a time, from an IP address, with a size. Batch reports through a shuffler or a trusted relay if the schedule itself is sensitive; LDP protects the payload, not the envelope.
• De-biased estimates can be negative. They will be, for genuinely empty cells, and clamping them to zero reintroduces exactly the upward bias in sparse areas that the estimator removed. Publish the negative estimate with its error bar, or suppress the cell — do not clamp silently.

Validation and compliance checklist

1. The estimator is unbiased on synthetic data. Feed known frequencies through the randomiser and confirm the recovered counts are within the predicted standard error. Pass criterion: mean estimate within $2\sigma$ of truth over 100 trials.
2. Randomised output is memoised. Reporting the same cell twice produces byte-identical output. Pass criterion: an automated test asserts equality across two calls.
3. The client RNG is cryptographic. Pass criterion: a code check rejects random and Math.random in the randomiser path.
4. The per-epoch distinct-value cap is enforced client-side. Pass criterion: a device that hits the cap emits nothing, and the test asserts no report is sent.
5. Population sizing is documented per cell. Every published cell records the number of contributing clients, and cells below the sizing floor are suppressed. Pass criterion: no published cell has fewer contributors than the floor.
6. The domain is versioned. Changing the cell domain invalidates memoised outputs and changes the estimator. Pass criterion: the domain version is transmitted with every report and mismatched versions are aggregated separately.

Failure modes and remediation

• Every cell looks equally busy. The de-biasing step is missing or the parameters used to invert do not match the parameters the client used. Log the client’s parameter version with each report and assert it server-side.
• Estimates are wildly noisy despite a large population. The domain is too large for the chosen mechanism. Move from unary encoding to local hashing, or — better — coarsen the grid, which reduces both $d$ and the variance.
• Sparse cells oscillate between large positive and large negative estimates. Expected: the estimator’s standard error exceeds the true count. Suppress cells whose estimate is within the error bar of zero rather than publishing noise as data.
• Privacy loss accumulates faster than planned. Devices are re-randomising rather than memoising, or the distinct-value cap is server-enforced and therefore not enforced at all. Both are client bugs; neither is visible from server metrics, so they need client-side tests.
• A regulator asks who holds personal data. With correct LDP, nobody does — but the claim depends on the client build, the memoisation and the cap. Keep the client randomiser small, audited, and separately versioned so that claim can be evidenced.

Frequently Asked Questions

Related

• Comparing Central vs Local Differential Privacy for GIS — the quantitative version of the choice.
• Randomized Response for Grid-Cell Reporting — the simplest randomiser, in full.
• Frequency Estimation of Visited Cells with LDP — the server-side estimator and its error bars.
• On-Device Budget Management for LDP Clients — memoisation, caps, and the client ledger.

Up one level: Differential Privacy for Geospatial Data.