差分隐私

差分隐私（英语：differential privacy）是一个数据共享手段，可以实现仅分享可以描述数据库的一些统计特征、而不公开具体到个人的信息。差分隐私背后的直观想法是：如果随机修改数据库中的一个记录造成的影响足够小，求得的统计特征就不能被用来反推出单一记录的内容；这一特性可以被用来保护隐私。从另一个角度来理解差分隐私，可以将其视为用于公开统计数据库统计特征的算法的一个约束条件。该约束条件要求数据库各记录中的隐私信息不被公开。例如，差分隐私的算法被一些政府部门用于公开人口统计信息或其它统计数据，同时保证各被统计对象的回答的保密；又如，一些公司在收集用户行为信息的时候可以籍此控制包括内部人员在内的访问者可以看到的细节。

粗略地讲，若观察者无法分辨一个算法的输出是否使用了某一特定个体的信息，这样的算法就是差分隐私的。讨论差分隐私时，经常会考量数据库中的个体是否可以被分辨出来。尽管定义时没有直接使用再识别攻击的概念，差分隐私的算法通常可以抵御此种攻击。

差分隐私的概念最早由密码学家提出，因此相关研究也经常与密码学相关联、使用大量密码学术语。

历史

官方的统计机构负责收集个人和组织机构的信息，并公开综合数据以服务大众。例如，1790年美国人口普查收集了居住在美国的个人的信息，并发布了基于性别、年龄、种族和劳役情况的统计表。很久以来，各统计机构在收集信息时都会承诺保密、保证数据只用于统计学用途，但公开发布的数据不可再被用于识别单一的个人或组织。为了实现这一要求，统计机构传统上会在发布时隐去一部分信息。例如，在按照行业分类统计一个城市的各行业营业额情况的表格中，如果某一格的数据仅来自一家公司，则该格数据可能会被隐去，以保证该公司的真实营业额不会因此泄露。

1950到1960年代，各统计机构开始使用电子信息处理系统，大大加快了一个机构可以制作的统计表数量。如此一来，保密信息被不当公开的机会也因而增加了。例如，如果前述的公司被隐去的营业额数据也被统计进了该区域所有公司的总营业额，则用总数减去其他各行业的营业额，仍可得出该公司的真实营业额。更复杂的加减组合亦可能揭示更多信息。随着公开发布的统计表格增加，需要检查的计算方案呈指数增长。如果数据使用者可以在交互式系统中访问统计数据库，则需要检查的计算方案数可能是无上限的。

1977年，托雷·达勒纽斯（Tore Dalenius）用数学语言描述了在表格中隐去一格数据的过程。

1979年，多萝西·丹宁、彼得·丹宁和迈耶施瓦茨（Mayer D. Schwartz）正式提出了“追踪者”的概念。这里的追踪者是指一个具有使用一系列查询并记录结果的能力、可以通过访问统计数据库来获知保密内容的攻击者。该研究及之后的研究分析了统计数据库输出的隐私性质：追踪记录每条查询对数据库中个体的隐私的影响是NP困难的。

2003年，科比·尼西姆和伊里特·迪努尔的研究显示，对于一个统计数据库，公开任意数量的查询结果而不在此过程中泄露任何隐私信息是不可能的，且仅需进行很少次数的随机查询就可以完全揭示整个数据库的每个记录。这一现象被称为信息恢复基本定律。由此可以推知，在绝大多数情况下，如不注入一定程度的噪声，就无法确保隐私。这一结论引出了差分隐私的研究。

2006年，辛西娅·德沃克、弗兰克·麦克雪丽、科比·尼西姆和亚当·D·史密斯的研究提出了确保隐私所需的噪声，并提出一个添加噪声的通用机制。 该研究赢得了2017年的哥德尔奖。

自此以来，后续研究进一步揭示了还有许多可以提供非常准确的统计数据、同时保证高程度隐私的方法。

动机

设想一个受信任的机构持有涉及众多人的敏感个人信息（例如医疗记录、观看记录或电子邮件统计）的数据库，且想提供一个全局性的统计数据。这样的系统被称为统计数据库。尽管表面看来，只有经过处理的统计特征被发布，但这些统计结果也有可能揭示一些涉及个人的信息。例如，当研究人员同时使用两个或多个分别进行过匿名化处理的数据库时，个人信息的匿名化手段仍然可能失效。差分隐私就是为防护这类统计数据库再识别技术而提出的一个概念。

网飞悬赏事件

2006年10月，网飞提出一笔100万美元的奖金，以奖励可将其推荐系统改进10%的参与者。为此，网飞发布了一个训练数据集供开发者训练其系统。在发布此数据集时，网飞提供了免责声明：为保护客户的隐私，可用于识别单个客户的所有个人信息已被删除，并且所有客户ID已用随机生产的ID替代。

