本文将介绍差分隐私及其相关概念。

差分隐私的承诺

一个有趣的例子：

医学数据库可能会告诉我们，吸烟会导致癌症，影响保险公司对吸烟者长期医疗费用的看法。吸烟者受到分析的伤害了吗？如果保险公司知道他吸烟，他的保险费可能会上涨。他可能也会得到帮助。但保险公司学习他的健康风险，使他进入戒烟计划。吸烟者的隐私被侵犯了吗？当然，研究结束后对他的了解比以前更多，但他的信息是不是“泄露”了？差分隐私将认为它不是，理由是对吸烟者的影响是相同的独立于他是否在研究中。是这项研究得出的结论影响了吸烟者，而不是他在数据集中的存在与否影响了实验得出的结论。

差分隐私解决了一个问题，即分析人员通过数据集学习整体信息的同时（趋势、统计信息），无法获取个人的详细信息。

对于给定的计算任务 $T$ 和给定的 $\varepsilon$ 值，将有许多不同的私有算法以 $\varepsilon$ 方式实现 $T$ 。有些算法会比其他算法更准确。当 $\varepsilon$ 很小时，很难为任务 $T$ 找到一个高精度的 $\varepsilon$ -差分隐私算法，就像为一个特定的计算任务找到一个数值稳定的算法一样。

隐私保护的数据分析

数据不能完全匿名并且仍然有用

一般来说，数据越丰富，就越有趣和有用。这就产生了“匿名化”和“删除可识别个人信息”的概念，这些概念希望部分数据记录可以被掩盖，其余部分可以发布并用于分析。

然而，由于数据的丰富性使得“个人”数据属性可能与其他领域的数据属性相重合，比如邮政编码、出生日期和性别的组合，甚至三个电影的名字和一个独立的人观看这些电影的大致日期。这种“命名”功能可用于联动攻击，以将不同数据集中的“匿名”记录与非匿名记录进行匹配。有如下两个事例：

1.通过将匿名医疗遭遇数据与（公开提供的）选民登记记录相匹配，确定了马萨丘塞特政府的医疗记录。
2.通过与互联网电影数据库（IMDB）的链接，确定了 Netflix 用户，其观看历史记录包含在 Netflix 发布的匿名电影记录集合中，作为推荐竞赛的训练数据。

重标识“匿名”记录并非唯一风险

“匿名”数据记录的重新标识显然是不可取的，这不仅是因为重新标识本身（这肯定揭示了数据集中的成员身份），而且还因为记录可能包含损害信息，如果它与个人相关联，则可能会造成损害。在给定日期从特定紧急护理中心收集的医疗遭遇记录可能只列出少量不同的投诉或诊断。邻居在相关日期访问设施的附加信息给出了邻居病情的一系列可能诊断结果。可能无法将特定记录与邻居匹配这一事实为邻居提供了最低限度的隐私保护。

长期的事实并不“好”

如果一个数据主体随着时间的推移而被跟踪，那么揭露数据个体长期的行为（例如购买面包）可能会有问题。举个例子，假设某人，他年复一年地定期买面包，直到突然转向很少买面包。一位分析师可能会得出结论，某人很可能被诊断为2型糖尿病。分析员可能是正确的，也可能是不正确的；不管怎样，某人的隐私都会受到伤害。

差分隐私的公式化

定义1（概率单纯形），给定一个离散集 $B$ ，将 $B$ 上的概率单纯形（是一个数学空间，其中的每个点代表有限个互斥事件之间的概率分布），表示为 $\Delta(B)$ ，其定义为：

\Delta(B)=\{x\in R^{\vert B \vert}:\ x_i \ge 0\ for\ all\ o\ and\ \Sigma_{i=1}^{\vert B\vert}x_i=1 \}

可以理解为将数据库中的数据集映射到各个离散状态集合 $B$ 中

定义2（数据库之间距离），将数据库的 $l_1$ 范数距离表示为 $\vert \vert x\vert \vert_1$ ，其定义为

$\vert \vert x\vert \vert_1=\Sigma_{i=1}^{\vert \chi \vert} \vert x_i\vert

数据库 $x,y$ 之间的距离为 $\vert \vert x-y \vert \vert_1$

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