要理解差分隐私，必须知道差分在数学中代表什么

​ 差分（difference）又名差分函数或差分运算，差分的结果反映了离散量之间的一种变化，是研究离散数学的一种工具。它将原函数f(x) 映射到f(x+a)-f(x+b) 。差分运算，相应于微分运算，是微积分中重要的一个概念。总而言之，差分对应离散，微分对应连续。差分又分为前向差分、向后差分及中心差分三种。

通过差分，将离散数值构建起相关关系，隐瞒实际想要表达的数值

​ 等差数列：a1 a2 a3……an……，其中an+1= an + d（ n = 1,2,…n ）d为常数，称为公差， 即 d = an+1 -an , 这就是一个差分, 通常用D(an) = an+1- an来表示，于是有D(an)= d , 这是一个最简单形式的差分方程。

前向差分

函数的前向差分通常简称为函数的差分。对于函数f(x)，如果在等距节点：
$$
x_k = x_0 + k * h, (k = 0, 1, …, n)
\
\triangle f(x_k) = f(x_{k+1}) - f(x_k)
$$
则称$ \triangle f(x)$，函数在每个小区间上的增量$ y(k+1) - y(k)$为$f(x)$的一阶前向差分。在微积分学中的有限差分（finite differences），前向差分通常是微分在离散的函数中的等效运算。差分方程的解法也与微分方程的解法相似。当是多项式时，前向差分为Delta算子，一种线性算子。前向差分会将多项式阶数降低1。

向后差分

对于函数$\ f(x_k)$，一阶向后差分为：
$$
\triangle f(x_k) = f(x_k) - f(x_{k-1})
$$
注：差分方程：difference equations

中心差分

对于函数$\ f(x_k)$，一阶中心差分为：
$$
\triangle f(x_k) = \frac{1}{2}(f(x_{k+1}) - f(x_{k-1}))
$$

差分的阶

二阶差分

逆差分

应用

泰勒公式通过差分公式求近似值

差分隐私

​ 差分隐私（英语：differential privacy）是密码学中的一种手段，旨在提供一种当从统计数据库查询时，最大化数据查询的准确性，同时最大限度减少识别其记录的机会。

​ 假设 ε 是一个正实数，A是一个随机算法，它将数据集作为输入（表示信任方拥有的数据）。imA表示A的映射。对于在非单个元素（即，一个人的数据）的所有数据集D1和D2以及imA的所有子集S，算法A是 ε -差分隐私，其中概率取决于算法的随机性。
$$
Pr[A(D_1) \in S] \le e^ε \times Pr[A(D_2) \in S]
$$
例如：假设我们有一个医疗记录数据库 D1 在那里每条记录是一对 (名字, x), 其中 X 是一个布尔值表示一个人是否痪有糖尿病。例如:

假设：

1. 一个恶意用户 (通常被称为攻击者) 想知道Chandler是否有糖尿病。

2. 他知道Chandler在数据库的哪一行。

3. 攻击者只能使用特定形式的查询Qi返回数据库中前i行中第一列 X 的部分总和。

​ 攻击者为了获取Chandler是否有糖尿病的信息，只需要执行两个查询 Q5（D1）和Q4（D1），分别计算前五行和前四行的总和，然后计算两个查询的差别。

​ 在本例中Q5（D1）=3，Q4（D1）=2，差是1。攻击者在知道Chandler在第5行的情况下，就会知道他的糖尿病状况是1（有糖尿病）。

这个例子显示了即使在没有明确查询特定个人信息的情况下, 个人信息如何被泄露。

​ 继续这个例子，如果我们用（Chandler，0）代替（Chandler，1）构造D2，那么这个恶意攻击者将能够通过计算每个数据集的Q5-Q4来区分D2和D1。 如果攻击者被要求通过ε-差分隐私算法接收Qi值，对于足够小的ε，则他将不能区分这两个数据集。

我们之前提到过，保护数据隐私的方法就是将原有的单一查询结果概率化。Laplace噪声就给我们提供了一个很好的概率化的方法。举个简单的例子，假如查询为“查询数据集中年龄小于20的人数”，并且查询结果为“50”：在传统模式下，输出就是50；在差分隐私模式下，会以比较大概率输出50左右的结果，也会以比较小的概率输出和50差别比较大的结果。但是，我们需要保证输出的期望为50（保证数据有效性）。

——DP-拉普拉斯机制 - 知乎 (zhihu.com)

灵敏度

用于评判添加了噪音的输出与原属于的差距是否足够大，大到基本能够满足混淆adversary对得到数据进行评估的可能性。

$$
\triangle f = \max_{x,y \in \mathbb{N}^{|\chi|}, ||x-y||_1 = 1} ||f(x) - f(y)||_1
$$

差分隐私的其他概念

​ 对很多应用而言, 差分隐私被认为过于严格, 因此建议了许多被弱化的版本。这些包括 (ε, δ)-差分隐私, 随机差分隐私, 以及特定标度的隐私。

差分隐私机制

拉普拉斯机制

给定查询函数$ f: \mathbb{N}^{\chi} \to \mathbb{R}^{k} $ ，拉普拉斯机制可以表示为：
$$
M_L(x,f(·), ε) = f(x) + (Y_1, Y_2, …, Y_k)
$$
其中，$ Y_i $是独立同分布的变量，为$Lap(\frac{\triangle f}{ε} )$ 。

验证

假设 $p_x$ 表示$M_L(x,f,ε)$ 的pdf（probability density function）， $p_y$表示 $M_L(y,f,ε)$的pdf，则对于某个输出$\mathcal{z}$，我们有：
$$
\begin{align*}
\frac{p_x(\mathcal{z})}{p_y({\mathcal{z}})} &= \prod_{i=1}^{k} \frac{exp(-\frac{ε|f(x)_i - \mathcal{z}_i|}{\triangle f})}{exp(-\frac{ε|f(y)_i - \mathcal{z}i|}{\triangle f})} \
&=\prod{i=1}^{k}exp \frac{ε(|f(y)_i - \mathcal{z}_i| - |f(x)_i - \mathcal{z}i|)}{\triangle f} \
&\le \prod{i=1}^{k}exp (\frac{ε(|f(x)_i - f(y)_i|)}{\triangle f}) \
&= exp(\frac{ε·||f(x) - f(y)||_1}{\triangle f})\
&\le exp(ε)
\end{align*}
$$

Netflix奖

医疗数据库事件

元数据与流动数据库