RAPPOR 2014 — 用随机应答在浏览器端实现本地差分隐私

是什么

RAPPOR（Randomized Aggregatable Privacy-Preserving Ordinal Response）是 Google 2014 年在 CCS 会议上发表的一套在浏览器端给用户数据加噪声，再让服务端从大量噪声中恢复群体统计规律的系统。

日常类比：想象一个大型匿名问卷——每个人收到卷子后，先掷一枚硬币决定是写真实答案还是写随机答案。单看任何一份卷子，你分不清这人到底是真答还是掷了币；但如果收到 100 万份，掷币的误差会互相抵消，真实的群体分布就浮出水面了。RAPPOR 把这套”随机应答”的做法搬到了 Chrome 浏览器里。

技术定义：RAPPOR 是一种满足 epsilon-本地差分隐私（LDP）的客户端数据收集协议——先把原始值编成布隆过滤器，再经永久/瞬时两轮随机化，服务端从海量噪声报告里用统计方法（如 LASSO）还原群体频率。细节见「核心要点」。

为什么重要

不理解 RAPPOR，下面这些问题就答不上来：

• 为什么 Chrome 能统计”用户的默认首页被哪些恶意软件劫持了”却不知道任何一个具体用户的首页——RAPPOR 在数据离开浏览器之前就加了不可逆噪声
• 为什么 Apple 的差分隐私系统和 RAPPOR 长得很像——Apple 2017 年公开的方案继承了 RAPPOR 的”客户端随机化 + 服务端解码”架构
• 为什么说”收集端加密”不够而要”收集端加噪”——加密只是不让第三方看到，服务端解密后数据还是明文；加噪让服务端也只能看到统计量
• 为什么隐私预算 epsilon 能在 RAPPOR 里拆成两层（永久 + 瞬时）——两轮翻转分别控制纵向关联和横向关联的隐私损失
• 为什么本地差分隐私系统总是需要几百万用户才出结果——Duchi 2013 证明了 LDP 精度极限天然比中心化差得多，RAPPOR 是在这个理论框架下做工程权衡

前置知识

读这篇论文需要先理解三个概念：

1. 差分隐私的 epsilon 含义：epsilon 越小隐私保护越强，但统计精度越差。建议先读 dwork-dp-2006 掌握基本定义。
2. 布隆过滤器（Bloom Filter）：一种用 k 个哈希函数把元素映射到 m 位向量的概率数据结构，支持快速判断”可能存在/一定不存在”。RAPPOR 把它当编码层。
3. 随机应答（Randomized Response）：1965 年 Warner 提出的问卷技术——受访者掷币决定是说真话还是说反话。这是 RAPPOR 隐私机制的思想原型。

如果这三个概念已经熟悉，可以直接跳到”核心要点”。

核心要点

RAPPOR 的设计可以拆成三步理解：

第一步：编码——把任意值变成位向量

客户端把原始字符串（比如 “www.evil.com”）通过 k 个哈希函数映射到一个长度为 m 的布隆过滤器（Bloom filter）。这一步把无限种可能的字符串压缩到了固定长度的 0/1 向量。类比：把一本书的内容压成 128 位指纹。

第二步：永久随机响应（Permanent Randomized Response, PRR）

对布隆过滤器每一位独立掷币：以概率 1-f 原样保留；以概率 f/2 强制写成 1；以概率 f/2 强制写成 0。得到”永久模板”B’ 后就固定下来——同一用户对同一值以后都复用这份 B’，避免多次上报被取平均还原真值。

第三步：瞬时随机响应（Instantaneous Randomized Response, IRR）

每次实际上报时，再对 B’ 的每一位重新掷币：B’=1 时以概率 q 报 1；B’=0 时以概率 p 报 1。目的：即使攻击者逼近了 B’，单次报告仍带噪声。

服务端收到百万份噪声位向量后，用统计解码（如 LASSO）恢复高频字符串。

隐私保证（论文分两层，不要混成一个数）：永久层 ε_∞ = 2h·ln((1-f/2)/(f/2))（h 为哈希个数）；瞬时层另有 ε₁，由 f、p、q 决定。f 管纵向隐私，p/q 管单次报告隐私。

