前言
本文参考了动手学差分隐私
去标识
去标识是只从数据集中删除标识信息的过程，尤其是唯一标识数据。如果标识信息没删除，就容易造成信息泄露。
倘若删除了唯一标识信息，这样就安全了吗？错，社会工程学就是这么一门学科，可以利用其他标识组合来标识唯一个体。
k-匿名性
介绍
k-匿名性（英语：k-anonymity）是匿名化数据的一种性质。如果一组公开的数据中，任何一个人的信息都不能和其他至少k−1人区分开，则称该数据满足k-匿名性。1显然，任何数据集都天然包含了k=1的1-匿名性。
满足k-匿名性
为了保护数据，一般都要满足k匿名性，k应该为较大的数，如果k过小，那么k-匿名性的隐私保护是不行的。那么有些数据集不满足k-匿名性，应该如何做呢？
一般可以通过泛化（generalization）的方法来更改数据集，比如一个班级的成绩不公布具体分数，只公布整十的分数。已经证明了，实现满足k-匿名性的最有泛化方法是一个NP-hard问题。
差分隐私
介绍
与k-匿名性相类似，差分隐私也是一个用数学语言描述的隐私定义，但是k-匿名性是数据具有的属性，而差分隐私是算法具有的属性，也就是说，我们只能证明一个算法满足差分隐私。给出数学定义：
\frac{\text{Pr}[F(x)=S]}{\text{Pr}[F(x')=S]}\leq e^\epsilon
其中 F 标识具有差分隐私属性的函数，x和x'是邻近数据集（后面进行解释，可以理解为两个数据集非常相近，只有细微区别），S是所有可能输出，\Pr表示概率的意思。用通俗的话来说，就是输入非常相近的两个数据集，这个差分隐私函数输出同一个值的概率非常接近。
- 邻近数据集：如果两个数据集只有一个个体的数据不同，就称为是邻近数据集。
- 差分隐私函数：差分隐私函数一般是个随机函数，也就是输入相同的数据集，输出的结果不一定一样，而是满足某个概率分布。
- 参数\epsilon：称为隐私参数（privacy parameter）或者隐私预算（privacy budget），较小时，F对相似输入的输出也更相似。较大时，则输出更不那么相似。经验来说一般设置成约小于1的数。
拉普拉斯机制
对一个输出数值型结果的函数f(x)来说，定义差分隐私机制：
F(x) = f(x) + \text{Lap}\left(\frac{s}{\epsilon}\right)
其中，s是f的敏感度，\text{Lap}(S)表示均值为0、放缩系数为S的拉普拉斯分布采样。下面同样给出拉普拉斯分布的概率密度函数吧
f(x|\mu,S)=\frac{1}{2S}\exp\left(-\frac{|x-\mu|}{S}\right)
而在 python 中有
np.random.laplace(loc, scale) # 生成 laplace 分布
# loc 就是 \mu，scale 就是 S 放缩系数
差分隐私的性质
介绍
差分隐私有三个重要的性质
- 串行组合性：如果F_1(x)满足\epsilon_1-差分隐私，F_2(x)满足\epsilon_2-差分隐私，则同时发布两个结果的机制G(x)=(F_1(x),F_2(x))满足(\epsilon_1+\epsilon_2)-差分隐私。
- 并行组合性：将数据集分成k份，然后在每一份上面应用差分隐私，那么就满足\max\limits_{i}\epsilon_i-差分隐私
- 后处理性：对于差分隐私出来的结果，对这个结果应用于另一个函数出来的结果也都是具有\epsilon-差分隐私的。
敏感度
介绍
我们上面提到了一个拉普拉斯机制，如下所示
F(x)=f(x)+\text{Lap}\left(\frac{s}{\epsilon}\right)
其中，s就被称为是f的敏感度，假设定义f:\mathcal{D}\rightarrow\mathbb{R}，其中\mathcal{D}是数据集，\mathbb{R}是实数域。那么可以定义f全局敏感度为：
\text{GS}(f)=\max\limits_{x,x':d(x,x')\leq 1}\left|f(x)-f(x')\right|
其中d(x,x')表示两个数据集x,x'之间的距离，距离小于1称之为邻近数据集，这个公式的含义如下：
全局敏感度：邻近数据集经过差分隐私函数之后，输出最大差\text{GS}(f)。
距离与敏感度
-
如果x'是x添加或者删除一行得到的，那么距离为1。如果是修改一行得到的，那么距离是2。
-
敏感度就是，自变量变化1，因变量变化多少就是敏感度了。比如：
\begin{align} f(x)=x\quad&dx=1, df(x)=1\\ f(x)=nx\quad&dx=1, df(x)=n\\ f(x)=x^2\quad&dx=1,df(x)=2x(\text{Unkown}) \end{align}
第一个的敏感度为1，第二个的敏感度为n，第三个的敏感度跟x有关，无从得知。
不同的查询敏感度
- 计数问询：比如数据集中有多少人，敏感度为1，因为增加一个人，问询结果只会增加1。
- 求和问询：比如数据集中人的分数总和为多少，敏感度是未知的，增加一个人，分数增加是根据这个人的分数来定的。如果满分是100的话，那么可以认为敏感度为100，因为不可能超过100的变化量。因此认为，求和问询如果不存在上下界，那么称为无界敏感度，否则敏感度为上下界的差。
- 均值问询：比如数据集中人的分数均值是多少，这个其实是计数问询+求和问询的结果，两者做除法就能得到。
近似差分隐私
介绍
结合上述说的差分隐私，给出一个近似差分隐私的公式：
\Pr[F(x)=S]\leq \text{e}^{\epsilon}\Pr[F(x')=S]+\delta
跟差分隐私相比，多了一个\delta，称之为(\epsilon,\delta)-差分隐私。\delta的含义表示不满足此近似差分隐私定义的“失败概率”，有(1-\delta)的概率获得等价于纯粹差分隐私的隐私保护程度，有\delta的概率不满足隐私参数为\epsilon的纯粹差分隐私。也就是说：
- 满足\frac{\Pr[F(x)=S]}{\Pr[F(x')=S]}\leq\text{e}^{\epsilon}的概率为(1-\delta)
- 不满足上述的概率为\delta
泄露隐私的概率为\delta，所以\delta一般设置的很小，一般\delta\leq\frac{1}{n^2}，其中n是表示数据集的大小。
性质
与纯粹差分隐私一样，它也满足串行组合，并行组合和后处理性。
串行组合性质：如果F_1(x)满足(\epsilon_1,\delta_1)-差分隐私，F_2(x)满足(\epsilon_2,\delta_2)-差分隐私，那么G(x)=(F_1(x),F_2(x))满足(\epsilon_1+\epsilon_2,\delta_1+\delta_2)-差分隐私。
高斯机制
高斯机制使用高斯噪声，其无法满足纯粹\epsilon-差分隐私，但是可以满足(\epsilon,\delta)-差分隐私。用下述定义来表示高斯噪声
F(x)=f(x)+\mathcal{N}(\sigma^2)\\
\sigma^2=\frac{2s^2\log(1.25/\delta)}{\epsilon^2}
其中，s是f的敏感度，\mathcal{N}(\sigma^2)表示均值为0，方差为\sigma^2的高斯（正态）分布采样结果。高斯机制有两个缺点，一是需要使用宽松的(\epsilon,\delta)-差分隐私，二是准确性不如拉普拉斯，其应用在后面再讨论。
向量值函数
前面提到的函数都是将一个数据集映射到一个值，即D\rightarrow\mathbb{R}，拉普拉斯机制和高斯机制都可以扩展到将一个数据集映射到一个向量，即D\rightarrow\mathbb{R}^n的向量值函数的形式，鉴于此，重新定义了距离和敏感度等。
L1和L2范数
下面是两个范数的定义
\|A\|_1 = \sum\|a_i\|\\
\|A\|_2 = \sqrt{\sum a_i^2}
同样地，定义敏感度为
\text{GS}_1(f) = \max\limits_{d(x,x')\leq1}\|f(x)-f(x')\|_1\\
\text{GS}_2(f) = \max\limits_{d(x,x')\leq1}\|f(x)-f(x')\|_2
拉普拉斯机制需要使用L1敏感度，而高斯机制既可以使用L1敏感度也可以使用L2敏感度。
局部敏感度
介绍
局部敏感度的意思是，我们讨论敏感度，应该具体到某个数据集。换句话说，由于数据集的某些属性不同（比如数据集的大小），会影响邻近数据集的之间的最大差值，下面给出其数学定义
\text{LS}(f,x)=\max\limits_{x':d(x,x')\leq1}\left|f(x)-f(x')\right|
下面举一个例子，一个均值问询的例子，假设数据集大小为n，上界为u，我们在这个数据集增加一个新的数据，且这个数据大小就为u，得到了新的数据集，而且新数据集还是原来数据集的邻近数据集。
f(x) = \frac{\sum_{i=1}^nx_i}{n}\\
f(x')=\frac{\sum_{i=1}^nx_i+u}{n+1}\\
\begin{align}
\left|f(x')-f(x)\right|&=\left|\frac{\sum_{i=1}^nx_i+u}{n+1}-\frac{\sum_{i=1}^nx_i}{n}\right|\\
&\leq\left|\frac{\sum_{i=1}^nx_i+u}{n+1}-\frac{\sum_{i=1}^nx_i}{n+1}\right|\\
&=\left|\frac{u}{n+1}\right|\\
\end{align}
此时，局部敏感度与数据集的属性有关了，依赖于具体的数据集了。
局部敏感度实现差分隐私
下面介绍三种使用局部敏感度实现差分隐私的方案
建议-测试-发布（propose-test-release）
概括：
- 建议一个局部敏感度边界b
- 如果 D(f,x,b)+\text{Lap}(\frac{1}{\epsilon})<\log(2/\delta)/2\epsilon，拒绝
- 否则，返回f(x)+\text{Lap}(\frac{b}{\epsilon})
平滑敏感度（smooth sensitivity）
概括：不适用敏感度本身，使用局部敏感度的平滑近似值来校准噪声
- 设置\beta=\frac{\epsilon}{2\log(2/\delta)}
- 令S=\max_{k=1,\dots,n}e^{-\beta k}A(f,x,k)
- 发布f(x)+\text{Lap}(\frac{2S}{\epsilon})
采样聚合（sample and aggregate）
- 将数据集X\in D拆分成k个不相交的数据块x_1,\dots,x_k，u,l分别为上下界
- 计算每个数据块的裁剪回复值a_i=\max(l,\min(u,f(x_i)))，（这一步就是为了把f(x_i)的输出限定在l,u之间）
- 计算平均回复值并增加噪声A=\left(\frac{1}{k}\sum_{i=1}^ka_i\right)+\text{Lap}(\frac{u-l}{k\epsilon})
差分隐私变体
KL散度
相对熵又被称为KL散度，用来衡量两个分布间差异的非对称性度量。设P(x),Q(x)为两个分布，下式分别为离散和连续情况下，P与Q之间的分布差异。
\begin{align}
\text{KL}(P\|Q)&=\sum P(x)\log\frac{P(x)}{Q(x)}\quad或,\\
&=\int P(x)\log\frac{P(x)}{Q(x)}
\end{align}
KL散度是非负的，当且仅当P=Q时，才取0，并且\text{KL}(P\|Q)\neq\text{KL}(Q\|P)，KL越大表示两个分布差异越大。
在差分隐私中，可以用最大散度可以来描述差分隐私定义是否可行，最大散度就是KL散度的最坏情况，即KL值最大的情况。
我们还记得差分隐私定义是：\frac{\Pr[F(x)=S]}{\Pr[F(x')=S]}\leq e^\epsilon\rightarrow\log\frac{\Pr[F(x)=S]}{\Pr[F(x')=S]}\leq \epsilon。最大散度定义如下：
D_\infty(Y\|Z)=\max\left[\log\frac{\Pr[Y\in S]}{\Pr[Z\in S]}\right]
只需要D_\infty(F(x)\|F(x'))\leq\epsilon，我们就可以说，F满足\epsilon-差分隐私。
瑞丽散度
瑞丽散度也是一个描述差分隐私是否可行的一个工具。概率分布P,Q的\alpha阶瑞丽散度定义为：
D_\alpha(P\|Q)=\frac{1}{\alpha-1}\log E_{x\sim Q}\left(\frac{P(x)}{Q(x)}\right)^\alpha
瑞丽差分隐私要求F(x),F(x')的\alpha阶瑞丽散度不超过\overline\epsilon，称F满足(\alpha,\overline\epsilon)-差分隐私，如下所示：
D_\alpha(F(x)\|F(x'))\leq\overline\epsilon
如果一个机制满足瑞丽差分隐私，那么一定也满足(\epsilon,\delta)-差分隐私，其中有\delta>0,\epsilon=\overline\epsilon+\log(1/\delta)/(\alpha-1)，一般取\delta\leq1/n^2
零集中差分隐私
零集中是瑞丽的一个变体
D_\alpha(F(x)\|F(x'))\leq\rho\alpha
称为满足\rho-差分隐私，\alpha\in(1,+\infty)，同样此时\epsilon=\rho+2\sqrt{\rho\log(1/\delta)}
指数机制
介绍
前面的高斯机制和拉普拉斯机制，都是在结果上面做差分隐私（即加噪声），而指数机制是在过程上面做差分隐私。
指数机制是从备选回复中选出最佳回复的同时，保证回复过程满足差分隐私。指数机制满足\epsilon-差分隐私，过程如下：
- 备选集合：分析者选择一个备选回复集合\mathcal{R}
- 评分函数：分析者指定一个全局敏感度为\Delta u的评分函数u:\mathcal{D}\times\mathcal{R}\rightarrow\mathbb{R}
- 输出：指数机制输出r\in\mathcal{R}，各个回复的输出概率与\exp\left(\frac{\epsilon u(x,r)}{2\Delta u}\right)成正比
指数机制的输出一定是备选回复集合\mathcal{R}的成员，在输出结果一定属于一个有限集合的情况下非常有用。
应用场景：假设获取了班级所有人空闲的日期，来制定一个出行日期，直接在出行日期或者在空闲日期上面加噪声是没什么用的，一来是可能把周五变成周六，二来是周5.3是没有任何意义的。
下面概括指数机制的特点：
- 无论\mathcal{R}中有多少个备选输出，隐私消耗量均为\epsilon
- 既可以应用于有限集合，又可以应用于无限集合
- 指数机制代表了\epsilon-差分隐私的基本机制，选择合适的评分函数，所有\epsilon-差分隐私机制都可以用指数机制来定义
稀疏向量技术
本地差分隐私
随机响应机制
References
- [1] k-匿名性