差分隐私

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
薄荷（讨论 | 贡献）2021年12月19日 (日) 11:31的版本
跳到导航 跳到搜索


差分隐私 Differential privacy是一个用于公开分享数据集信息的系统，它在描述数据集中的群体特征的同时保护了数据集中的个人信息。差分隐私的理念是，如果在数据库中进行任意单次更迭的影响足够小，那么查询结果就不能用于推断任何单一个体的大量信息，因此个体的隐私得以保证。另一种对于差分隐私的描述表示，这是针对发布统计数据库的汇集信息的算法的约束条件，这种算法限制了数据库中信息的记录的个人信息的披露。例如，一些政府机构使用差分隐私算法公布人口信息或其他统计数据，同时确保调查结果的保密性；而公司则使用该算法收集用户行为信息，同时控制哪些信息对于内部分析人员是可见的。


简单来说，如果观察者发现某算法的输出不能推断出一个特定个体的信息是否被用于其计算，则该算法是差分隐私的。通常，差分隐私算法会在识别其信息可能存在于数据库中的个体时被讨论。虽然差分隐私算法不直接涉及身份识别和身份重识别攻击，但它或许能够防御这些攻击。[1]


差分隐私是由密码学家开发的，因此经常与密码学相关，且其大量内容来自于密码学。


历史

官方统计机构负责收集个人或机构的信息并公布汇集数据，以服务公众利益。例如，1790年的美国人口普查收集了生活在美国的个人的信息，并公布了基于性别、年龄、种族和奴役情况的表格。统计机构长期保证收集信息的保密性，即所提供的信息将用于统计目的，但出版物不会产生可追溯到具体个人或机构的信息。为了实现这一目标，统计机构长期以来一直在其出版物中压缩信息。例如，在按产业类别表示某个城镇中企业的销售情况的表格中，只有一家公司信息的单元格可能会被隐藏，从而对该公司的具体销售情况保密。


1950年代和1960年代，统计机构采用了电子信息处理系统，这大量增加了统计机构可产出的表格数量，从而显著提高了不当暴露机密信息的潜在可能性。例如，如果一个企业的销售数字被隐藏，这些数字也被统计在该地区的总销售额中，那么可能从总销售额中减去其他销售额即可确定被隐藏的数据。或者也有可能通过增法和减法的结合，导致隐私信息被泄露。随着出版物数量的增加，需要检查的组合数量呈指数增长，甚至没有上限——如果数据的用户能够使用交互式查询系统对统计数据库进行查询。


1977年，托雷· 达伦纽斯 Tore Daleniu规范了单元抑制 Cell Suppression的数学模型。[2]


1979年，Dorothy Denning、Peter j. Denning和Mayer d. Schwartz正式提出了“跟踪器 Tracker”的概念，这个对手可以通过创建一系列有针对性的查询并储存查询结果，来分析获取统计数据库的机密内容。[3]这项研究和包括之后的研究表明，只有根据（可能是所有）以前的查询来考虑每个新的查询，才能保证数据库的隐私属性。这种工作有时被称为查询隐私，最终的结果是，追溯某查询对于数据库中个人隐私造成的影响是 NP难问题。


2003年，Kobbi Nissim和Irit Dinur证明，在私人统计数据库上发布任意查询而不泄露一些私人信息是不可能的，而且通过公开少得惊人的随机查询的结果就可能会显示数据库的全部信息内容——远远少于以往研究的推断。[4]这种现象被称为信息恢复基本定律 Fundamental Law of Information Recover，其核心观点是，在最普遍的情况下，隐私无法在不加入一定量的噪音的情况下得到保护，这导致了差分隐私的发展。


2006年，Cynthia Dwork、 Frank McSherry、Kobbi Nissim和Adam D. Smith发表了一篇文章，正式确定了需要增加的噪音量，并提出了一种通用的增加噪音的机制。[1] Their work was a co-recipient of the 2016 TCC Test-of-Time Award[5]他们的工作共同获得了2016年移动通信协会时间检验奖[5]和2017年哥德尔奖[6]。


自此，后续的研究展示了许多方法，可以在保证高度隐私的同时，从数据库中生成非常准确的统计数据。[7][8]


ε-差分隐私

2006年Dwork、McSherry、Nissim和Smith的文章引入了ε-差分隐私的概念，这是一个数学定义，用来定义从统计数据库中发布的任何数据所导致的隐私损失。(此处的统计数据库一词是指遵从保密性承诺收集的一组数据，目的是统计数据，同时不会因其数据的产生损害提供数据的个人的隐私。)