然而，网飞不是网络上唯一涉及电影评级的网站。其他很多网站，包括IMDb，亦提供类似的功能：用户可以在IMDb上注册和评价电影，且也可以选择匿名自己的详细资料。德克萨斯州大学奥斯汀分校的研究员阿尔文德·纳拉亚南和维塔利·什马蒂科夫（Vitaly Shmatikov）将网飞匿名化后的训练数据库与IMDb数据库（根据用户评价日期）相连，能够重新识别网飞数据库中的个人。这表明网飞采取的匿名化手段仍然可以泄露部分用户的身份信息。

马萨诸塞州集团保险委员会（GIC）医疗数据库事件

麻省理工学院的拉坦亚·斯维尼将匿名化的GIC数据库（包含每位患者的出生日期、性别和邮政编码）与选民登记记录相连后，可以找出马萨诸塞州州长的病历。

元数据与流动数据库

MIT的德蒙乔耶（De Montjoye）等人引入了单一性（意为独特性）概念，显示出4个时空点、近似地点和时间就足以唯一性识别一个150万人流动数据库中的95%用户。该研究进一步表明，即使数据集的分辨率较低，这些约束仍然存在，即粗糙或模糊的流动数据集和元数据也只提供很少的匿名性。

ε-差分隐私

2006年德沃克等人的文章提出了ε-差分隐私（英语：ε-differential privacy）的概念：用数学语言定义了统计数据库的数据隐私损失。（这里的“统计数据库”是指在承诺保密的条件下收集的一组数据，这些数据仅用于产生统计数据，且在此过程中不损害数据提供者的隐私。）

这一定义背后的想法是：如果在统计数据公开的时候，如果一个人的数据不再数据库里，那他的隐私就不会被泄露。因此，差分隐私旨在为每一个体提供与把对应数据移除可以带来的隐私几乎相同的隐私。也就是说，在这样的数据库上运行的统计函数（例如求和、求平均等）不能过于依赖任何个体的统计数据（即不能依赖任何单一记录）。

当然，每个个体在统计结果中的贡献取决于所使用的查询请求了多少数据。如果一个数据库只含有一个人的数据，那这个人的贡献就是100%。如果数据库里含有一百人的数据，则每个人可能只贡献1%。差分隐私的关键在于，查询请求的数据越少，就要添加越多的噪声，以保证同等程度的隐私。正如2006年论文的标题所说的那样：“在隐私数据分析中用灵敏度标定噪声”。

在提出差分隐私的数学定义的同时，这篇论文还提出了一个基于添加拉普拉斯噪声（即该噪声服从拉普拉斯分布）的机制，该机制满足差分隐私的定义。

定义

令ε为一正实数，而${\mathcal {A}}$ 为一随机算法，以一数据库为该算法的输入。 令${\textrm {im}}\ {\mathcal {A}}$ 为算法${\mathcal {A}}$的像。若对所有的仅有一个记录（例如一个人的数据）不同的两个数据库$D_{1}$和$D_{2}$，以及${\textrm {im}}\ {\mathcal {A}}$的所有子集$S$，

$\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp \left(\varepsilon \right)\cdot \Pr[{\mathcal {A}}(D_{2})\in S],$

则称该算法${\mathcal {A}}$可以提供$\varepsilon$-差分隐私。其中，取概率的随机性来自于算法${\mathcal {A}}$。

差分隐私的定义提供了模块化设计和分析差分隐私机制的方法。差分隐私具有以下性质：可组合性、对后续过程的稳健性，以及在具有相关性的数据上可以自然地退化。

可组合性

可（自）组合性是指（有可能是按照特定顺序排列的）多个差分隐私机制的输出仍然是差分隐私的。

顺序组合（串联）：如果要查询一个ε-差分隐私机制$t$次，而该机制对于多次查询的随机性是独立的，则所有结果是$\varepsilon t$-差分隐私的。更一般地，若有$n$个独立的机制${\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}$，分别为$\varepsilon _{1},\dots ,\varepsilon _{n}$-差分隐私的，则任意一个它们的函数$g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})$是$\left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)$-差分隐私的。

并行组合（并联）：如果前述多个机制实施在一个数据库的不相交的子集上，则函数$g$是$(\max _{i}\varepsilon _{i})$-差分隐私的。

对后续过程的稳健性

对任何定义在${\mathcal {A}}$的像上的确定或随机的函数$F$，若${\mathcal {A}}$是ε-差分隐私的，则$F({\mathcal {A}})$也是。

可组合性和稳健性一同保证了差分隐私机制的模块化设计和分析是可行的。这些性质也促成了“隐私损失预算”的概念。如果访问敏感数据的一组机制各自都是差分隐私的，则它们的组合、外加任意的后续过程也都是差分隐私的。

