Introduction

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.

Try It

Pick a value below and click Encode. The demo hashes it into a Bloom filter, flips bits with probability p=0.5p = 0.5 (PRR), then flips again with probability q=0.75q = 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.

<!-- RAPPOR demo: pick a value, see it encoded into a Bloom filter, then randomized twice (PRR + IRR) -->
<div class="controls">
  <label>Pick a value to encode:</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">Bloom</span>
  <div id="bloomBits" class="bits"></div>
</div>
<div class="bloom-row">
  <span class="bloom-label">PRR</span>
  <div id="prrBits" class="bits"></div>
</div>
<div class="bloom-row">
  <span class="bloom-label">Report</span>
  <div id="irrBits" class="bits"></div>
</div>
<div class="report-note" id="reportNote"></div>
<div class="action-row">
  <button type="button" id="encodeBtn">Encode</button>
  <button type="button" id="aggregateBtn">Aggregate 500 users</button>
  <button type="button" id="resetBtn" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// RAPPOR (Erlingsson et al., 2014): local differential privacy via two-stage Bloom filter randomization.
// Stage 1 PRR: each bit flipped independently with prob P_PRR (stored on device). Stage 2 IRR: re-randomized per report.

const VALUES = ['A', 'B', 'C', 'D'];
const K = 16; // number of Bloom filter bits
const P_PRR = 0.5; // probability of randomizing each bit in the PRR stage
const Q_IRR = 0.75; // probability a 1-bit in PRR stays 1 in the IRR stage

// Hash a value string into K Bloom filter bit positions (3 positions per value).
function hashBits(val) {
  const bits = new Array(K).fill(0);
  let h = 0;
  for (let i = 0; i < val.length; i++) h = (h * 31 + val.charCodeAt(i)) >>> 0;
  for (let s = 0; s < 3; s++) {
    const idx = (h ^ (h >>> (s * 7))) % K;
    bits[((idx % K) + K) % K] = 1;
    h = (h * 1664525 + 1013904223) >>> 0;
  }
  return bits;
}

// Apply Permanent Randomized Response: flip each bit with probability P_PRR.
function applyPRR(bloom) {
  return bloom.map(b => Math.random() < P_PRR ? (Math.random() < 0.5 ? 1 : 0) : b);
}

// Apply Instantaneous Randomized Response: re-randomize each bit per report.
function applyIRR(prr) {
  return prr.map(b => b === 1 ? (Math.random() < Q_IRR ? 1 : 0) : (Math.random() < (1 - Q_IRR) / 2 ? 1 : 0));
}

function renderBits(id, bits, highlight) {
  const el = document.getElementById(id);
  el.innerHTML = '';
  bits.forEach((b, i) => {
    const d = document.createElement('div');
    d.className = 'bit ' + (b ? 'on' : 'off') + (highlight && highlight[i] ? ' flipped' : '');
    d.textContent = b;
    el.appendChild(d);
  });
}

let currentVal = 'A';
let currentBloom = hashBits('A');
let currentPRR = currentBloom.slice();
let currentIRR = currentBloom.slice();
let chartData = null;

// Handle value button selection.
document.querySelectorAll('.val-btn').forEach(btn => {
  btn.addEventListener('click', () => {
    document.querySelectorAll('.val-btn').forEach(b => b.classList.remove('active'));
    btn.classList.add('active');
    currentVal = btn.dataset.val;
    resetDisplay();
  });
});

function resetDisplay() {
  currentBloom = hashBits(currentVal);
  currentPRR = currentBloom.slice();
  currentIRR = currentBloom.slice();
  renderBits('bloomBits', currentBloom, null);
  renderBits('prrBits', currentPRR, null);
  renderBits('irrBits', currentIRR, null);
  document.getElementById('reportNote').textContent = '';
  document.getElementById('status').textContent = '';
  document.getElementById('chartTitle').textContent = '';
  document.getElementById('chart').innerHTML = '';
}

function encode() {
  currentBloom = hashBits(currentVal);
  currentPRR = applyPRR(currentBloom);
  currentIRR = applyIRR(currentPRR);
  const prrFlipped = currentBloom.map((b, i) => b !== currentPRR[i] ? 1 : 0);
  const irrFlipped = currentPRR.map((b, i) => b !== currentIRR[i] ? 1 : 0);
  renderBits('bloomBits', currentBloom, null);
  renderBits('prrBits', currentPRR, prrFlipped);
  renderBits('irrBits', currentIRR, irrFlipped);
  const totalFlipped = irrFlipped.reduce((a, b) => a + b, 0);
  document.getElementById('reportNote').textContent =
    i18nFmt('Value %val% → %flipped% bit(s) flipped by noise. The server sees only the Report row.', { val: currentVal, flipped: totalFlipped });
  document.getElementById('status').textContent = '';
}

