Tuning RAPPOR-Style Encoding for Grid-Cell Reports

Under local differential privacy the client perturbs its own report, so the parameters that matter are the Bloom width $k$, the hash count $h$ and the flip probability $f$. Only two of the three are free: $f$ is fixed by your epsilon, and the pair $(k, h)$ then decides whether the aggregate has enough signal to recover a cell count at all.

Core Calculation # permalink

A client observing grid cell $c$ writes it into a $k$-bit Bloom filter using $h$ hashes, then flips each bit independently:

The privacy cost of one report is bounded by the ratio of the most and least likely outputs across the $h$ bits a single cell touches:

Solving for the flip probability given a target epsilon:

The estimator inverts the flipping. With $N$ reports and $Y_i$ the count of ones in bit position $i$:

and its standard error, which is the number that decides usability:

Note what $h$ does: it appears in the denominator of the exponent, so raising $h$ lowers the required flip probability for a fixed epsilon, but multiplies the number of bits each cell sets and therefore the collision rate. $h = 2$ is the near-universal choice, and it is not an accident.

Worked numeric example # permalink

A city grid of 4 096 cells at 250 m, $\varepsilon = 2$ per report, $h = 2$:

With $k = 512$ and $N = 500{,}000$ clients:

A cell holding 1 % of the population — 5 000 reports — is roughly 3.6 standard errors above zero, so it is detectable. A cell holding 0.2 % (1 000 reports) is below the noise entirely. The practical threshold is that a cell must hold about 1 % of your reporting population to survive $\varepsilon = 2$ local DP, and that fact drives the grid resolution far more than any cartographic consideration.

Python Implementation # permalink

from __future__ import annotations

import hashlib
import math

import numpy as np


def flip_probability(epsilon: float, h: int = 2) -> float:
    """Flip probability giving `epsilon`-LDP for a report touching `h` bits.

    Raising h lowers f for a fixed epsilon but multiplies the collision rate,
    which is why h = 2 is the standard choice rather than a tuning knob.
    """
    return 2.0 / (1.0 + math.exp(epsilon / (2.0 * h)))


def bloom_bits(cell_id: str, k: int, h: int = 2) -> list[int]:
    """Deterministic bit positions for a grid cell in a k-bit filter."""
    digest = hashlib.sha256(cell_id.encode()).digest()
    return [int.from_bytes(digest[i * 4:(i + 1) * 4], "big") % k for i in range(h)]


def client_report(cell_id: str, k: int, epsilon: float, h: int = 2,
                  rng: np.random.Generator | None = None) -> np.ndarray:
    """Encode and perturb one client's cell — runs on the device, not the server.

    The perturbation happens before the report leaves the handset, so the
    collector never holds a true cell for any individual. That is the whole
    point of the local model and the reason the variance is so large.
    """
    rng = rng or np.random.default_rng()
    bits = np.zeros(k, dtype=np.int8)
    bits[bloom_bits(cell_id, k, h)] = 1

    f = flip_probability(epsilon, h)
    coin = rng.random(k)
    out = bits.copy()
    out[coin < f / 2] = 1
    out[(coin >= f / 2) & (coin < f)] = 0
    return out


def estimate_counts(reports: np.ndarray, cells: list[str], k: int,
                    epsilon: float, h: int = 2) -> dict[str, dict[str, float]]:
    """Debias the bit sums and attribute them back to candidate cells."""
    f = flip_probability(epsilon, h)
    n = reports.shape[0]

    y = reports.sum(axis=0).astype(float)
    t_hat = (y - (f / 2) * n) / (1.0 - f)
    se = (math.sqrt(n * f * (2 - f)) / 2.0) / (1.0 - f)

    out = {}
    for cell in cells:
        positions = bloom_bits(cell, k, h)
        # The min over the cell's own bits is the standard Bloom-style estimate:
        # a collision can only inflate a position, never deflate it.
        est = float(np.min(t_hat[positions]))
        out[cell] = {
            "estimate": est,
            "std_error": se,
            "significant": est > 3.0 * se,
        }
    return out

Verification # permalink

Three checks, run before the encoder ships to devices.