组隐私

一般而言，ε-差分隐私可以保障两个仅相差一个记录的数据库之间的隐私。也就是说，任何拥有任意外部信息的攻击者都无法知道任何一个个体在数据库中的信息。但这一定义也可以自然地扩展到两个数据库之间相差至多$c$个记录的情况。组隐私希望保证任何拥有任意外部信息的攻击者都无法知道$c$个个体是否在数据库中有信息。这也是成立的，因为如果$c$个记录不同，则概率扩张的上界是$\exp(\varepsilon c)$而不是$\exp(\varepsilon )$，也就是说，对于相差至多$c$个记录的数据库$D_{1}$和$D_{2}$：

$\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot \Pr[{\mathcal {A}}(D_{2})\in S]\,\!$

因此，使用ε而非$\varepsilon /c$即可实现想要的效果（保护$c$个记录）。也就是说，现在每$c$个条目都被ε-差分隐私的机制保护（而对于每一个条目而言，该机制则是$(\varepsilon /c)$-差分隐私的）。

满足ε-差分隐私的机制

因为差分隐私是一个基于概率论的概念，任何差分隐私机制都是随机的。其中一些，例如下述的拉普拉斯机制，依赖于在一个查询需要计算的函数上添加一定的噪声。其它机制，例如指数机制和后验抽样则使用一种由需求决定的概率分布来抽样的方法。

灵敏度

令$d$为一正整数，${\mathcal {D}}$为一组数据库，而$f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}$为一函数。把函数$f$的“灵敏度” 记作$\Delta f$，其定义是

$\Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1}$

其中最大值取在${\mathcal {D}}$ 中任意两个相差至多一个条目的数据库$D_{1}$和$D_{2}$上，而$\lVert \cdot \rVert _{1}$表示$\ell _{1}$范数。

在下面的医疗数据库的例子里，如果把$Q_{i}$作为函数$f$，则该函数的灵敏度是1，因为改变数据库中任意一个记录会使函数的值改变0或1。

有一些方法可以为低灵敏度的函数创建差分隐私的算法。

拉普拉斯机制

参见：添加噪声机制