2006年，人们对ε-差分隐私的定义的直觉认知是，如果一个人的数据不在数据库中，那么他的隐私就不会因为统计数据的公布而受到损害。因此，差分隐私的目标是给每个人大体相同的隐私性，这将导致他们的数据删除。也就是说，在数据库上运行的统计功能不应过分依赖于任何个人的数据。


当然，任何个体对数据库查询结果的贡献率部分取决于该查询的数据来自的人员的数量。如果数据库只包含来自单个人的数据，则该人的数据贡献率为100% 。如果数据库包含来自100人的数据，则每个人的数据贡献率仅为1% 。差分隐私的主要观点是，由于查询的数据来自的人员数量越来越少，所以查询结果需要被添加更多的噪音以达到同样程度的隐私性。因此，这篇2006年的论文被命名为《隐私数据分析中噪声灵敏度的校准 Calibrating noise to sensitivity in private data analysis》。


这篇2006年的论文给出了差分隐私的数学定义，以及加入拉普拉斯噪音（i. e. 满足拉普拉斯分布Laplace Distribution的噪音）后能够满足该定义的机制。


ε-差分隐私的定义

设 ε 是一个正实数，而 [math]\displaystyle{ \mathcal{A} }[/math] 是一个以数据集作为输入(表示持有数据的受信任方的操作)的随机算法Randomized Algorithm。

让[math]\displaystyle{ \textrm{im}\ \mathcal{A} }[/math]表示数学[math]\displaystyle{ \mathcal{A} }[/math]的映像。如果对于所有在单个元素上不同（例如一个人的数据）的数据集 [math]\displaystyle{ D_1 }[/math]和[math]\displaystyle{ D_2 }[/math] ，以及所有[math]\displaystyle{ \textrm{im}\ \mathcal{A} }[/math]的子集[math]\displaystyle{ S }[/math]满足:

[math]\displaystyle{ \Pr[\mathcal{A}(D_1) \in S] \leq \exp\left(\epsilon\right) \cdot \Pr[\mathcal{A}(D_2) \in S], }[/math]

其中概率取代了算法所使用的随机性，那么算法[math]\displaystyle{ \mathcal{A} }[/math]被认为实现了 [math]\displaystyle{ \epsilon }[/math]差分隐私。[9]


差异化隐私提供了稳健性和鲁棒性保证，其可组合性、对后处理的鲁棒性以及在相关数据存在的情况下的功能损耗，促进了差分隐私机制的模块化设计和分析。


可组合性

(自)可组合性 (Self-)composability是指（可能是自适应选择的）差分隐私机制的输出的联合分布满足差分隐私的条件。


顺序合成 Sequential composition。如果我们对一个ε-差分隐私机制进行[math]\displaystyle{ t }[/math]次查询，并且该机制的随机化独立于每个查询，那么结果将是[math]\displaystyle{ \epsilon t }[/math]- 差分隐私的。在更普遍的情况下，如果存在[math]\displaystyle{ n }[/math]个独立的机制：[math]\displaystyle{ \mathcal{M}_1,\dots,\mathcal{M}_n }[/math]——其隐私保证分别是[math]\displaystyle{ \epsilon_1,\dots,\epsilon_n }[/math]差分隐私，那么它们的任何函数[math]\displaystyle{ g }[/math]：[math]\displaystyle{ g(\mathcal{M}_1,\dots,\mathcal{M}_n) }[/math]是[math]\displaystyle{ \left(\sum\limits_{i=1}^{n} \epsilon_i\right) }[/math]-差分隐私的。


并行合成 Parallel composition。如果前面的机制是在私有数据库的不相交子集上计算的，那么函数[math]\displaystyle{ g }[/math]将是[math]\displaystyle{ (\max_i \epsilon_i) }[/math]-差分隐私的。[10]


后处理的鲁棒性

对于任意在机制[math]\displaystyle{ \mathcal{A} }[/math]的映射上定义的确定性函数或随机函数[math]\displaystyle{ F }[/math]，如果[math]\displaystyle{ \mathcal{A} }[/math]满足ε-差分隐私性，则[math]\displaystyle{ F(\mathcal{A}) }[/math]也满足ε-差分隐私性。


