引言

在过去的二十年中，随着数据挖掘技术的普遍应用，一些厂商，组织和政府所收集的数字信息形成了大量的数据集，并且这种数据收集的速度在最近几年中得到了极大的提高。 通常，数据收集者负责发布数据用以进行进一步分析。 然而，大部分收集的数据集都包含隐私或者敏感的信息。 即使数据收集者可以应用几种简单的匿名化技术，敏感的个人信息仍然很有可能被公开。 因此，隐私保护已成为迫切需要解决的问题。

研究人员提出了各种保护个人隐私的方法,并将这些方法及其隐私标准定义为一个隐私模型。如图1所示，隐私模型位于受信任的数据收集者（Curator）和不受信任的公众用户（User）之间。差分隐私就是这样一种新兴的、有前途的隐私模型。它可以保证对手(敌手)在数据集中对任何个体造成伤害的能力基本上是相同的，与任何个体选择进入或退出数据集无关。与以往的隐私模型相比，差分隐私模型能够成功抵御大多数隐私攻击，并提供了可证明的隐私保障。

相关定义

我们假设一个大小为$|x|$的有限数据空间$x$。设$r$表示具有$d$个属性的记录;数据集$D$是从有限数据空间$x$中采样的$n$条记录的无序集合。两个数据集$D$和$D\prime$如果有且仅有一条记录$r$不同，则这两个数据集称为为相邻数据集。查询$f$是一个将数据集$D$映射到抽象范围$R$: $f:D\to R$的函数。一组查询记作$F$。我们用符号$m$表示$F$中的查询数量。

差分隐私的目的是掩盖相邻数据集之间查询$f$的差异。将查询结果$f$的最大差异定义为灵敏度（或者敏感度）$\Delta f$。 通常通过机制$M$实现差分隐私，机制$M$是访问数据库并实现某些功能的随机算法。 随机输出由回旋符号表示，例如，$fˆ(D)$表示在$D$上查询$f$的随机返回答案。图2总结了本文中可能使用到的符号。

(ϵ,δ)-差分隐私

如果$M$满足以下条件，在$D$和$D^{\prime }$的任何相邻数据集中，随机机制$M$为每一组输出$\Omega$提供(ϵ,δ)-差分隐私：

$Pr[M(D)\in \Omega ]\le exp(ϵ)\cdot Pr[M(D^{\prime })\in \Omega ]+\delta$

注：如果$\delta ＝0$，则随机机制$M$通过其最严格的定义给出ϵ-差分隐私。(ϵ,δ)-差分隐私为某些低概率事件提供了违反严格的差分隐私的自由。 ϵ-差分隐私通常称为纯差分隐私，而δ> 0的(ϵ,δ)-差分隐私称为近似差分隐私。

ϵ：隐私预算

在(ϵ,δ)-差分隐私定义中，参数$ϵ$表示隐私预算，它控制机制$M$实现的隐私保证级别。$ϵ$越小表示隐私级别越强。 目前广泛使用两种隐私预算组成定理：顺序组成和并行组成。

1. 并行组成

假设我们有一组隐私机制 M = { M 1 ， … ， M m } M = \{M_1，…，M_m\} M={M1​，…，Mm​}。 如果每个$M_i$对整个数据集的互不相交子集提供ϵi-差分隐私保证，则$M$将提供max {ϵ_1，…，ϵ_m}-差分隐私。

2. 顺序组成

假设在数据集上依次执行一组隐私机制 M = { M 1 ， . . . ， M m } M = \{M_1，...，M_m\} M={M1​，...，Mm​}，并且每个$M_i$提供ϵ-差分隐私保证，则$M$将提供(m⋅ϵ)差分隐私。

Δf：敏感度

对于查询$f:D\to R$，以及相邻数据集$D$和$D^{\prime }$，$f$的敏感度$\Delta f$定义为
$\Delta f=ma{x}_{D,D^{\prime }}||f(D)-f(D^{\prime })||$

敏感度$\Delta f$仅与查询$f$的类型有关，它衡量了相邻数据集上查询结果之间的最大差异。

两种常用的差分隐私保护机制

任何满足差分隐私定义的机制都可以认为是差分隐私的。目前，广泛使用两种基本机制来保证差分隐私: 拉普拉斯机制（The Laplace Mechanism）和指数机制（The Exponential Mechanism）。

拉普拉斯机制（The Laplace Mechanism）

拉普拉斯机制为真实结果增加了独立的噪音，且使用$Lap(b)$表示从比例为$b$的Laplace分布中采样的噪声。拉普拉斯机制适用于数值型查询。

对于数据集$D$上的函数$f:D\to R$(可视为一次查询)，以下公式中的机制$M$提供了ϵ-差分隐私。
$M(D)=f(D)+Lap(\frac{\Delta f}{ϵ}).$

指数机制（The Exponential Mechanism）

对于非数值查询，差分隐私使用指数机制对结果进行随机化处理，并与一个score(评价函数)函数$q(D，\varphi )$一一对应，该函数用于对输出$\varphi$的质量进行评估。score函数取决于具体应用，并且不同的应用可能会有不同的score函数。

