差分隐私

邻接与定义 ​

设数据集 $S,S^{\prime }\in Z^m$ 只在一个位置不同，称为替换邻接并记作 $S\simeq S^{\prime }$。随机机制 $A:Z^m\to \mathcal{O}$ 是 $(\epsilon ,\delta )$-差分隐私的，若对任意相邻数据集及任意可测输出事件 $E\subseteq \mathcal{O}$，都有

$$\text{Pr}[A(S)\in E]\le e^{\epsilon }\text{Pr}[A(S^{\prime })\in E]+\delta .$$

由于邻接关系对称，同一不等式也适用于交换 $S,S^{\prime }$ 后的方向。若 $\delta =0$，称为纯 $\epsilon$-DP；$\delta >0$ 的版本称为近似 DP。概率来自机制的内部随机性，输入数据集在定义中固定，不对某个训练分布平均。DP 因而是逐相邻数据集的最坏情形保证，而不是“平均用户不容易被识别”的经验指标。

删除或增加一条记录的 unbounded adjacency 是另一种常见约定，适合“某个人是否参与数据集”的叙事；替换邻接则固定样本量，比较某条记录被另一条取代。两种约定可以在参数常数代价下转换，却不是同一个关系。定理、库接口与隐私预算必须从头到尾使用声明过的版本。

隐私损失图像 ​

若输出分布有密度，观察到输出 $o$ 时的隐私损失可写成

$$L_{S,S^{\prime }}(o)=\log \frac{p_{A(S)}(o)}{p_{A(S^{\prime })}(o)}.$$

纯 DP 要求所有可发生输出的似然比都被 $e^{\epsilon }$ 控制；近似 DP 允许总概率至多约为 $\delta$ 的坏区域越界。这个图像帮助理解定义，但正式事件不等式不要求预先选共同密度，也能覆盖离散、连续和混合输出。

$\epsilon$ 越小，相邻输入的输出分布越接近；它不是“泄漏了 $\epsilon$ bit”的直接换算。$\delta$ 也不是普通算法失败概率：它允许隐私比较在一小部分概率质量上失去纯 DP 的乘法控制，因此通常必须远小于目标人群规模的倒数，并与威胁模型共同报告。

灵敏度与 Laplace 机制 ​

对数值查询 $f:Z^m\to {\mathbb{R}}^d$，其 ${\ell }_1$ 全局灵敏度为

$${\mathrm{\Delta }}_{1}f=\underset{S\simeq S^{\prime }}{sup}\Vert f(S)-f(S^{\prime }){\Vert }_1.$$

Laplace 机制发布

$$A(S)=f(S)+Y,Y_j\stackrel{\mathrm{iid}}{\sim }\mathrm{Lap}({\mathrm{\Delta }}_{1}f/\epsilon ).$$

相邻数据集让输出密度的对数比至多为

$$\frac{\epsilon }{{\mathrm{\Delta }}_{1}f}\Vert f(S)-f(S^{\prime }){\Vert }_1\le \epsilon ,$$

因此得到纯 $\epsilon$-DP。证明依赖最坏相邻差，不是数据上观测到的平均改变量。若先查看数据再未经隐私保护地选一个更小灵敏度，选择过程本身可能泄漏信息。

例如数据是 $m$ 个 bit，发布总和 $f(S)=\sum _i{S}_i$。替换一条记录最多改变 1，因此加入尺度 $1/\epsilon$ 的 Laplace 噪声即可保护计数。发布均值时灵敏度为 $1/m$，噪声随样本量缩小；若值域不先限制在 $[0,1]$，均值查询的全局灵敏度可能无界，公式便没有可用尺度。

后处理与组合 ​

若 $A$ 满足 $(\epsilon ,\delta )$-DP，任何不再访问原数据的随机后处理 $g(A(S))$ 保持相同参数。攻击者把输出转换、筛选、与公开信息拼接，都不能让两分布比原先更可区分；但若 $g$ 再读取私有数据，它已不是后处理。

依次运行机制会累积隐私损失。最基本的自适应顺序组合把 $({\epsilon }_i,{\delta }_i)$ 相加为 $(\sum _i{\epsilon }_i,\sum _i{\delta }_i)$；高级组合、Rényi DP 或 privacy accountant 可以在额外结构下给出更紧预算。不能把每轮单独安全理解成无限轮仍用同一预算，也不能在交互结束后只挑“最好看”的一轮而忽略此前输出。

群体差异会放大参数：若两数据集相差 $k$ 条记录，可沿邻接链反复应用定义，纯 DP 的乘法因子增长为 $e^{k\epsilon }$。DP 保护单条记录的边际影响，不承诺整个群体模式、总体均值或由许多人共同决定的事实保持秘密。

模型边界 ​

中央 DP 假设可信机制接触原始数据后只发布私有输出；本地 DP 要求每位用户在发送前先随机化记录，通常为同等统计精度付出更多样本。shuffle、pan-privacy 和 continual observation 又改变观察者能看到的中间状态。只写“使用 DP”而不说明信任边界，无法判断定义覆盖了数据库、客户端还是持续日志。

DP 对任意辅助信息保持其相邻分布比较，但不会修复输入收集、访问控制、实现侧信道或输出语义本身的问题。若发布的统计量在业务上已经唯一确定某个人，机制必须靠噪声和参数承担这项风险；哈希标识符或删除姓名并不自动满足 DP。

差分隐私也不等于泛化。它最初是隐私定义；输出分布对单条样本稳定，又能作为控制自适应过拟合的充分条件。这个额外统计结论及其样本量和失败概率见差分隐私蕴含泛化公理库差分隐私蕴含泛化Differential privacy implies generalization · Differential privacy and generalization · 隐私稳定性泛化把相邻数据集上的差分隐私稳定性转化为自适应选择统计量的高概率泛化保证。，不能反向写进 DP 的定义。

参考资料

• Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith, “Calibrating Noise to Sensitivity in Private Data Analysis,” TCC, 2006。
• Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 2014, Chapters 2–3。
• Cynthia Dwork et al., “Our Data, Ourselves: Privacy Via Distributed Noise Generation,” EUROCRYPT, 2006，关于分布式与本地信任边界的早期路线。