// Simulate N users, each choosing a value from trueDist, encoding it with RAPPOR, and sending the IRR.
function aggregate() {
  const N = 500;
  // Fixed true distribution for the simulation.
  const trueDist = { A: 0.4, B: 0.3, C: 0.2, D: 0.1 };
  // Accumulate sum of IRR bit vectors across all simulated users.
  const sumIRR = new Array(K).fill(0);
  const trueCounts = {};
  VALUES.forEach(v => { trueCounts[v] = 0; });

  for (let i = 0; i < N; i++) {
    const r = Math.random();
    let acc = 0, chosen = 'A';
    for (const v of VALUES) { acc += trueDist[v]; if (r < acc) { chosen = v; break; } }
    trueCounts[chosen]++;
    const b = hashBits(chosen);
    const prr = applyPRR(b);
    const irr = applyIRR(prr);
    irr.forEach((bit, j) => { sumIRR[j] += bit; });
  }

  // Decode: for each value, sum the expected Bloom bit contributions from the noisy aggregate.
  // Decode: for each value, count how many of its Bloom bits dominate in sumIRR.
  const decoded = {};
  VALUES.forEach(v => {
    const b = hashBits(v);
    let score = 0;
    b.forEach((bit, j) => {
      if (bit === 1) score += (sumIRR[j] / N) - 0.5;
    });
    decoded[v] = Math.max(0, score);
  });

  // Normalize decoded scores to a probability distribution.
  const total = Object.values(decoded).reduce((a, b) => a + b, 0) || 1;
  VALUES.forEach(v => { decoded[v] = decoded[v] / total; });

  chartData = { trueDist, decoded, trueCounts, N };
  renderChart();
  document.getElementById('status').textContent =
    i18nFmt('Aggregated %n% users — decoded histogram shown above.', { n: N });
}

function renderChart() {
  if (!chartData) return;
  const { trueDist, decoded, N } = chartData;
  document.getElementById('chartTitle').textContent = 'True distribution (blue) vs. decoded estimate (red)';
  const chart = document.getElementById('chart');
  chart.innerHTML = '';

  // Build the legend element once before reinserting the chart.
  const legend = document.createElement('div');
  legend.className = 'legend';
  legend.innerHTML =
    '<span><span class="legend-dot" style="background:#1d3557"></span>true</span>' +
    '<span><span class="legend-dot" style="background:#e63946"></span>Decoded</span>';
  chart.parentNode.insertBefore(legend, chart);

  const maxH = 68;
  VALUES.forEach(v => {
    const trueH = Math.round(trueDist[v] * maxH);
    const decH = Math.round(decoded[v] * maxH);
    const group = document.createElement('div');
    group.className = 'bar-group';
    group.innerHTML =
      `<div class="bar-wrap">` +
      `<div class="bar true-bar" style="height:${trueH}px" title="${Math.round(trueDist[v]*100)}%"></div>` +
      `<div class="bar decoded-bar" style="height:${decH}px" title="${Math.round(decoded[v]*100)}%"></div>` +
      `</div><div class="bar-label">${v}</div>`;
    chart.appendChild(group);
  });
}

document.getElementById('encodeBtn').addEventListener('click', encode);
document.getElementById('aggregateBtn').addEventListener('click', aggregate);
document.getElementById('resetBtn').addEventListener('click', () => { resetDisplay(); chartData = null; document.querySelector('.legend') && document.querySelector('.legend').remove(); });

resetDisplay();
renderBits('bloomBits', currentBloom, null);
renderBits('prrBits', currentPRR, null);
renderBits('irrBits', currentIRR, null);
Result
Console

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.

The Real Complexity

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

Pr⁡[M(v)∈S]≤eε⋅Pr⁡[M(v′)∈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 vv from v′v' by more than a factor of eε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 pp. 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 qq if the PRR bit is 1, or with probability 12(1−q)\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(k2/ε2)O(k^2 / \varepsilon^2) where kk is the number of bits in the Bloom filter.

The cost of strong privacy (ε→0\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.

Where It Matters

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.

Conclusion

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 nn (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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rappor-local-dp/Content licensed under CC BY-NC 4.0.