The epsilon is what you claim. Recompute it from the flip probability actually used, not from the one in the design doc:

def realised_epsilon(f: float, h: int = 2) -> float:
    return 2 * h * math.log((1 - f / 2) / (f / 2))

assert abs(realised_epsilon(flip_probability(2.0)) - 2.0) < 1e-9

The estimator is unbiased. Simulate a known distribution and confirm recovery within the stated error:

def check_recovery(true_counts: dict[str, int], k: int, epsilon: float,
                   h: int = 2, seed: int = 0) -> dict:
    rng = np.random.default_rng(seed)
    reports = np.vstack([
        client_report(cell, k, epsilon, h, rng)
        for cell, n in true_counts.items() for _ in range(n)
    ])
    est = estimate_counts(reports, list(true_counts), k, epsilon, h)
    return {
        cell: {
            "true": n,
            "estimated": round(est[cell]["estimate"]),
            "within_3se": abs(est[cell]["estimate"] - n) < 3 * est[cell]["std_error"],
        }
        for cell, n in true_counts.items()
    }

The collision floor is below the detection floor. With $\lvert C \rvert$ candidate cells in a $k$-bit filter and $h$ hashes, the chance two cells share both positions is roughly $(h/k)^h$. For $k = 512$, $h = 2$, $\lvert C \rvert = 4096$, that is $1.5 \times 10^{-5}$ per pair, which over $\binom{4096}{2}$ pairs gives about 128 fully-colliding pairs. Those pairs are indistinguishable in the aggregate — a fact worth stating in the release notes, because an analyst who sees two neighbouring cells with identical counts will otherwise assume a bug.

Edge Cases & Adjustments # permalink

• Repeated reports from one device. Epsilon composes over reports. A client sending its cell hourly spends $24\varepsilon$ per day unless you add a memoised permanent randomisation layer — the original RAPPOR design’s first stage — which fixes one perturbed value per cell per client and reports a fresh instantaneous perturbation of that. Without memoisation, averaging over a day recovers the true cell exactly.
• Sparse grids. Most city grids are mostly empty. The estimator returns noise for empty cells, and negatives are common; clamp at zero for display but keep the signed estimate for any downstream arithmetic, because clamping introduces an upward bias in every sum.
• Alphabet drift. Adding cells to the grid changes the collision structure. Recompute the collision table and re-verify the detection floor; do not assume the previous release’s numbers hold.
• Small panels. Below roughly $N = 50{,}000$ the local model is usually the wrong tool. If you have a trusted aggregator, central DP delivers the same epsilon at a fraction of the variance.
• The min estimator’s bias. Taking the minimum across a cell’s bits is conservative but slightly downward-biased when the estimates are noisy. For a formal analysis, fit a regression over the full candidate set instead — at the cost of needing the candidate set in advance.

FAQ # permalink

Why is $h = 2$ almost always right?

Because $h$ appears twice with opposite signs: it divides epsilon in the flip-probability formula (good) and multiplies the collision rate (bad). At $h = 2$ the collision term is already the binding constraint for realistic grid sizes, so raising it trades a real loss for a marginal gain.

Can I use one epsilon for the whole day instead of per report?

Only with memoisation. Without a permanent randomised response held per client, each report is an independent draw and they compose linearly, so a day of hourly reports at $\varepsilon = 2$ is $\varepsilon = 48$ — no protection at all.

What grid resolution should I pick?

The one where your smallest cell of interest holds about 1 % of the reporting population at $\varepsilon = 2$. Work backwards from the detection floor rather than forwards from cartography.

Do negative estimates mean the code is broken?

No. The debiased estimator is unbiased around the true count, so a cell with a true count near zero produces negatives about half the time. Their absence would be the bug.

Related # permalink

• Local Differential Privacy for Mobile Clients — where the local model belongs and where it does not
• Differential Privacy for Location Data — the central-model comparison
• Privacy Budget Allocation for Spatial Queries — how repeated reports compose
• Grid Aggregation & Spatial Binning Strategies — choosing the cell alphabet
• Setting Minimum Count Thresholds for Published Map Cells — the suppression analogue

← Back to Local Differential Privacy for Mobile Clients