跳转到内容
← 返回计算理论
计算理论当代约 17 分钟阅读

差分隐私

Differential Privacy

差分隐私拉普拉斯机制组合定理矩会计本地差分隐私

2006 年，辛西娅·德沃克（Cynthia Dwork）、弗兰克·麦克雪莉（Frank McSherry）、科比·尼西姆（Kobbi Nissim）与亚当·史密斯（Adam Smith）在 ICALP 上给出一套把「参与数据集是否改变输出分布」写成不等式的定义。同一会议周期里，德沃克的综述把这个定义命名为差分隐私（differential privacy）。它要挡住的不是某一种再识别技巧，而是一类更强的对手：即使对手已经知道除你以外所有人的记录，也不能从发布结果里确认你在不在表中——至少不能超出由 ε\varepsilon 控制的倍数。

定义的现场感来自更早的失败。把姓名删掉、把邮编截断、把 $k$-匿名当成匿名，一次次被辅助数据击穿。差分隐私改问一个可证明的问题：机制 $M$ 在相邻数据集上的输出分布，能够相差多少。

破除误解：差分隐私不是加一点噪声，更不是教人躲过隐私

常见的假故事有三条。第一，以为「加高斯噪声」就是差分隐私。噪声必须按灵敏度校准，相邻关系必须写明，预算必须记账。随手加噪声可以既毁掉统计、又不给出任何 ε\varepsilon。第二，以为 ε\varepsilon 越小越好到可以忽略效用。ε=0\varepsilon=0 的机制输出与数据独立，于是什么也学不到。差分隐私是一条斜率，不是开关。第三，把差分隐私读成规避隐私规则的技术说明书。它不是。它是发布方约束自己推断能力的数学；它不提供、也不讨论如何削弱别人的保护、如何还原被保护的记录、如何绕过审计。本文只解释定义、机制与制度争论，不进入攻击步骤。

另一个技术误解是把「个体」理解成数据库的一行主键。相邻关系是设计者选的：可以是一条记录、一个用户的全部事件、一个设备上有界贡献的更新。相邻选错，保证就会保证错的东西。用户级相邻比事件级相邻更贵，因为灵敏度按该用户可能贡献的最大范数来量。人口普查、广告归因、联邦学习各自要先写清「谁算一个个体」，再谈 ε\varepsilon。

最后，差分隐私不替代加密、访问控制和数据最小化。加密保护的是传输与存储中的明文；差分隐私保护的是授权计算的输出仍可能泄露参与信息。两者回答不同的威胁。见 隐私工程 对数据动作与后果的分工。

定义：相邻、灵敏度与 $(\varepsilon,\delta)$

设 $D$ 与 $D'$ 至多差一个约定个体的数据，称为相邻。随机机制 $M$ 满足 ε\varepsilon-差分隐私，若对任意相邻对、任意可测输出集合 $S$，