拉普拉斯机制添加拉普拉斯噪声（即服从拉普拉斯分布的噪声。该种噪声可以用以下概率密度函数表示：${\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!$，其均值为0，标准差为${\sqrt {2}}\lambda \,\!$）。假设算法${\mathcal {A}}\,\!$可以看作一个实值函数，而${\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!$，其中$Y\sim {\text{Lap}}(\lambda )\,\!\,\!$，而$f\,\!$是原本要在数据库上进行的一个查询（也是一个实值函数）。${\mathcal {T}}_{\mathcal {A}}(x)\,\!$可以被视为一个连续随机变量，其中

${\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!$

且至多为$e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!$。把${\frac {\Delta (f)}{\lambda }}\,\!$作为隐私系数$\varepsilon \,\!$。这样，${\mathcal {T}}\,\!$就是一个差分隐私的机制（参考前面的定义）。类似地，其它形式的噪声，例如高斯噪声等，也可以使用。使用其它噪声时的隐私系数需要进行相应的推导。如果在下面的医疗数据库例子里使用拉普拉斯机制，根据前面的推导，若需使${\mathcal {A}}\,\!$满足$\varepsilon \,\!$-差分隐私，则应令$\lambda =1/\varepsilon \,\!$。

根据这个定义，差分隐私可以看作是数据库的统计数据公开机制（例如，负责发布统计查询结果的程序）上的一个条件，而不是对数据库本身的要求。直观上说，这意味着对于任意两个相近似的数据库，一个差分隐私的算法在它们上的运算结果都会是大致相似的。这样的定义也意味着单一记录的存在与否不会大程度地影响算法的输出。

例如，假设有一个医疗数据库$D_{1}$，每条记录是一个二元组(姓名, X)，其中$X$是一个布尔值，表示一个人是否患有糖尿病。

姓名	糖尿病（X）
张三	1
李四	1
王五	0
赵六	0
孙七	1
周八	0

假设一个恶意用户（通常被称作“敌手”）想要知道孙七有没有糖尿病。假设他已经知道该数据库里孙七位于第几行。又假设用户只能使用一个特定的查询$Q_{i}$，该查询只可以返回$X$这一列的前$i$行数值的和。为了找出赵六的具体数值，敌手可以执行$Q_{5}(D_{1})$和$Q_{4}(D_{1})$，然后查看两个数值的差。在上例种，$Q_{5}(D_{1})=3$而$Q_{4}(D_{1})=2$，所以它们相差1。这意味孙七在着“糖尿病”这一列的数值一定是1。这个例子显示了就算不能具体地查询每一行的数值，统计数据库还是有可能会泄露特定个体的信息。

继续看这个例子。如果另有一个数据库$D_{2}$，其中将(孙七, 1)改写为(孙七, 0)，则该恶意用户可以分辨出$D_{2}$和$D_{1}$是不同的数据库，方法是对每个数据库各进行一次$Q_{5}-Q_{4}$计算。但若敌手必须通过一个$\varepsilon$-差分隐私的算法来获取$Q_{i}$的值，如果$\varepsilon$足够小，该敌手就不能看出两个数据库有何差别，也就无法推断出孙七在“糖尿病”一列的数值。

随机化返回值

参见：本地差分隐私

举一个简单的例子，这样的例子在社会科学中尤其常见，在统计调查中经常使用诸如“你是否满足条件A？”这样的问题。不直接记录回答，而是使用如下方法：

1. 投一枚硬币。
2. 如果正面朝上，则再投一次（忽略投出的结果）。然后如实地回答问题。
3. 如果反面朝上，则再投一次。如果正面朝上，就回答“是”；如果反面朝上，就回答“否”。

（注：第二次投掷看上去是多余的。但该步骤实际上是为了防止以下情况出现：“投硬币”这一动作本身可能会被人观察到，就算投掷结果本身没有被公开）有赖于可证伪性，这样做可以提升每个人的回答的保密程度。

但总体上看，如果回答的数量足够多，最终得到的数据仍然是可用的。因为回答被记录为“是”的人里，可以期望有四分之一的人实际上不满足“条件A”，而四分之三则实际上满足。这样，如果令$p$表示实际上满足A的人的比例，则期望上，记录中“是”所占的比例应当是$(1/4)(1-p)+(3/4)p=(1/4)+p/2$。因此，人们可以从统计结果中估计$p$的值。

这一方法的另一个好处是，如果“条件A”是指一个非法行为，则根据被记录的回答“是”不能推断回答者有罪，因为不管实际情况如何，所有人都有一定概率回答“是”。

在这样的依赖随机化回答的例子中，微观数据库（即完全公开每个人回答情况的数据库）或许是可行的。但根据定义，差分隐私仍不允许微观数据公开，只能通过查询（即将多个回答合成为统计数据）进行，因为这样的例子仍不符合差分隐私的要求：每个个体都无法否认自己参与了这一调查（即各记录是否存在于数据库里）。

对变换的稳定性

如果$T(A)$和$T(B)$之间的汉明距离至多是$c$倍的$A$与$B$之间的汉明距离，其中$A,B$是两个数据库，则称一个变换$T$是$c$-稳定的。中的定理2表明，如果一个机制$M$是$\varepsilon$-差分隐私的，则组合$M\circ T$是 $(\varepsilon \times c)$-差分隐私的。

利用这一性质，可以将差分隐私一般化为组隐私，因为可以用$A$和$B$之间的汉明距离$h$来表示一组记录的大小（其中$A$里包含这组记录，而$B$不包含）。这时，$M\circ T$就是$(\varepsilon \times c\times h)$-差分隐私的。

其它定义

差分隐私的原始定义在一些实际应用中可能会太强或太弱，因此也有研究提出一些其它类似的定义。最常用的一种更弱的定义是(ε, δ)-差分隐私，该定义在ε指数倍概率的上界上再增加一个较小的数δ。

现实世界中对差分隐私的应用

至今为止，比较知名的采用差分隐私的应用如下：

• 2008年：美国普查局，应用差分隐私来发布通勤模式的统计数据。
• 2014年：谷歌的RAPPOR，用于监测功能，例如收集劫持用户设置的恶意软件的统计数据。
• 2015年：谷歌，发布历史流量数据。
• 2016年：苹果宣布计划在iOS 10中使用差分隐私来改进其虚拟个人助理技术。
• 2017年：微软，用于Windows中的监测功能。
• 2019年：Privitar Lens是一款应用差分隐私的API。
• 2020年：领英，用于广告商的查询。
• 在数据挖掘模型中使用差分隐私的实际表现已有一些初步研究。

参见

• 准标识符
• 指数机制
• k-匿名性

外部链接

• Privacy of Dynamic Data: Continual Observation and Pan Privacy （页面存档备份，存于互联网档案馆） by Moni Naor, Institute for Advanced Study, November 2009
• Tutorial on Differential Privacy （页面存档备份，存于互联网档案馆） by Katrina Ligett, California Institute of Technology, December 2013
• A Practical Beginner's Guide To Differential Privacy （页面存档备份，存于互联网档案馆） by Christine Task, Purdue University, April 2012
• Private Map Maker v0.2 （页面存档备份，存于互联网档案馆） on the Common Data Project blog
• Learning Statistics with Privacy, aided by the Flip of a Coin （页面存档备份，存于互联网档案馆） by Úlfar Erlingsson, Google Research Blog, October 2014