辛西娅·德沃克

破除误解：加噪声不是差分隐私，删姓名更不是#

把连续字段加上随机扰动，或把姓名换成编号，都不自动得到差分隐私。差分隐私是相邻数据集上输出测度的倍数约束。必须先固定「相邻」指哪一个保护单位：一条记录、一个用户、还是一户。没有相邻关系，谈 $\varepsilon$ 没有意义。

第二个误解是把 $\varepsilon$ 读成「泄露了百分之几的人」。$\varepsilon$ 是对数几率比的上限。$\varepsilon=0$ 表示输出与数据独立；$\varepsilon$ 很大时定义几乎不限制机制。没有敏感度、组合规则和贡献上界，$\varepsilon$ 只是装饰。隐私工程 里的去标识清单解决不了这件事：辅助数据一变，昨天的等价类可以重新变成准标识。

第三个误解是把差分隐私等同于 密码学基础 里的语义安全。后者隐藏明文消息，通常只对多项式对手成立，并依赖单向函数一类假设。纯 $\varepsilon$-差分隐私隐藏的是参与关系，常常对计算无界的观察者成立，但查询答案本身仍要有用。把「可证明安全」四个字共用，会让人口普查的噪声和公钥加密的归约听起来像同一条定理。

现场：相邻、拉普拉斯与组合#

记 $D\sim D'$ 表示两个数据集只差一个保护单位。随机机制 $M$ 满足 $\varepsilon$-差分隐私，若对任意相邻对和任意可测输出集合 $S$，

