差分隐私定义
当一个算法 $ \mathcal{A} $ 满足 $ \epsilon-DP(\epsilon > 0) $，当且仅当对任意两个仅相差一条数据的数据集 $ D $ 和 $ D \prime $，有
$$ \forall T \subseteq Range(\mathcal{A}): Pr[\mathcal{A}(D) \in T] = e^\epsilon Pr[\mathcal{A}(D \prime) \in T] $$
其中 $ Range(\mathcal{A}) $ 表示算法 $ \mathcal{A} $ 所有可能的输出。上式也可等价写为如下形式：
$$ \forall t \in Range(\mathcal{A}): \frac{Pr[\mathcal{A}(D) = t]}{Pr[\mathcal{A}(D \prime) = t]} \leq e^\epsilon $$
相邻数据集 Neighboring Dataset
两个相差一条数据的数据集互为相互数据集。
对于相邻数据集：
- 如果它们包含的数据数量相同，其中一个数据集可以由另一个数据集替换一条数据得到，则它适用于 Bounded DP
- 如果它们包含的数据数量相差1，其中一个数据集可以由另一个数据集增加/减少一条数据得到，则它适用于 Unbounded DP
注意：所有满足 $ \epsilon-unbounded DP $ 的算法都满足 $ (2\epsilon)-bounded DP $，因为用一个元素替换另一个元素可以通过删除一个元素然后添加另一个元素来实现。
差分隐私的性质
后处理 Post Processing
对一符合 $ \epsilon-DP $ 的算法 $ \mathcal{A} $，对任意算法 $ \mathcal{B} $，$ \mathcal{B}(\mathcal{A}) $ 满足 $ \epsilon-DP $，即对数据进行后处理不会影响 DP 提供的隐私性。
顺序组成 Sequential Composition
有一符合 $ \epsilon_1-DP $ 的算法 $ \mathcal{A}_1 $ 和一符合 $ \epsilon_2-DP $ 的算法 $ \mathcal{A}_2 $，则 $ \mathcal{A} = \mathcal{A}_2(\mathcal{A_1(D)}, D) $ 符合 $ (\epsilon_1 + \epsilon_2)-DP $
一般化表示形式如下：对满足 $ \epsilon_i-DP $ 的算法 $ \mathcal{A}_i $，有算法 $ t = \langle t_1, t_2, \dots, t_k \rangle $ 满足 $ (\sum_{i=1}^k \epsilon_i)-DP $，其中 $ t_1 = \mathcal{A}_1(D), t_1 = \mathcal{A}_2(t_1, D), \dots, t_k = \mathcal{A}_k(\langle t_1, t_2, \dots, t_{k - 1} \rangle, D) $
平行组合 Parallel Composition
将数据集 $ D $ 分为 $ k $ 部分 $ D_1, D_2, \dots, D_k $，有算法 $ \mathcal{A}_i $ 符合 $ \epsilon_i-DP $，则 $ \mathcal{A}_1(D_k), \mathcal{A}_2(D_k), \dots, \mathcal{A}_k(D_k) $ 符合 $ max_{i \in [1, \dots, k]}(\epsilon_i)-DP $
注意：在 bounded DP 下，平行组合不成立
凸度 Convexity
有 $ k $ 个符合 $ \epsilon-DP $ 的机制，取 $ p_1, p_2, \dots, p_k \in [0, 1] $，且 $ \sum_{i=1}^k p_i = 1 $，则有机制 $ \mathcal{A} = p_1 \mathcal{A_1} + p_2 \mathcal{A_2} + \dots + p_k \mathcal{A_k} $ 符合 $ \epsilon-DP $
拉普拉斯机制 Laplace Mechanism
全局敏感度 Global sensitivity
我们使用 $ D \simeq D^\prime $ 来表示 $ D $ 和 $ D^\prime $ 为相似数据集，$ \Delta_f $ 表示函数 $ f $ 的全局敏感度，则标量的全局敏感度 $ \Delta_f=\max _{D \simeq D^{\prime}}\left|f(D)-f\left(D^{\prime}\right)\right| $，向量的全局敏感度为 $ \Delta_f=\max _{D \simeq D^{\prime}}\left\|f(D)-f\left(D^{\prime}\right)\right\|_1 $
标量形式
要让一个输出标量的函数 $ f $ 符合 $ \epsilon-DP $，我们可以设一个函数 $ \tilde{f}(D) = f(D) + X $，其中 $ X $ 为一个从某分布随机取到的值，对于 $ X $ 所属分布，我们需要他的均值为 0，这样 $ \tilde{f}(D) $ 就是 $ f(D) $ 的无偏估计了，同时我们还需要满足：
$$ \forall t, \frac{\operatorname{Pr}[\tilde{f}(D)=t]}{\operatorname{Pr}\left[\tilde{f}\left(D^{\prime}\right)=t\right]}=\frac{\operatorname{Pr}[f(D)+X=t]}{\operatorname{Pr}\left[f\left(D^{\prime}\right)+X^{\prime}=t\right]}=\frac{\operatorname{Pr}[X=t-f(D)]}{\operatorname{Pr}\left[X^{\prime}=t-f\left(D^{\prime}\right)\right]} \leq e^\epsilon $$
其中 $ X $ 和 $ X \prime $ 都来自同一分布。
我们设 $ d = f(D) - \tilde{f}(D \prime) $，我们需要保证 $ \forall x, \frac{\operatorname{Pr}[X=x]}{\operatorname{Pr}\left[X^{\prime}=x+d\right]} \leq e^\epsilon $，并确保 $ \forall d \leq \Delta_f $，也就是说噪声所属的分布应当满足如下性质：如果在 x 轴上移动不超过 $ \Delta_f $ 个单位，概率的变化应该不超过 $ e_\epsilon $，即如果在 x 轴上移动不超过一个单位，则概率的变化不应超过 $ e^\frac{\epsilon}{\Delta_f} $
满足上述要求的分布为拉普拉斯分布 $ Lap(\frac{\Delta_f}{\epsilon}) $，$ Pr[Lap(\beta) = x] = \frac{1}{2\beta}e^{-\frac{|x|}{\beta}} $，$ \frac{\operatorname{Pr}[\operatorname{Lap}(\beta)=x]}{\operatorname{Pr}[\operatorname{Lap}(\beta)=x+d]} \leq e^{d / \beta} \leq e^{\Delta_f / \beta}=e^\epsilon $
对所有函数 $ f $，有拉普拉斯机制 $ \mathcal{A}_f(D) = f(D) + Lap(\frac{\Delta_f}{\epsilon}) $ 符合 $ \epsilon-DP $
向量形式
对所有函数 $ f $，有拉普拉斯机制 $ \mathcal{A}_f(D) = f(D) + \langle X_1, X_2, \dots, X_k \rangle) $ 符合 $ \epsilon-DP $，其中 $ X_1, X_2, \dots, X_k $ 取自 $ Lap(\frac{\Delta_f}{\epsilon}) $
指数机制 Exponential Mechanism
拉普拉斯机制只适用于数值输出，并不适用于非数值输出（如分类等），而指数机制都适用
设 $ O $ 为包含所有可能输出的集合，在 $ O $ 中的一些值会比其他值更可取（如想输出出现次数最多的项则它比其他的输出更可取），我们使用效用函数（quality function） $ q: (\mathbb(D) \times O) \rightarrow \mathbb{R} $ 来衡量一个值的重要性，其中 $ \mathbb{D} $ 表示所有数据集的集合，$ \mathbb{R} $ 为实数集。
对任何效用函数 $ q: (\mathbb(D) \times O) \rightarrow \mathbb{R} $，指数机制 $ \mathcal{M}^\epsilon_q(D) $ 的输出 $ o \in O $ 与 $ exp(\frac{\epsilon q(D, o)}{2\Delta_q}) $ 成正比，其中 $ \Delta q=\max _{\forall o, D \simeq D^{\prime}}\left|q(D, o)-q\left(D^{\prime}, o\right)\right| $ 为函数 $ q $ 的敏感性。即
$$ \operatorname{Pr}\left[\mathcal{M}_q^\epsilon(D)=o\right]=\frac{\exp \left(\frac{\epsilon q(D, o)}{2 \Delta q}\right)}{\sum_{o^{\prime} \in O} \exp \left(\frac{\epsilon q\left(D, o^{\prime}\right)}{2 \Delta q}\right)} $$
（效用函数）单调情形
一般当效用函数是基于满足某种条件的记录数进行计数时，就会出现效用函数是单调函数的情况。在这种情况下，指数机制的输出不再与 $ exp(\frac{\epsilon q(D, o)}{2\Delta_q}) $ 成正比，而是和 $ exp(\frac{\epsilon q(D, o)}{\Delta_q}) $ 成正比。