2.3 形式化差分隐私
我们将从差分隐私的专业定义开始，然后对其进行解读。差分隐私通过特定的过程 (process) 来提供隐私保护，特别是会引入随机性。通过随机过程保护隐私的一个早期例子是随机响应 (randomized response)，这是社会科学中为收集不当或不法行为的统计信息而开发的一项技术，不当或不法行为通过是否具备属性 \(P\) 来判定。参与研究的受访者被要求根据以下步骤报告自己是否具备属性 \(P\)：
- 抛掷一枚硬币。
- 如果是反面，则如实回答。
- 如果是正面，则抛掷第二枚硬币，如果是正面则回答“是”，如果是反面则回答“否”。
该技术对“隐私”的保护来自于受访者存在合理否认任何结果的可能性；特别是，如果具备属性 \(P\) 意味着参与了非法行为，即使回答“是”也无法证明受访者有罪，因为无论受访者是否具备属性 \(P\)，他们回答“是”的概率至少有 \(1/4\)。准确性 (accuracy) 来自于对噪音生成过程（随机引入伪造的答案“是”和“否”）的理解：回答 “是” 的人数的期望等于不具备属性 \(P\) 的人数的 \(1/4\) 加上具备属性 \(P\) 的人数的 \(3/4\)。因此，如果 \(p\) 表示具备属性 \(P\) 的受访者的真实比例，则回答 “是” 的预期人数为 \((1/4)(1 − p) + (3/4)p = (1/4) + p/2\)。这样，我们可以估计 \(p\) 的值为回答 “是” 的人数的两倍再减去 \(1/2\)，即 \(2((1/4) + p/2) − 1/2\)。
随机化是至关重要的一环；更准确地说，无论现在或者将来存在什么样的辅助信息（包括其他数据库、研究、网站、线上社区、流言、报纸以及政府统计等等），任何有意义的隐私保护都必须要通过随机化才能实现。这可以通过一个简单的混合论证来证明，现在我们简述如下。为了进行反证，现假设存在一个有意义的确定性算法。“有意义”意味着对于某个查询，两个不同的数据库会产生有差异的结果。通过改变某个数据库中的一行数据，可以构造出一对数据库，它们只在特定的一行数据上有不同的取值，但在相同的查询下会产生不同的结果。如果攻击者知道这两个是几乎一样的数据库，那么他就能通过观察查询结果来推断出未知行的数据值。
因此，我们需要讨论随机算法的输入和输出空间。在本书中，我们使用的是离散概率空间。有时我们会将算法描述为从连续分布中采样，但这些情况应始终以适当的方式离散化为有限精度（参阅下文中的注解2.1）。一般而言，一个定义域为 \(A\) 和（离散）值域为 \(B\) 的随机算法，将与从 \(A\) 到 \(B\) 上的概率单纯形 (probability simplex) \(\Delta(B)\) 相关联：
定义 2.1 (概率单纯形). 对于给定的离散集合 \(B\)，其上的概率单纯形 \(\Delta(B)\) 定义如下：
\[ \Delta(B) = \{ x \in \mathbb{R}^{| B |}: x_i \ge 0 \text{ for all } i \text{ and } \sum_{i=1}^{| B |}{x_i} = 1 \} \]