实践案例

案例 1：单客户端三步（跟读）

假设要上报字符串 "evil.com"，参数取论文常用组：布隆长度 m=128、哈希数 h=2、f=0.5、q=0.75、p=0.5。

1) 编码：用 2 个哈希把 "evil.com" 映到 128 位向量 B（通常只有 2 个 1）
2) PRR：对每位 —— 50% 保留原值，25% 强制 1，25% 强制 0 → 得到固定模板 B'
3) IRR：每次上报对 B' 再掷币 —— 位为 1 时 75% 报 1；位为 0 时 50% 报 1 → 发出报告 S

此配置下永久层 ε_∞ = 2·2·ln(3) = 4ln(3) ≈ 4.39；瞬时层论文给出约 ε₁ ≈ 1.07。若误把 h=1 的 2ln(3)≈2.2 当成「总 epsilon」，就和推荐参数对不上。

案例 2：Chrome 里实际收什么

Google 用 RAPPOR 收三类遥测：默认首页 URL（抓大规模劫持）、默认搜索引擎、进程里出现的可执行路径。数百万用户本地加噪后上报，服务端只做噪声聚合。论文在约百万用户规模下能恢复高频首页域名；对比实验表明：不做布隆编码、只靠单轮随机应答，面对无限字符串域几乎无法解码。

案例 3：Cohort 分治降碰撞

为降低布隆碰撞，用户被随机分进 64/128 个 cohort，每组用不同哈希种子；服务端分组解码再合并。代价是每组样本量变小——精度与碰撞率的权衡，后来也被 Apple 方案借鉴。

踩过的坑

1. 布隆过滤器碰撞导致误报：两个不同字符串哈希到同样的位模式，服务端无法区分。解决方法是用多组哈希（cohort），把用户随机分到不同组用不同哈希种子，降低全局碰撞率。但这也意味着每组人数变少、统计精度下降——这是一个根本性的 trade-off。

2. 永久模板仍可能被纵向逼近：同一用户反复上报同一值时，多次 IRR 均值会逼近 B’。PRR 让 B’ 本身已是噪声；f 太小则纵向保护不够。论文常用 f=0.5；再降要先按 ε_∞=2h·ln((1-f/2)/(f/2)) 算清预算。

3. LASSO 解码对低频项不灵敏：RAPPOR 能准确恢复高频项（出现率 > 0.1%），但对长尾低频项几乎无能为力。这不是 bug 而是 LDP 的本质限制——Duchi 2013 证明了在给定 epsilon 和用户数下的精度下界。想检测出只被 100 人使用的恶意软件？需要把用户池扩大到千万级。

4. 参数选择影响隐私-精度 trade-off 的方式非线性：直觉上觉得”f 越大噪声越大隐私越好”，但 f 超过某个阈值后精度急剧崩溃而隐私提升微乎其微。论文建议通过理论公式而非直觉调参。

适用 vs 不适用场景

适用：

• 大规模客户端遥测——用户量百万级以上，想统计群体分布但不想碰个人数据
• 字符串型数据的频率估计——“最常被设为首页的域名 top-100”
• 不信任服务端的场景——即使数据库被拖库，攻击者看到的也只是噪声

不适用：

• 小用户群体（< 10 万人）——LDP 噪声太大，恢复不出有意义的信号
• 需要精确个体级数据——RAPPOR 只能恢复群体频率，无法知道”张三到底用了什么”
• 数值型数据的均值/中位数估计——RAPPOR 针对离散字符串优化，数值型场景用 Duchi 机制更合适
• 低延迟实时分析——LASSO 解码需要积累足够样本后批处理
• 需要跨多个属性做联合分析——RAPPOR 每次只收集一个属性的频率，多属性关联分析需要更复杂的协议

判断公式：如果你的场景满足”用户量 > 百万 + 只需群体频率 + 数据是离散字符串”这三个条件，RAPPOR 就值得考虑。

历史小故事（可跳过）

2014 年之前，差分隐私几乎只活在学术论文里。工业界的态度是”理论很美但没法落地”。