可组合性和后处理的鲁棒性保证了差分隐私机制的模块化构建和分析，并促成了隐私损失预算的概念。如果访问复杂机制的敏感数据的所有部分都是分别差分隐私的，那么不论接下来是任何后处理，它们的组合依然是差分隐私的。


群体隐私

一般来说，设计ε- 差分隐私的目的是保护只有一行不同的相邻数据库之间的隐私。这意味着任何拥有任意辅助信息的对手都不能知道一个特定的参与者是否提交了他的信息。然而，如果我们想要保护不同于 [math]\displaystyle{ c }[/math]行的数据库，这也是可扩展的，这相当于拥有任意辅助信息的对手可以知道 [math]\displaystyle{ c }[/math]特定的参与者是否提交了他们的信息。这是可以实现的，因为如果 [math]\displaystyle{ c }[/math]项发生变化，概率膨胀的界限是[math]\displaystyle{ \exp ( \epsilon c ) }[/math]，而不是[math]\displaystyle{ \exp ( \epsilon ) }[/math]，[11]，例如对于在[math]\displaystyle{ c }[/math]项上不同的 D1和D2来说:

[math]\displaystyle{ \Pr[\mathcal{A}(D_{1})\in S]\leq \exp(\epsilon c)\cdot\Pr[\mathcal{A}(D_{2})\in S]\,\! }[/math]


因此，将 ε 设置为[math]\displaystyle{ \epsilon/c }[/math]可以达到预期的结果（[math]\displaystyle{ c }[/math]项的保护）。换句话说，并非每一项都实现ε- 差分隐私保护，而是每组的[math]\displaystyle{ c }[/math]项都被ε- 差分隐私保护（并且每一项都被[math]\displaystyle{ (\epsilon/c) }[/math]-差分隐私保护）。


ε-差分隐私机制

因为差分隐私是一个概率概念，所以任何差分隐私机制都必然是随机的。其中一些，如接下来描述的拉普拉斯机制，依赖于在我们要计算的函数中添加可控噪声。其他的机制，如指数机制[12]和后验抽样[13]，则是从一个与问题相关的分布系列中取样。


敏感性

设 [math]\displaystyle{ d }[/math]为一正整数，[math]\displaystyle{ \mathcal{D} }[/math]为一数据集，[math]\displaystyle{ f \colon \mathcal{D} \rightarrow \mathbb{R}^d }[/math]是函数。函数的灵敏度[1]记为[math]\displaystyle{ \Delta f }[/math]，定义为：

[math]\displaystyle{ \Delta f=\max \lVert f(D_1)-f(D_2) \rVert_1, }[/math]

其中最大值是[math]\displaystyle{ \mathcal{D} }[/math]中所有最多只有一个元素不同的一对数据集[math]\displaystyle{ D_1 }[/math]和[math]\displaystyle{ D_2 }[/math]，而 [math]\displaystyle{ \lVert \cdot \rVert_1 }[/math]定义了[math]\displaystyle{ \ell_1 }[/math]范数。

在下面的医学数据库的例子中，如果我们认为[math]\displaystyle{ f }[/math]是函数[math]\displaystyle{ Q_i }[/math]，那么函数的灵敏度是1，因为改变数据库中的任何一个条目都会导致函数的输出变为0或1。


我们也可以通过一些技术(如下所述) 使用低灵敏度函数设计差分隐私算法。


拉普拉斯机制

拉普拉斯机制 The Laplace mechanism增加了拉普拉斯的噪音（例如满足拉普拉斯分布的噪声，其可以用概率密度函数[math]\displaystyle{ \text{noise}(y)\propto \exp(-|y|/\lambda)\,\! }[/math]来表示，这个函数的平均值是0，标准差为[math]\displaystyle{ \sqrt{2} \lambda\,\! }[/math]）。在我们的例子中，我们定义了输出函数[math]\displaystyle{ \mathcal{A}\,\! }[/math]作为一个实值函数（由 [math]\displaystyle{ \mathcal{A}\,\! }[/math]调用为文本输出）[math]\displaystyle{ \mathcal{T}_{\mathcal{A}}(x)=f(x)+Y\,\! }[/math]，其中[math]\displaystyle{ Y \sim \text{Lap}(\lambda)\,\!\,\! }[/math]，且[math]\displaystyle{ f\,\! }[/math]是我们计划在数据库上执行的原始实值的查询（或函数）。现在可以确定，[math]\displaystyle{ \mathcal{T}_{\mathcal{A}}(x)\,\! }[/math]可以被认为是一个连续的随机变量，当