Pr⁡[M(D)∈S]≤eεPr⁡[M(D′)∈S].\Pr[M(D)\in S] \le e^{\varepsilon}\Pr[M(D')\in S].

ε\varepsilon 是隐私损失的对数倍数。ε=0.1\varepsilon=0.1 时两分布的似然比被压在大约 $1.1$ 附近；ε=8\varepsilon=8 时倍数可以到 e8≈2980e^8\approx 2980，保证变弱，往往只对非常弱的对手叙事还有意义。(ε,δ)(\varepsilon,\delta)-差分隐私允许再加一项 δ\delta：坏事件可以以 δ\delta 概率突破倍数约束。δ\delta 通常取远小于 $1/n$ 的量，避免「把一个指定个体直接输出」这种灾难以不可忽略的概率发生。

全局灵敏度 Δ1f=max⁡D∼D′∥f(D)−f(D′)∥1\Delta_1 f=\max_{D\sim D'}\|f(D)-f(D')\|_1 量的是查询在相邻数据集上最多能跳多远。计数查询的灵敏度常为 1；求和则取决于单个个体能贡献的上下界，必须先截断。没有界，灵敏度可以是无穷，拉普拉斯机制无从校准。

后处理不变性是定义送出的第一件礼物：对 $M$ 的输出再做任何不看原始数据的计算，不会让 ε\varepsilon 变差。组隐私则说：若 $k$ 个个体同时变化，保证退化到大约 kεk\varepsilon。这解释了为什么「用户级」比「一次点击级」贵。

拉普拉斯机制与高斯机制

拉普拉斯机制针对实值向量查询 $f$。对每个坐标加独立的 Lap(Δ1f/ε)\mathrm{Lap}(\Delta_1 f/\varepsilon) 噪声，得到纯 ε\varepsilon-DP。证明是：拉普拉斯密度的对数差正好被 ℓ1\ell_1 距离控制，灵敏度把这个距离封顶。直方图、计数、有界均值都走这条路。

高斯机制改用 ℓ2\ell_2 灵敏度 Δ2f\Delta_2 f，加协方差与 Δ2f\Delta_2 f、ε\varepsilon、δ\delta 相关的各向同性高斯噪声，得到 (ε,δ)(\varepsilon,\delta)-DP。高维时 ℓ2\ell_2 往往远小于 ℓ1d\ell_1\sqrt{d}，同样的查询在高斯机制下噪声更省。深度学习里的梯度是高维向量，这就是为什么 DP-SGD 走高斯而不是拉普拉斯。

指数机制面向离散输出：按打分函数 $q(D,r)$ 以正比于 exp⁡(εq/2Δq)\exp(\varepsilon q/2\Delta q) 的权重抽样，用于中位数、选一项发布等「答案不是数字」的场合。报告噪声最大（report-noisy-max）从一组查询里选出噪声后最大的那个，只付一次选择的预算，而不是为每个查询各付一次。机制的设计空间，核心是把灵敏度从「整张表」降到「一次选择」。

稀疏向量技术允许对可能很长的查询流作阈值检验：只为「越过阈值」的查询付费。它极其容易实现错——阈值噪声、检查噪声、是过是不过的记账，任何一处漏记都会在组合上破产。差分隐私的论文与工程事故，有相当比例发生在「我以为这个查询是免费的」。

组合：基本、高级与矩会计

差分隐私能落地，是因为组合定理让多次发布可以记账。基本组合：若各机制满足 εi\varepsilon_i-DP，自适应或非自适应地依次运行，总保证是 ∑εi\sum\varepsilon_i。$k$ 次 ε\varepsilon 就是 kεk\varepsilon。线性累加很快把预算花光。

高级组合（Dwork、Rothblum、Vadhan 等，以及后续精化）说：对 (ε,δ)(\varepsilon,\delta) 机制重复 $k$ 次，总隐私损失大约是 εklog⁡(1/δ′)\varepsilon\sqrt{k\log(1/\delta')} 量级，而不是 kεk\varepsilon，外加可控的 δ′\delta'。平方根来自隐私损失随机变量的集中：每次查询是一次小的对数似然比，和的尾界比最坏线性更好。条件是每次的 ε\varepsilon 不能太大，否则 ε(eε−1)\varepsilon(e^{\varepsilon}-1) 那一项会重新变成线性。

矩会计（moments accountant）由阿巴迪等人在 2016 年的深度学习差分隐私工作中普及。它对高斯机制的隐私损失做矩母函数跟踪，得到比通用高级组合更紧的 (ε,δ)(\varepsilon,\delta) 曲线，特别适合小噪声、多步 SGD。后续的 Rényi 差分隐私（Mironov）、zCDP（Bun、Steinke）和高斯 DP（Dong、Roth、Su）把会计从「定理套用」推进到「按噪声倍率查表」。没有会计，就没有可信的「我们训练了一千步仍然是 ε=2\varepsilon=2」。

组合是自适应的：下一步查询可以依赖上一步输出。这正是交互式查询接口危险的原因。分析师若可以无限次提问，即使每次 ε\varepsilon 很小，平方根也会被次数追上。差分隐私系统必须把预算当成稀缺资源分配，而不是当作用户体验里的刷新按钮。

本地与中心：谁来随机化

中心模型假定有一个被信任的策展人：先收集明文（或密文后解密），再运行机制并发布。人口普查、官方统计多走这里，因为噪声可以按查询灵敏度加一次，效用远好于每人自己加噪。信任假设是硬的：策展人看到个体数据。安全聚合、可信执行环境、多方计算被用来削弱这个假设，但那是系统补充，不是定义的一部分。

本地模型里每个人在设备上先随机化再上传。没有策展人看见真值。RAPPOR（Erlingsson、Pihur、Korolova，2014）用随机化响应把 Chrome 的主页设置做成本地 DP。苹果后来把本地 DP 用于表情符号、查找建议等。本地 DP 的代价是噪声按人数的平方根累加到估计里：要达到中心模型同样的误差，样本量往往大一个数量级以上。许多产品于是把 ε\varepsilon 放到两位数，名义上「有本地 DP」，统计上接近没保护——这是公开文献里对苹果早期参数的主要批评，而不是教人如何破解那些流水线。

shuffle 模型插在两者之间：本地随机化后再经一个洗牌器打乱来源，分析器只看到无序的消息 multiset。在适当假设下，洗牌可以把本地 DP 放大成更强的中心式保证。它降低对单一策展人的信任，却把信任转移到洗牌器与匿名通道。

人口普查与制度争论

美国 2020 年人口普查在人口统计发布中采用差分隐私，替换更早的交换与抑制方法。争论立刻分成两层。统计层：小地区、细交叉表的误差是否大到损害拨款、选区和科研。法律与政治层：宪法要求的是「计数人口」，还是也包括沿用几十年的细表？差分隐私把以前隐藏在交换算法里的误差，变成了显式的 ε\varepsilon 与会计，于是第一次能被公开骂——这本身是透明度，不是新引入的误差之全部。

官方统计的核心张力是：国家需要可加总的表，民主需要小地区的可见性，隐私需要限制「只差一个人」时表的可区分性。这三件事不能同时做到任意精度。差分隐私没有结束争论，它迫使争论用 ε\varepsilon、相邻关系和误差表来进行，而不是用「我们做了去标识」来结束。

工业界的争论对称。产品想要细漏斗、分位数、用户级留存；隐私预算按查询次数平方根消耗。不预先切分预算，第一次临时报表就会把账掏空。NIST 的指南强调：不公开相邻关系、ε/δ\varepsilon/\delta、贡献上界和组合方式，宣称「使用差分隐私」没有可核查内容。

普查局论证的起点，是对 2010 年传统保护方法的内部重构研究：在现代辅助数据下，交换与抑制不足以守住微观记录的不可区分性。批评者则指出，自顶向下算法把噪声沿地理层次注入后，稀疏街区与交叉表出现与常识冲突的波动，可能影响拨款公式与选区划分。州一级人口常被设为不变量，更细的格子吃掉大部分预算。法律诉讼与学术通信并行，争的不是「不等式是否成立」，而是在法定精度义务下，ε\varepsilon 与层次分配有没有被选对。定义保证参与关系的倍数，不保证每一个小格子的相对误差都让规划部门满意。

与密码学可证明安全不是同一句话

语义安全（如 IND-CPA）问的是：多项式时间对手能否区分两则明文对应的密文。它依赖计算假设，保护的是消息本身，通常不信任信道上的窃听者，但密钥持有者看见明文。差分隐私问的是：无界观察者看过发布结果后，相邻数据库的输出测度相差多少。中心模型信任策展人看见微数据；本地模型才把随机化提前到个人设备。

组合语言也不同。密码学用混合论证与归约损失；差分隐私用预算、高级组合和矩会计。零知识可以验证计算而不复制输入，见 交互式证明与零知识，却不自动给出 ε\varepsilon：可接受的输出仍可能带统计泄漏。把「可证明安全」四个字共用，会让人口普查的噪声和公钥加密的归约听起来像同一类定理。密码学基础 需要最坏情况更强的平均情况困难；差分隐私在纯 ε\varepsilon 下甚至不需要单向函数。

代价与争议

ε\varepsilon 的公共语义至今没有社会共识。密码学里 2−642^{-64} 的失败概率有工程传统；差分隐私的 ε=1\varepsilon=1 或 ε=8\varepsilon=8 没有同等的公众读法。同一数字在中心模型和本地模型里对应完全不同的噪声。报道若只写「启用了差分隐私」，等于什么都没说。

效用与公平会打架。全局灵敏度由最极端个体决定，于是多数人的信号被少数高贡献者的截断规则拖累。对稀疏群体、小地区、罕见病，相对误差先爆炸。保护「任意一个个体」的最坏情况定义，会系统性地牺牲尾部群体的统计可见性。这不是实现 bug，是定义的几何。

侧信道与实现也在定义之外。浮点、随机数、时序、缓存、日志里的未加噪副本，都可以让纸上的 ε\varepsilon 对不上系统。差分隐私论文默认的是理想随机机制；工程必须把随机源、多次运行和调试开关算进威胁模型。本文不讨论如何利用这些缝，只指出：缝存在时，不等式不自动迁移到代码。

机器学习把预算花在成千上万次梯度步上。DP-SGD 能工作，是因为高斯会计比朴素线性组合紧得多，且裁剪把每样本贡献封顶。代价是超参变成隐私参数：裁剪范数、批次、步数、噪声倍率一起决定最终 (ε,δ)(\varepsilon,\delta)。把准确率下降全部归因于「加了噪声」，会忽略裁剪对异质梯度的伤害。

跨域连接

  • 概率论：差分隐私约束的是相邻数据集上输出分布的似然比，因此它首先是关于随机机制的定理，而不是关于加密编码的定理。拉普拉斯密度的尾、高斯的集中、隐私损失随机变量的矩，决定了基本组合与高级组合为什么一个线性、一个接近平方根。没有概率语言，就无法写出可加的预算。
  • 测度论：严格定义必须对任意可测集合 $S$ 成立，而不是只对「看起来像直方图的箱子」成立。连续输出、混合分布、以及 δ\delta 所对应的坏事件，都要在测度空间里说。工程实现若用有限精度浮点代替连续拉普拉斯，等于换了一个不同的测度；保证要重新证，不能口头迁移。
  • 信息几何：Rényi 差分隐私和高斯 DP 把隐私损失看成输出分布之间的散度，而不是单次对数似然比的最坏值。会计于是变成沿训练轨迹积分的几何量：噪声倍率越大，每步走的散度越小。这解释了为何同一 ε\varepsilon 可以对应不同的噪声形状——约束的是散度预算，不是某一种噪声的名字。
  • 国家能力：人口普查采用差分隐私，是国家统计能力与个体不可区分性之间的制度选择。国家需要可加总的表来分配资源，同时又必须限制「只差一名居民」时表的可分辨程度。ε\varepsilon 在这里不只是算法参数，它是行政能力愿意用多少统计精度去换取最坏情况隐私的公开数字；争论的激烈程度，来自这个数字第一次被放到桌面上。

参考文献

  • Dwork, C., McSherry, F., Nissim, K. & Smith, A. "Calibrating Noise to Sensitivity in Private Data Analysis." TCC, 2006; Journal of Privacy and Confidentiality 7(3), 2017.
  • Dwork, C. "Differential Privacy." ICALP, 2006.
  • Dwork, C., Rothblum, G. N. & Vadhan, S. "Boosting and Differential Privacy." FOCS, 2010.
  • Abadi, M. et al. "Deep Learning with Differential Privacy." Proceedings of CCS, 2016.
  • Mironov, I. "Rényi Differential Privacy." IEEE CSF, 2017.
  • Erlingsson, Ú., Pihur, V. & Korolova, A. "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response." CCS, 2014.

延伸阅读

  • Dwork, C. & Roth, A. "The Algorithmic Foundations of Differential Privacy." Foundations and Trends in Theoretical Computer Science 9(3–4):211–407, 2014.
  • NIST. Guidelines for Evaluating Differential Privacy Guarantees (SP 800-226), 2025.