Google 的 Ulfar Erlingsson 团队做了一件关键的事：不追求最优理论精度，而是把一种 1960 年代就有的老技术——华纳（Warner, 1965）随机应答——和布隆过滤器拼在一起，做出了一个真正能在十亿用户的浏览器里跑起来的系统。

论文发表后一年内，Apple 也公开了自己的本地差分隐私方案，微软的 BLENDER 系统紧随其后。RAPPOR 开启了”工业界大规模部署差分隐私”的时代。

值得一提的是，RAPPOR 的名字来自法语 rapport（报告），也暗合了随机应答（Randomized Response）的缩写。

一个有意思的细节：Erlingsson 原本在微软研究院做系统安全（他写过 CFI 控制流完整性的奠基论文），加入 Google 后转向隐私方向。他的方法论是”系统人做隐私”——不追求理论最优，而是追求在十亿级设备上能实际部署的方案。

学到什么

1. 隐私不是加密的同义词——加密保护传输，差分隐私保护统计推断。两者解决不同层面的问题，RAPPOR 需要的是后者
2. 两轮随机化各有分工——永久层防纵向关联（同一用户多次上报），瞬时层防横向推断（单次上报的位值）。分层设计是系统工程的常见模式
3. 布隆过滤器是把无限域压缩到有限位的通用武器——在密码学、网络、数据库、隐私系统中反复出现
4. 理论下界决定了工程上限——Duchi 2013 的 minimax bound 告诉你”再怎么优化算法也超不过这条线”，工程师该做的是逼近这条线而不是幻想突破它
5. 从 1960 年代的问卷技术到 2014 年的浏览器——好的老想法加上新的组合方式就是创新
6. Cohort 分治是应对哈希碰撞的标准手段——把用户分组、每组用不同种子，是在精度和碰撞率之间找平衡的通用模式

延伸阅读

• 原始论文 PDF：Erlingsson et al., “RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response”, CCS 2014
• Google 开源实现：github.com/google/rappor——含 Python 模拟器和参数调优工具
• Warner 1965 随机应答原始论文：Stanley Warner, “Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias”, JASA 1965
• Apple 差分隐私技术报告（2017）：对比 RAPPOR 的双层设计与 Apple 的 CMS/HCMS 方案
• Duchi et al. 2013 的 minimax 下界为 RAPPOR 的精度损失提供了理论解释
• 后续改进：Fanti et al., “Building a RAPPOR with the Unknown”, PoPETs 2016——处理未知字符串域的扩展版本

关联

• duchi-local-dp-2013 —— 给出了 LDP 的精度理论下界，RAPPOR 的精度损失正是该定理的直接体现
• mironov-renyi-dp-2017 —— Renyi 差分隐私为多轮组合提供了更紧的隐私预算记账方式，改进 RAPPOR 的组合分析
• dwork-dp-2006 —— 差分隐私的奠基论文，定义了 epsilon-DP 的语义；RAPPOR 是其”本地化”版本
• apple-dp —— Apple 2017 年部署的本地差分隐私系统，继承 RAPPOR 的客户端加噪架构但改用 Count Mean Sketch
• bloom-filter —— RAPPOR 的编码层核心数据结构，把无限字符串域压缩到固定长度位向量
• warner-randomized-response-1965 —— 1965 年随机应答原始论文，RAPPOR 隐私机制的思想源头
• google-prochlo-2017 —— Google 后续的 Prochlo/Encode-Shuffle-Analyze 架构，可视为 RAPPOR 的演进版

反向链接

• abadi-dpsgd-2016 —— DP-SGD 2016 — 给深度学习训练加上差分隐私保护
• bonawitz-fl-system-2019 —— Bonawitz 2019 — Google 联邦学习的工业级系统设计
• kairouz-advances-fl-2019 —— Kairouz 2019 — 联邦学习 58 个开放问题路线图
• mcmahan-fedavg-2017 —— FedAvg 2017 — 让手机本地训练模型再上传平均值
• shokri-mia-2017 —— Shokri MIA 2017 — 判断一条数据是否被模型见过