一、差分隐私承诺

差分隐私 描述了数据持有者对数据主体的承诺：“无论您将数据用于任何研究或分析，都不会受到不利影响或其他影响。”

1.1 隐私保护数据的分析（存在问题）

数据不能完全匿名并且仍然有用（背景知识）
重标识“匿名”记录并非唯一风险（匿名提供的隐私保护限度不高）
不具有保护性的大数据集查询（差分攻击）
查询审查存在的问题（审核、防止差分攻击语句是不现实的）
“不安全”的摘要统计
普适结论（长期的事实）并不“好”
“少数人”原则（为大多数用户提供隐私保护，而放弃或损害了少数用户的隐私）

二、基本术语

2.1 计算模型

假设存在一个可信的和可信赖的数据提供者，他将个人的数据保存在数据库$D$中，通常由若干$N$行组成。数据库每一行包含单个个体的数据，而隐私目标是同时保护每个个体行，同时允许对整个数据库进行统计分析。

非交互式或离线的模型：数据提供者会一次性地生成某种对象，例如“合成数据库”、“摘要统计数据集合”或“净化数据库（经数据清洗的数据库）”。发布后，数据提供者不再扮演任何角色，原始数据可能会被销毁。

交互式或在线模型：允许数据分析员自适应地询问查询，根据观察到的对先前查询的响应来决定下一个查询的位置。

差分隐私机制是一种算法。

输入：一个数据库或一组全体数据类型 $\mathcal{X}$（所有可能的数据库行）、随机位和一组查询（可选）

输出：字符串。

希望可以对输出字符串进行解码，以便对查询产生相对准确的答案。如果没有出现任何查询，那么我们就处于非交互式的情况下，希望输出字符串可以被解释为将来的查询提供答案。

在某些情况下，我们可能要求输出字符串是合成数据库。这种合成数据库是由所有可能的数据库行（ $\mathcal{X}$）中得到的多集合组成。这种情况下的解码方法是对合成数据库进行查询，然后应用一些简单的变换，如缩放因子的乘法，使其近似于查询的真实答案。

2.2 定义隐私数据分析

隐私：要求分析人员在分析完成后对数据集中的任何个人的了解不超过分析开始前的了解。这一目标的形式化也是很自然的，要求对手对个人的前后认知（即访问数据库之前和之后的认知）不应该“差别过多”，或者对数据库的访问不应该“过多”地改变对手对任何个人的认知。

可用性

2.3 形式化差分隐私

随机响应技术

定义2.1（概率单纯形）给定一个离散集$B$，将$B$上的概率单纯形，表示为$\Delta(B)$ ，其定义为：

$\Delta (B)=\{x\in \mathbb{R}^{|B|}:x_i\geq0\space for\space all \space i\space and \space \sum_{i=1}^{|B|}x_i=1\}$

定义2.2 （随机化算法）具有域$A$和离散范围$B$的随机算法$\mathcal{M}$与映射$M:A \to \Delta(B)$相关联。在输入$a∈A$时，算法$\mathcal{M}$以概率$M(a)_b$输出$\mathcal{M}(a)=b$ $(b∈B)$。概率空间在算法$\mathcal{M}$的硬币翻转上（意思是算法$\mathcal{M}$随机翻转随机串的比特位，形成随机性）。

定义2.3 （数据库之间距离）将数据库的$\ell_1$范数距离表示为$\Vert x\Vert _1$其定义为:

$\Vert x\Vert _1=\sum_{i=1}^{|\mathcal{X}|}|x_i|$

数据库$x$和$y$之间的$\ell_1$距离为$\Vert x-y\Vert _1$。$\Vert x\Vert _1$是衡量数据库$x$的大小（也就是说，数据库$x$包含的记录数），而$\Vert x-y\Vert _1$表示数据库$x$和$y$之间相差多少条记录。我们称这种记录相差为1的数据库为相邻数据集。

注解：数据库$x$视为来自全集$\mathcal{X}$的记录的集合。用它们的直方图表示数据库通常会很方便：$x \in \mathbb{N}^{|\mathcal{X}|}$，其中每个项$x_i$表示数据库$x$中类型$i\in\mathcal{X}$元素的数量。

定义2.4 （差分隐私）对于所有的$\mathcal{S} \subseteq Range(\mathcal{M})$且所有的$x,y\in \mathbb{N}^{|\mathcal{X}|}$有$\Vert x-y\Vert _1 \leq 1$，如果满足下列关系：

$Pr[\mathcal{M}(x)\in \mathcal{S}] \leq exp(\varepsilon)Pr[\mathcal{M}(y)\in \mathcal{S}]+\delta$

则将这个域在$\mathbb{N}^{|\mathcal{X}|}$的随机算法$\mathcal{M}$称为$(\varepsilon,\delta)$差分隐私（ $(\varepsilon,\delta)$- Differentially private）。其中概率空间在算法$\mathcal{M}$的硬币翻转上。特别的，如果$\delta=0$，则将$\mathcal{M}$称为$\varepsilon$差分隐私(即$\varepsilon \text{-} Differentially \ private$)。

机制质量（隐私损失）：

$\mathcal{L}_{\mathcal{M}(x)||\mathcal{M}(y)}^{(\xi)}=ln(\frac{Pr[\mathcal{M}(x)=\xi]}{Pr[\mathcal{M}(y)=\xi]})$

$(\varepsilon,\delta)$差分隐私确保对于所有相邻的$x$、$y$，隐私损失的绝对值小于等于$\varepsilon$的概率至少为$1-\delta$。

命题 2.1 （后处理）令$\mathcal{M}: \mathbb{N}^{|\mathcal{X}|} \to R$是$(\varepsilon,\delta)$- 差分隐私随机算法。令$f:R \to R’$为任意随机映射。则$f \circ \mathcal{M}: \mathbb{N}^{|\mathcal{X}|} \to R’$是$(\varepsilon,\delta)$- 差分隐私。

定理2.2 任意一个大小为$k$的群体，这个群体的机制$\mathcal{M}$是$(\varepsilon,0)$- 差分隐私，则这个机制$\mathcal{M}$会变成 $(k\varepsilon,0)$- 差分隐私。也就是说，对于所有$\Vert x-y\Vert _1 \leq k$和所有$\mathcal{S} \subseteq Range(\mathcal{M})$有:

$Pr[\mathcal{M}(x)\in\mathcal{S}]\leq exp(k\varepsilon)Pr[\mathcal{M}(y)\in\mathcal{S}]$

概率空间在机制$\mathcal{M}$的硬币翻转上。

（个人理解：群体是由多个不同类型数据集组合形成的，群隐私是指一个隐私保护机制（查询）应用于相差多条记录的两个数据集上，对所有的这些数据集都采用机制$\mathcal{M}$，则机制$\mathcal{M}$会变成 $(k\varepsilon,0)$- 差分隐私。但群隐私与隐私参数合成相加定理不同，若$\delta\neq 0$，则大小为$k$的群体是$(k\varepsilon,ke^{(k-1)\varepsilon}\delta)$-差分隐私。合成定理可以理解为对一个数据集采用多次具有差分隐私的机制，这样得到的新机制可以参数相加）