设$q(D,\varphi )$是数据集$D$的score函数，该函数衡量输出$\varphi \in \Phi$的质量，$\Delta q$表示$\varphi$的灵敏度。满足以下条件时，指数机制$M$满足ϵ-差分隐私

$M(D)=(return\varphi \propto exp(\frac{ϵq(D,\varphi )}{2\Delta q}))$

差分隐私效用衡量

当隐私级别(隐私预算)固定为$ϵ$时，差分隐私一般使用以下两种效用衡量。

噪声大小测量:最简单的方法是衡量向查询结果添加了多少噪声。噪音越小，效用越高。这种效用度量在数据发布中得到了广泛的应用。

误差测量:效用也可以通过未经隐私保护机制处理输出和经隐私保护机制处理后输出之间的差值来评估。误差测量通常由精度参数的范围表示。

(α,β)可用性

如果满足以下条件，则机制$M$是$(\alpha ，\beta )$可用的
$Pr(ma{x}_{f\in F}|F(D)-Fˆ(D)|\le \alpha )>1-\beta$

其中$\alpha$是限定误差的精度参数。

对于不同的发布场景，误差测量可以使用不同的方式进行解释。对于合成数据集发布，上述公式可以解释为
$Pr(ma{x}_{f\in F}|F(D)-F(Dˆ)|\le \alpha )>1-\beta$

在数据分析中，效用衡量通常取决于具体分析算法。假设算法用$M$表示，隐私算法用$Mˆ$表示，上述公式可以解释为
$Pr(|M(D)-Mˆ(D)|\le \alpha )>1-\beta$

差分隐私在数据发布中的应用

差分隐私数据发布的目的是在不披露任何个人记录（或者说具体个人信息）的情况下向公众输出聚合信息。这个问题可以表述为：如果一个数据收集者有一个数据集$D$，并且收到一个查询集合 F = { f 1 ， … ， f m } F=\{f_1，…，f_m\} F={f1​，…，fm​}，那么他们需要在满足差分隐私约束的前提下回答每个查询$f_i\in F$。

此发布方案涉及交互式和非交互式两个场景（interactive and non-interactive）。 在交互式场景中，只有收到了前一个查询$f_{i-1}$的响应后才能申请下一个查询$f_i$。 在非交互式场景中，所有查询都一次提供给数据收集者，数据收集者可以在充分了解查询集合$F$的情况下响应请求。

下面给出了交互式和非交互式两个场景之间差异的示例。对数据收集者的查询可能如下所示：

• 查询1($f_1$): 40至79岁之间有多少患者患有糖尿病?

• 查询2($f_2$): 40至59岁之间有多少患者患有糖尿病?

假设每次查询的隐私预算$ϵ$是固定的。在交互式场景中，数据收集者将首先收到查询$f_1$，然后计算40至79岁之间患有糖尿病的患者人数，$f_1$的灵敏度为1，并将独立的拉普拉斯噪声$Lap(1/ϵ)$加上。 然后将$f_2$提交给数据收集者时，此时$f_2$的灵敏度将等于2，因为更改表中的任意一个人可能会更改两个查询的结果。 添加到查询集的总噪声为$Lap(1/ϵ)+Lap(2/ϵ)$。

在非交互式场景中，两个查询都同时提交给数据收集者。两个查询的敏感度均为2，添加到查询集中的总噪声为$2\ast Lap(2/ϵ)$，大于交互式场景的总噪声$Lap(1/ϵ)+Lap(2/ϵ)$。 查询之间的相关性也会导致更高的敏感性。 因此，非交互式场景通常会比交互式场景产生更多的噪音。

上面的示例显示了交互式和非交互式两个场景之间的差异，并说明当查询彼此相关时，噪声量会急剧增加。 此外，对于大小为n的数据集，拉普拉斯机制最多只能在n个查询中以一定程度的准确性回答次线性问题。这些缺点使得拉普拉斯机制在需要回答大量查询的场景中效果不理想。

差分隐私在数据分析中的应用

差分隐私数据分析的基本任务是将现有的非隐私算法扩展到差分隐私算法。这种扩展可以通过几个框架来实现，大致分为拉普拉斯/指数框架和隐私学习框架。 其中拉普拉斯/指数框架直接将拉普拉斯或指数机制整合到非隐私分析算法中。 例如，在算法的计数步骤中加入拉普拉斯噪声，或者在进行选择时执行指数机制。

参考和推荐

本文主要主要翻译并整理了论文的一部分内容Differentially Private Data Publishing and Analysis: A Survey
同时推荐一下几篇关于差分隐私的入门资料：

• 某乎用户“Nemo”对问题《苹果的 Differential Privacy 差分隐私技术是什么原理？》的回答
• DP-Differential Privacy概念介绍
• DP-Laplace Mechanism
• DP-指数机制
• 差分隐私保护：从入门到脱坑