1. 差分隐私的承诺

“差分隐私” 描述了数据持有者或管理者对数据主体的承诺：“无论是否存在其他研究、数据集或者信息源，您都不会因数据被用于任何研究或分析而受到不利影响”。理想情况下，满足差分隐私的数据库机制允许我 们对广泛的机密数据，在无需借助于数据净室 (data clean rooms)、数据使用协议、数据保护计划或受限视图的情况下，进行精准分析。尽管如此，数据的可用性最终还是会受到影响：信息恢复的基本规律(Foundamental Law of Information Recovery) 指出，对太多问题作出过于精准的回答会以惊人的方式摧毁隐私¹。差分隐私算法研究的目标是竭尽所能地延缓这一必然结果。

差分隐私解决了这样一个“悖论”：在获取有效群体信息的同时不暴露个体信息。一个医学数据库可能会告诉我们吸烟致癌，从而影响保险公司对某个吸烟者长期医疗费用的评估。那么这一分析是否损害到了该吸烟者的利益？也许是的——如果保险公司知道他抽烟，他的保费可能会因此上涨。但他也可能因此获益——在了解了自身存在的健康风险后，他启动了戒烟计划。那吸烟者的隐私是否受到了损害？可以肯定的是，经过分析后对他的了解比分析前更多，但他的信息被 “泄露” 了吗？差分隐私认为事实并非如此，根本原因在于，无论该吸烟者是否参与了此项调研，此分析对他的影响都是相同的。影响吸烟者的是研究中得出的结论，而与他/她是否出现在该研究数据集中无关。

差分隐私确保了无论任何个体加入或退出数据集都会得出相同的结论，例如，吸烟致癌。具体来讲，它确保的是任意输出序列 (对查询的响应) 出现的可能性“基本上”独立于任何个体的存在与否。这里，结果的概率被隐私机制 (由数据管理员控制) 采取的随机选择控制，而术语 “基本上” 被参数 ϵ 约束。较小的 ϵ 会产生更好的隐私保护效果 (和不太准确的响应)。

差分隐私是一种定义，而不是一种算法。对一个给定的计算任务 T 和一个定值 ϵ，有许多差分隐私算法可以通过满足 ϵ-差分隐私 的方式实现该计算任务 T。其中一些算法比其他算法精度更高。当 ϵ 很小时，为任务 T 找到一个高精度的 ϵ-差分隐私 算法很难，就好比为特定的计算任务找到一个数值稳定的算法一样困难。