[math]\displaystyle{ \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))}\,\! }[/math]


其最多为 [math]\displaystyle{ e^{\frac{|f(D_{1})-f(D_{2})|}{\lambda}}\leq e^{\frac{\Delta(f)}{\lambda}}\,\! }[/math]。我们可以设[math]\displaystyle{ \frac{\Delta(f)}{\lambda}\,\! }[/math]为隐私因子[math]\displaystyle{ \epsilon\,\! }[/math]。因此，[math]\displaystyle{ \mathcal{T}\,\! }[/math]满足差分隐私机制的规则（从上面的定义可以看出）。如果尝试在我们的糖尿病例子中使用这个概念，那么从上述事实可以推出，为了使用[math]\displaystyle{ \mathcal{A}\,\! }[/math]作为[math]\displaystyle{ \epsilon\,\! }[/math]-差分隐私算法，我们需要满足[math]\displaystyle{ \lambda=1/\epsilon\,\! }[/math]。虽然我们在这里使用了拉普拉斯噪音，但是其他形式的噪音，如高斯噪音也是可使用的——但是可能需要稍微放宽差分隐私的定义。[11]


根据这个定义，差分隐私是发布机制的一个条件（例如，由可信方发布数据集的信息），而不是数据集本身。直观地说，这意味着对于任何两个相似的数据集，一个给定的差分隐私算法在两个数据集上的表现将大致相同。该定义强有力地保证了个体的存在与否不会对算法的最终输出产生重大影响。


例如，假设我们有一个关于医疗记录的数据库[math]\displaystyle{ D_1 }[/math]，其中每个记录是一对(Name, X)，其中[math]\displaystyle{ X }[/math]是一个布尔值Boolean Algebra，表示一个人是否患有糖尿病。例如:

Name Has Diabetes (X)
Ross 1
Monica 1
Joey 0
Phoebe 0
Chandler 1
Rachel 0

现在假设一个恶意用户（通常称为对手）想要查看 Chandler 是否患有糖尿病。假设他也知道 Chandler 在数据库的哪一行中。现在假设对手只被允许使用特定形式的查询[math]\displaystyle{ Q_i }[/math]，该查询返回数据库中列[math]\displaystyle{ X }[/math]的第一个[math]\displaystyle{ i }[/math]行的部分和。为了查找Chandler的糖尿病状态，对手执行 [math]\displaystyle{ Q_5(D_1) }[/math]和[math]\displaystyle{ Q_4(D_1) }[/math] ，然后计算它们的差值。在这个例子中，[math]\displaystyle{ Q_5(D_1) = 3 }[/math]和 [math]\displaystyle{ Q_4(D_1) = 2 }[/math]，所以它们的差值是1。这表示 Chandler 行中的“Has Diabetes”字段必然为1。这个例子强调了即使不显式查询特定个人的信息，个人信息也可能被泄露。


继续讨论这个例子，如果我们用(Chandler, 0)替换(Chandler, 1)来构造[math]\displaystyle{ D_2 }[/math]，那么这个恶意的对手将能够通过计算每个数据集的[math]\displaystyle{ Q_5 - Q_4 }[/math]来区分[math]\displaystyle{ D_2 }[/math]和[math]\displaystyle{ D_1 }[/math]。如果对手被要求通过一个 [math]\displaystyle{ \epsilon }[/math] 差分隐私算法对于一个足够小的[math]\displaystyle{ \epsilon }[/math]接收[math]\displaystyle{ Q_i }[/math]值，那么他或她将无法区分两个数据集。


随机应答

举一个简单的例子，尤其是在社会科学领域[14]，这就是指让一个人遵从下列程序回答“你拥有属性A吗？”:

  1. 抛硬币Toss a Coin。
  2. 如果是正面，再掷一次硬币（忽略结果），并诚实地回答问题。
  3. 如果是反面，再掷一次硬币，如果是正面，回答“是”; 如果是反面，回答“否”。


（在第一种情况下，看似多余的额外投掷是必要的，因为在这种情况下，即使实际结果仍然隐藏着，仅仅是抛硬币的动作就可能被其他人观察到。）这种保密性来自于个人反应的可驳性。


但是，总的来说，这些有很多回答的数据是有意义的，因为有四分之一的人给出了肯定的回答，而有四分之三的人给出了真正拥有A属性的人的答案。因此，如果p是A型人群的真实比例，那么我们期望得到(1/4)(1-p) + (3/4)p = (1/4) + p/2的积极反应。因此，我们可以估计p。


