RAPPOR (Local DP)

Every time Chrome notices a suspicious homepage setting, Google wants to know how common it is. But asking users to simply report their setting would reveal their configuration to a central server. RAPPOR — Randomized Aggregatable Privacy-Preserving Ordinal Response — solves this by adding carefully calibrated noise on the device itself, before anything is sent.

The idea descends from Warner's randomized response (1965): if you want people to admit to a stigmatized behavior, tell them to flip a coin first — heads, tell the truth; tails, say yes regardless. The researcher can later correct for the coin, recovering accurate population statistics, but no individual answer can be pinned down.

RAPPOR extends this to strings. A value such as a browser setting is first hashed into a Bloom filter — a fixed-length bit vector. Then each bit is independently randomized, producing a Permanent Randomized Response (PRR) stored locally. Each time a report is sent, the PRR undergoes a second round of randomization — the Instantaneous Randomized Response (IRR). Google receives only these scrambled bits; it cannot decode any individual report. But when millions of reports arrive, the signal survives the noise: a careful statistical decode recovers which values are common in the population.

This is local differential privacy: the privacy guarantee lives at the source, not in a trusted server. Even if Google's servers were breached, each record would reveal nothing — because it was already randomized before leaving the device. Compare this with differential privacy variants that require trusting a central curator.

Pick a value below and click Encode. The demo hashes it into a Bloom filter, flips bits with probability $p = 0.5$ (PRR), then flips again with probability $q = 0.75$ to produce the final report. Run Aggregate to simulate 500 users choosing values at random, send their noisy reports, and decode the population histogram.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{label_pick_value}}</label>
  <div class="value-btns" id="valueBtns">
    <button type="button" class="val-btn active" data-val="A">A</button>
    <button type="button" class="val-btn" data-val="B">B</button>
    <button type="button" class="val-btn" data-val="C">C</button>
    <button type="button" class="val-btn" data-val="D">D</button>
  </div>
</div>
<div class="bloom-row">
  <span class="bloom-label">{{label_bloom}}</span>
  <div id="bloomBits" class="bits"></div>
</div>
<div class="bloom-row">
  <span class="bloom-label">{{label_prr}}</span>
  <div id="prrBits" class="bits"></div>
</div>
<div class="bloom-row">
  <span class="bloom-label">{{label_irr}}</span>
  <div id="irrBits" class="bits"></div>
</div>
<div class="report-note" id="reportNote"></div>
<div class="action-row">
  <button type="button" id="encodeBtn">{{btn_encode}}</button>
  <button type="button" id="aggregateBtn">{{btn_aggregate}}</button>
  <button type="button" id="resetBtn" class="ghost">{{btn_reset}}</button>