$$\Pr[M(D)\in S]\le e^{\varepsilon}\Pr[M(D')\in S].$$

$(\varepsilon,\delta)$ 版本在右侧加一项 $\delta$，允许极小概率的定义失效；$\delta$ 必须小到不能把整行记录编码进失败事件，常见要求远小于 $1/n$。

函数 $f$ 的 $\ell_1$ 敏感度 $\Delta_1$ 是相邻数据集上 $\|f(D)-f(D')\|_1$ 的最大变化。拉普拉斯机制在每个坐标加独立的 $\mathrm{Lap}(\Delta_1/\varepsilon)$ 噪声，密度正比于 $e^{-\varepsilon|z|/\Delta_1}$，于是输出密度的对数比被 $\varepsilon$ 钉住。高斯机制对 $\ell_2$ 敏感度加高斯噪声，通常只给出 $(\varepsilon,\delta)$。指数机制按打分函数在离散候选上抽样，用于中位数、合成表一类非向量输出。

德沃克坚持的不只是这一条不等式，而是它能组合。基本组合： $k$ 次 $\varepsilon$-DP 自适应查询是 $k\varepsilon$-DP。隐私被当成预算，花一次少一次。高级组合（德沃克、罗斯布鲁姆、瓦德汉等）把总损失改进到约 $O(\varepsilon\sqrt{k\log(1/\delta')})$，平方根来自隐私损失随机变量的集中。没有组合，每次临时报表都是一次无法累加的「我们加了噪声」；有了组合，系统必须拒绝未记账的查询和缓存旁路，否则账本是假的。这与 计算机安全原则 里「机制必须关闭旁路」是同一类纪律，只是旁路从内存变成了未会计的查询。

后处理定理说：对差分隐私输出再做任意不回看原始数据的计算，不会削弱保证。于是平均、画图、写进新闻稿，都已经包含在第一次噪声里。反过来说，仪表盘若再去打未加噪的微数据，保证作废。定义把「发布」当成一次测度上的承诺，而不是一张可以反复打补丁的表。

信任边界决定噪声该加在哪一侧。中心模型假定有一位被信任的保管人，能看原始记录、只发布加噪结果，同样查询下噪声通常最小。本地模型要求每个人在交出数据前就随机化，保管人从未看见真值；代价是达到同样 $\varepsilon$ 往往要大一个数量级以上的噪声。洗牌模型介于两者之间：本地随机化后再由匿名通道打乱顺序。模型选择不是口味，是你是否允许任何一方看见微数据。消费级遥测常走本地模型并把 $\varepsilon$ 设得很大，语法上仍是差分隐私，保证上接近空洞。

1992 年，德沃克与纳奥尔还写过另一条与「免费查询」相反的思路：用计算定价来减慢批量滥用——让每次请求都付出可调节的工作量，使大规模抓取变贵，而不必识别谁是攻击者。这与差分隐私不是同一条定理，但同属她对滥用的立法习惯：不要维持一份攻击者黑名单，而要把伤害写成对所有人一视同仁的代价。定价处理的是速率，差分隐私处理的是参与关系，两者可以叠用，不能互相替代。

非延展、格与部分同步：更早的两次立法#

1991 年，多列夫、德沃克与纳奥尔提出非延展密码（期刊版 2000）。语义安全禁止从密文读出明文的函数；非延展禁止改写密文，使解密结果变成与原明文相关的另一条消息。拍卖里把别人的密封出价加一、投票里把赞成改成反对，都是延展性攻击。选择密文安全的现代游戏（IND-CCA）与非延展性在多项式对手下密切相关。德沃克在这里的手法与后来的差分隐私同构：不要列举已知篡改，而要让任何相关变换在游戏里都赢不了。

1997 年，阿吉泰与德沃克给出一类基于格的公钥方案，安全性可归约到格上最坏情况问题。最坏情况到平均情况的归约是格密码的方法论核心：若平均实例可破，则最坏实例也可破，因而「随机密钥看起来容易」不能当攻击借口。当代 NIST 后量子候选大量走格；阿吉泰–德沃克方案本身已不在部署前线，但「不要只假设平均实例硬」这一立法被保留下来。

更早还有一条常被隐私叙事漏掉的线。1988 年，德沃克、林奇与斯托克迈尔证明：在部分同步网络里，共识可以终止——消息延迟有上界，只是上界何时生效未知。形式对象见 Dwork–Lynch–Stockmeyer 1988。完全异步下，费希尔–林奇–帕特森（FLP）给出确定性共识的不可能；部分同步把不可能改写成超时与视图更换。后来的区块链实用协议（包括 PBFT 家族）多在这条模型里讨论活性。德沃克的名字因此同时出现在密码学、分布式计算与隐私三个索引里，不是跨界客串，而是同一习惯：先钉模型，再问可能与不可能。

1992 年她与纳奥尔提出用处理定价对抗垃圾邮件：发信必须附带一次中等难度的计算，普通用户只付短暂延迟，大规模群发则变成成本。这不是后来比特币的账本，但把滥用带宽改写成了可定价的工作量。身份认证处理「你是谁」，这里处理「你付得起多少计算」。身份与定价被拆开。工作量证明后来被接到能耗竞赛上，1992 年的论文并无那份激励。合同会迁移。

公平：把「相似的人应被相似对待」写成利普希茨#

2012 年，德沃克、哈特、皮塔西、赖因戈尔德与泽梅尔的 Fairness Through Awareness 把个体公平写成：若两人在任务相关度量下距离为 $d$，则分类器对他们的输出分布距离至多是 $d$ 的利普希茨函数。这与群体公平（人口统计均等、均衡赔率）不是同一句话。群体约束可以在每个群体内部继续对相似个体给出相反决定；个体约束则要求度量本身被公开讨论——公平的争议被推到「谁与谁算相似」，而不是藏进一条准确率数字。

德沃克的立场很硬：没有度量，谈公平是空的；度量一旦给定，算法不应再引入额外的任意性。反对意见同样硬：任务相关度量从哪里来？谁有权定义相似？个体公平在高维、稀疏、历史带偏差的数据上可能不可操作，而群体统计更容易审计。她没有声称自己结束了这场争论。她声称的是：若你拒绝写出度量，你就把任意性留在系统里，只是换了名字。

代价与争议#

人口普查。 美国人口普查局在 2020 年披露规避系统中采用差分隐私，用自顶向下算法把噪声按地理层次注入。州级人口常被设为不变量，街区与交叉表吃掉预算。局方的起点是对 2010 年传统交换与抑制的内部重构：旧方法不足以在现代辅助数据下守住微观记录。人口学家与若干州指出小地区出现与常识冲突的波动，影响拨款与选区。争议不是「差分隐私是否为定义」，而是在法定精度义务下 $\varepsilon$ 与层次分配有没有被选对。定义保证参与关系的不可区分，不保证每一个稀疏格子的相对误差都让规划部门满意。

工业里的大 $\varepsilon$。 消费电子与浏览器遥测常用本地差分隐私，并把 $\varepsilon$ 设到两位数。定义仍然成立，保证却接近空洞。德沃克多次区分「符合语法的差分隐私」与「参数下仍有意义的差分隐私」。把前者写成产品广告，是对 2006 年论文的广告性误用。

公平指标的冲突。 个体公平、群体均等、校准，三者在人口基线不同时无法同时成立——这是后续文献里的不可能定理，不是德沃克 2012 年论文单独宣布的。她的论文把讨论从「算法有没有偏见」推向「偏见相对哪一套度量」。法律若只写「不得歧视」而不写可检验的邻近关系，工程师仍会退回可训练的代理指标，而那些代理不必满足任何利普希茨。

预算、相邻、敏感度这些词之所以能进入统计机构的文件，是因为它们可以被违反、被测量、被辩论。尚未写成专论的概念篇可以展开机制清单；人物页只需要记住，清单之前先有一次合同改写。她不相信建立在对手缺信息之上的安全，也不相信建立在「看起来很糊」之上的隐私。

组合定理把隐私变成可以花光的预算，而不是一次性咒语。若你要极高精度的细格子计数，你就在花预算；若你拒绝花预算，你就在拒绝那种精度。不允许的是第三种话：又要细格子，又声称对每一个体毫无影响。美国 2020 年普查采用差分隐私作为披露控制的一部分，把这场参数争论从论文搬进了公共行政。支持者看到的是：联邦发布物第一次拥有可陈述的个体承诺。批评者看到的是：小地区计数与历史可比性被噪声扰动。两边争的是预算怎么花，不是要不要再删几个姓名。人物页停在这里是刻意的。

抗垃圾邮件的定价路线也有后续讽刺。工作量证明后来成为加密货币的能耗来源。1992 年的论文只想提高滥发成本，没有设计永久竞赛。这提醒读者：把滥用改写成定价，定价对象仍可能被接到另一套激励上。合同会迁移。非延展、部分同步、差分隐私与个体公平，看起来题材分散，方法却一致：先规定对手与失败测度，再要求机制在最坏情况下仍给出可组合的界限。

跨域连接#

• 概率：差分隐私约束的是相邻输入上输出分布的逐点倍数，拉普拉斯与高斯把敏感度翻译成尺度，高级组合则是隐私损失随机变量的集中。没有尾界，只剩下最坏情况的 $k\varepsilon$ 相加。本地模型把随机化提前到每个人交出数据之前，同一 $\varepsilon$ 下方差通常大一个数量级——硬币花在信任边界上，不是花在精度广告上。
• 测度论：纯 $\varepsilon$ 定义必须对所有可测集成立，而不是对几个预先写好的查询成立。这就是后处理无法救出已经太大的 $\varepsilon$ 的原因：任何可测事件的几率比已经被钉死。$\delta$ 对应一小块可以不服从倍数约束的质量，必须防止它大到能编码整行。把隐私写成「平均起来差不多」，与定义不是同一个对象。
• 国家能力：普查要同时完成清点与承诺不伤害。差分隐私把第二件任务参数化，于是第一件任务的小地区精度变成可谈判的预算。能力不只是能采集，也包括能在公开参数下解释误差，并承受稀疏格子上的政治成本。没有会计的噪声，国家只是在暗箱里改数；有会计而无合理 $\varepsilon$，国家只是把伤害改名为保护。
• 信息哲学：差分隐私拒绝「匿名之后信息还在、人却消失」的图像。它承认发布的是仍关于群体的信息，只限制单一个体造成的额外可区分性。知情与伤害被拆开：统计知识可以增加，参与关系的后验倍数却被 $\varepsilon$ 封顶。所有权不自动给出几率比；定义才给出。
• 信息不对称：中心模型把微数据交给保管人，公众只看见加噪输出，不对称被设计进协议。本地模型把不对称反过来，个人先随机化，机构失去精度。非延展性处理的是另一层不对称：持有密文的人不应获得对明文做合法相关变换的能力。德沃克的几条定义都在问：不对称还剩哪一层，以及那一层有没有被写进游戏。

人物小记：把「对已知攻击安全」改成「对相邻对象不可区分」#

德沃克没有图灵奖，但差分隐私已经进入法律、统计机构和机器学习的默认词汇。这种进入有双刃：词汇普及的速度高于参数纪律普及的速度。她在微软研究院与哈佛的任职，使定义同时出现在理论会议与产品备忘录里，也使她必须反复重申 $\varepsilon$ 不是徽章。

若把贡献压成一句：保护若只针对今天叫得出名字的攻击，明天就会过期；保护若写成相邻对象上的分布约束，攻击名单可以增长而定义不必重写。 非延展、格上的最坏情况归约、差分隐私、个体公平，都是这句话的实例。人口普查的争吵证明，实例化参数仍然是政治。定义能做的，是迫使政治在公开的 $\varepsilon$ 上发生，而不是发生在不可审计的抑制规则里。她不相信建立在对手缺信息之上的安全，也不相信建立在「看起来很糊」之上的隐私。预算可以争论，相邻关系可以重画，账本这一形状必须留下。

参考文献#

• Dwork, C., McSherry, F., Nissim, K. & Smith, A. Calibrating Noise to Sensitivity in Private Data Analysis. TCC, 2006.
• Dwork, C. Differential Privacy. ICALP, 2006.
• Dwork, C. & Roth, A. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 2014.
• Dolev, D., Dwork, C. & Naor, M. Non-Malleable Cryptography. SIAM Journal on Computing 30(2), 2000.（会议版 STOC 1991）
• Ajtai, M. & Dwork, C. A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC, 1997.
• Dwork, C., Lynch, N. & Stockmeyer, L. Consensus in the Presence of Partial Synchrony. Journal of the ACM 35(2), 1988.
• Dwork, C., Hardt, M., Pitassi, T., Reingold, O. & Zemel, R. Fairness Through Awareness. ITCS, 2012.
• Dwork, C. & Naor, M. Pricing via Processing or Combatting Junk Mail. CRYPTO, 1992.
• Dwork, C., Rothblum, G. N. & Vadhan, S. Boosting and Differential Privacy. FOCS, 2010.
• Dwork, C. & Naor, M. Pricing via Processing or Combatting Junk Mail. CRYPTO, 1992.
• Dwork, C. A Firm Foundation for Private Data Analysis. Communications of the ACM 54(1), 2011.

延伸阅读#

• Abadi, M. et al. Deep Learning with Differential Privacy. CCS, 2016.
• National Academies of Sciences, Engineering, and Medicine. 2020 Census Data Products: Data Needs and Privacy Considerations. NAP, 2020.
• ep Learning with Differential Privacy.* CCS, 2016.
• National Academies of Sciences, Engineering, and Medicine. 2020 Census Data Products: Data Needs and Privacy Considerations. NAP, 2020.