特别是，如果属性A是非法行为的同义词，在这个人有可能回答“是”的情况下，无论结果可能是什么，回答“是”并不意味着定罪。


虽然这个例子受到了随机应答Randomized Response的启发，可能适用于微数据Microdata（例如，发布每个响应的数据集），但根据定义，差分隐私排除了微数据的发布，并且只适用于查询（例如，将单个响应聚合成一个结果），因为这将违反其要求，更具体地说，是对一个主体是否参与的合理否认。[15][16]


稳定转换

对于任意两个数据库[math]\displaystyle{ A,B }[/math]，如果[math]\displaystyle{ T(A) }[/math]和 [math]\displaystyle{ T(B) }[/math])之间的汉明距离最多是[math]\displaystyle{ A }[/math]和[math]\displaystyle{ B }[/math]之间的汉明距离Hamming Distance的[math]\displaystyle{ c }[/math]倍，则变换[math]\displaystyle{ T }[/math]是 [math]\displaystyle{ c }[/math]-稳定的。文章[10]中的定理2指出，如果存在一个机制[math]\displaystyle{ M }[/math]是[math]\displaystyle{ \epsilon }[/math]-差分隐私的，那么复合机制[math]\displaystyle{ M\circ T }[/math]也是[math]\displaystyle{ (\epsilon \times c) }[/math]-差分隐私的。


这可以推广到群组体隐私，因为群体大小可以被视为[math]\displaystyle{ A }[/math]和[math]\displaystyle{ B }[/math]之间的汉明距离[math]\displaystyle{ h }[/math]（其中[math]\displaystyle{ A }[/math]包含群组，而[math]\displaystyle{ B }[/math]没有）。在这种情况下，[math]\displaystyle{ M\circ T }[/math]是[math]\displaystyle{ (\epsilon \times c \times h) }[/math]-差分隐私的。


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

在实践中，差分隐私的几个用途已经为人所知：

  • 2008：美国人口普查局，用于显示通勤模式。[17]
  • 2014：谷歌的 RAPPOR，用于遥测，例如了解不受欢迎的软件劫持用户设置的统计数据[18][19]
  • 2015：Google，用于分享历史流量统计数据。[20]
  • 2016：苹果公司宣布打算在iOS 10中使用差分隐私来改进其智能个人助理技术。[21]
  • 2017：微软，用于Windows遥测系统。.[21]
  • 2019：Priveritar Lens是一个使用差分隐私技术的 API。[22]
  • 2020：LinkedIn，用于广告商查询。[23]


公共目标的考虑

关于差分隐私技术，有几个重要的公共目标的问题需要考虑，尤其是对于那些对此技术的社会机遇和风险感兴趣的决策者和政策聚焦的受众而言：[24]


  • 数据的效用及准确性 Data Utility & Accuracy。差分隐私的主要关注点在于数据效用和个人隐私之间的权衡。如果将隐私损失参数设置为有利于实用性，则隐私性降低（向系统中加入的“噪音”较少）; 如果将隐私损失参数设置为有利于隐私性，则数据集的准确性和效用降低（向系统中注入更多的“噪音”）。对于决策者来说，重要的是要考虑差分隐私的权衡，以帮助建立适当的最佳实践标准来使用这种隐私保护机制，特别是考虑到组织用例的多样性。但是值得注意的是，准确性和效用的降低是所有的限制统计数据泄露的方法的共同问题，而并非只属于差分隐私。然而，独特之处在于，决策者、研究人员和实施者可以考虑如何减轻这种权衡带来的风险。


  • 数据隐私及安全 Data Privacy & Security。差分隐私提供了一个量化的隐私损失度量和上限，并允许管理者在隐私和准确性之间做出明确的权衡。它对仍然未知的隐私攻击具有鲁棒性。然而，它鼓励更大的数据共享——如果做得不好，会增加隐私风险。差分隐私意味着隐私是受到保护的，但这在很大程度上取决于选择的隐私损失参数，并可能会导致对安全性的错误认识。最后，尽管它对未来不可预见的隐私攻击具有鲁棒性，但可能会有我们无法预测的对策被设计出来。


另见


参考文献

引用错误：Closing tag missing for <references>


进一步阅读

取自“https://wiki.swarma.org/index.php?title=差分隐私&oldid=27944”