</div>
<div class="chart-title" id="chartTitle"></div>
<div id="chart" class="chart"></div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { margin-bottom: .7rem; }
label { font-weight: 600; display: block; margin-bottom: .35rem; }
.value-btns { display: flex; gap: .4rem; flex-wrap: wrap; }
.val-btn { padding: .35rem .8rem; border: 1.5px solid #1d3557; border-radius: 6px;
           background: #fff; color: #1d3557; cursor: pointer; font-weight: 600; font-size: .9rem; }
.val-btn.active { background: #1d3557; color: #fff; }
.bloom-row { display: flex; align-items: center; gap: .5rem; margin: .3rem 0; }
.bloom-label { width: 46px; font-size: .78rem; color: #555; text-align: right; flex-shrink: 0; }
.bits { display: flex; gap: 3px; flex-wrap: wrap; }
.bit { width: 20px; height: 20px; border-radius: 4px; border: 1px solid #ccc;
       display: flex; align-items: center; justify-content: center;
       font-size: .7rem; font-weight: 700; }
.bit.on { background: #1d3557; color: #fff; border-color: #1d3557; }
.bit.off { background: #e8eef3; color: #aaa; }
.bit.flipped { border-color: #e63946; }
.report-note { font-size: .82rem; color: #555; margin: .4rem 0 .6rem; min-height: 1.2em; }
.action-row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.chart-title { font-weight: 600; font-size: .85rem; margin-bottom: .3rem; color: #333; min-height: 1.1em; }
.chart { display: flex; gap: 8px; align-items: flex-end; height: 90px; margin-bottom: .4rem; }
.bar-group { display: flex; flex-direction: column; align-items: center; gap: 2px; min-width: 38px; }
.bar-wrap { display: flex; gap: 2px; align-items: flex-end; height: 70px; }
.bar { width: 14px; border-radius: 3px 3px 0 0; transition: height .3s; }
.bar.true-bar { background: #1d3557; }
.bar.decoded-bar { background: #e63946; }
.bar-label { font-size: .72rem; color: #555; }
.legend { display: flex; gap: .8rem; font-size: .75rem; margin-bottom: .3rem; }
.legend-dot { width: 10px; height: 10px; border-radius: 2px; display: inline-block; margin-right: 3px; }
.status { font-size: .85rem; font-weight: 600; min-height: 1.2em; color: #0a7d33; }

// Code not found

Notice: a single report looks like random noise. But once enough reports accumulate, the decoded histogram matches the true distribution — the signal survives, even though no individual value was ever sent in the clear.

RAPPOR's guarantee is expressed in the language of $\varepsilon$-local differential privacy. A randomizer $\mathcal{M}$ satisfies $\varepsilon$-LDP if for any two inputs $v$ and $v'$ and any output set $S$:

$$\Pr[\mathcal{M}(v) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{M}(v') \in S]$$

This means an adversary seeing the output cannot distinguish $v$ from $v'$ by more than a factor of $e^{\varepsilon}$. Smaller $\varepsilon$ means stronger privacy; larger $\varepsilon$ means more accuracy.

The two-stage design gives RAPPOR two important properties:

• The PRR (permanent randomized response) randomizes each bit with probability $p$. This provides the core LDP guarantee. Because the PRR is stored locally and reused, it also prevents a server from linking multiple reports from the same user to the same true value.
• The IRR (instantaneous randomized response) adds a second layer of noise. Each bit of the PRR is reported as 1 with probability $q$ if the PRR bit is 1, or with probability $\frac{1}{2}(1-q)$ otherwise. This further obscures any individual report.

Decoding requires inverting the noise channel. The server observes a sum of noisy bit vectors; it must estimate which underlying values are frequent. This is a linear inverse problem solved with LASSO regression or similar sparse recovery techniques — computationally tractable, but requiring enough reports for the signal to dominate the noise. The minimum sample size grows as $O(k^2 / \varepsilon^2)$ where $k$ is the number of bits in the Bloom filter.

The cost of strong privacy ($\varepsilon \to 0$) is accuracy: the noise dominates the signal and you need exponentially more users. This fundamental tension is not a flaw in RAPPOR — it is a theorem. Local differential privacy provably requires more data than central DP for the same accuracy, because the curator cannot subtract out the noise globally.

RAPPOR was deployed by Google in Chrome to learn which unwanted software was silently changing users' homepage or default search engine — a real harm that required real statistics. The same principle has spread across the industry:

• Apple's local DP (2016): Apple uses local differential privacy in iOS and macOS to collect statistics about emoji usage, word frequencies, and energy consumption — announced at WWDC and verified independently. The same mechanism now underpins several on-device analytics features.
• Microsoft's Windows telemetry: frequency estimation of app crashes and feature usage uses similar local randomization to limit server-side exposure.
• Browser fingerprinting defenses: randomizing reported browser attributes provides plausible deniability against trackers, borrowing the same coin-flip idea at the transport level.
• Federated learning: RAPPOR-style noise is one building block in federated learning pipelines, where gradients or model updates must be privatized before aggregation.

The broader lesson is that local DP is the right tool when you cannot trust the data collector — either because it might be breached, subpoenaed, or simply untrustworthy. The privacy guarantee is mathematical and device-side, independent of server policy.

For a complementary angle, see PAC learning — the statistical framework that asks how many samples suffice to learn a concept. Local DP imposes a fundamental tax on that sample count.

RAPPOR turns a philosophical question — can you learn from a population without knowing any individual? — into an engineering product. The answer is yes, but only through deliberate noise. The two randomization stages give users a mathematical privacy guarantee that does not depend on trusting Google's servers, its employees, or its legal obligations in any particular jurisdiction.

The price is efficiency: local DP needs more data than central DP to learn the same thing. That is not a bug to be engineered away — it is a lower bound, proved in information theory. Every deployment of RAPPOR, Apple's local DP, or any equivalent system is a live negotiation between two quantities: $\varepsilon$ (how much privacy you give up) and $n$ (how many users you need).

The next time your phone silently reports an aggregate statistic, there is a good chance a coin is being flipped somewhere on your device — not to deceive, but to protect.