文章总结： 本文从信息论与假设检验视角系统阐述差分隐私的数学理论，涵盖互信息与dp参数的双向关系、f-dp与Rényidp框架、高斯与指数机制的最优性、串行与并行及高级组合定理，并深入分析dp-sgd的矩会计方法，指出RDP组合在隐私预算累计上比高级组合更紧，是当前最优方法。 综合评分： 88 文章分类： ai安全,数据安全,安全分析,安全研究

差分隐私的信息论基础与最优机制

原创

pandazhengzheng pandazhengzheng

安全分析与研究

2026年9月24日 22:00 广东

在小说阅读器读本章

去阅读

在公众号小说中沉浸阅读

定位：本文从信息论与假设检验视角，建立差分隐私（DP）的数学理论，分析最优机制设计、组合定理的精确形式，以及DP-SGD的矩会计方法。面向研究者和高级安全工程师。

一、DP的信息论基础

1.1 互信息与DP的关系

定义（(ε,δ)-DP）：机制 M 是 (ε,δ)-DP 的，若对任意相邻数据集 D, D’ 与任意输出集 S：

P(M(D) ∈ S) ≤ e^ε · P(M(D') ∈ S) + δ

定理1（互信息上界）：若 M 是 (ε,δ)-DP 的，则对任意数据集 D 与随机选择的相邻 D’（差一个样本）：

I(D; M(D)) ≤ ε·(e^ε - 1)·n + δ·log(n/δ)

其中 n 为数据集大小，I 为互信息。

含义：DP 限制机制泄露的关于输入的信息量。ε 越小，互信息越小，隐私保护越强。

定理2（互信息下界）：对任意机制 M，若 I(D; M(D)) ≤ I_max，则 M 满足 (ε, δ)-DP，其中：

ε ≥ I_max / (2n)

含义：互信息与 DP 参数存在双向关系，DP 本质上是信息论约束。

1.2 DP的假设检验刻画

DP 可等价刻画为假设检验的困难度：

定理3（Wasserman-Zhou）：M 是 (ε, 0)-DP 当且仅当对任意相邻 D, D’ 与任意检验 φ: Output → {0,1}：

P_D(φ = 1) + e^ε · P_{D'}(φ = 0) ≥ 1

即”区分 M(D) 与 M(D’)”的假设检验错误率有下界。

f-DP 框架：用假设检验的 trade-off 函数刻画 DP：

f_M(α, β) = inf { trade-off curve of M(D) vs M(D') }

定理4（f-DP 等价性）：M 是 (ε, 0)-DP 当且仅当其 trade-off 曲线 f_M 满足：

f_M(α) ≤ e^ε · (1 - α)   ∀ α ∈ [0,1]

f-DP 框架的优势：

• 组合定理在 f-DP 下有简洁形式（函数卷积）。
• 精确刻画（不损失）DP 保证，而 (ε,δ) 参数化有损失。

1.3 Rényi DP

定义（(α, ε)-RDP）：M 是 (α, ε)-RDP 的，若对任意相邻 D, D’：

D_α(M(D) || M(D')) ≤ ε

其中 D_α 为 Rényi 散度：

D_α(P || Q) = (1/(α-1)) · log E_Q[(P/Q)^α]

RDP 与 DP 的关系：

(α, ε)-RDP ⟹ (ε + log(1/δ)/(α-1), δ)-DP

优势：RDP 在组合下有加性（ε 累加），且转换为 DP 时可选择最优 α，比直接用 (ε,δ) 更紧。

二、最优机制设计

2.1 满足DP的最优机制

定义（查询的敏感度）：查询 f: Dataset → R 的 L2 敏感度：

Δf = max_{D, D' adjacent} ‖f(D) - f(D')‖_2

定理5（高斯机制最优性）：对敏感度 Δf 的查询，高斯机制 M(D) = f(D) + N(0, σ²I) 是 (ε, δ)-DP 的，当且仅当：

σ ≥ Δf · √(2·ln(1.25/δ)) / ε

且高斯机制在均方误差意义下最优（对单次查询）。

2.2 指数机制

对非数值查询，指数机制用效用函数 u: Dataset × Output → R：

P(M(D) = r) ∝ exp(ε · u(D, r) / (2·Δu))

定理6（指数机制效用界）：指数机制的输出 r* 满足：

P(u(D, r*) < OPT(u, D) - t) ≤ exp(-ε·t/(2·Δu))

其中 OPT 为最优效用。

含义：指数机制以高概率输出接近最优的解，且满足 DP。

2.3 后验采样的最优性

对贝叶斯推断，后验采样机制天然满足 DP：

定理7（后验采样 DP）：若先验 π 满足 π(θ)/π(θ’) ≤ e^β 对所有 θ, θ’，则后验采样机制 M(D) ~ π(θ|D) 满足 (β·ΔL, 0)-DP，其中 ΔL 为似然比。

最优性：在贝叶斯框架下，后验采样在最小化后验风险的同时满足 DP，是”效用-隐私”的最优权衡。

三、组合定理

3.1 串行组合

定理8（串行组合）：若 M_1 是 (ε_1, δ_1)-DP，M_2 是 (ε_2, δ_2)-DP，则组合机制 (M_1, M_2) 是 (ε_1 + ε_2, δ_1 + δ_2)-DP。

局限：串行组合是上界，实际隐私损失可能更小（若 M_1, M_2 使用独立噪声）。

3.2 并行组合

定理9（并行组合）：若 M_1, …, M_k 各自 (ε, δ)-DP，且作用于数据集的不相交子集，则组合机制是 (ε, δ)-DP（非 k·ε）。

应用：联邦学习中，各参与方在本地数据上做 DP 机制，整体隐私损失为单方损失（非累加）。

3.3 高级组合定理

定理10（高级组合）：若 M_1, …, M_k 各自 (ε, δ)-DP，则组合机制是 (ε’, k·δ + δ’)-DP，其中：

ε' = k·ε²/2 + k·ε·√(2·log(1/δ'))

改进：当 ε < 1 时，ε’ = O(ε·√k) 远优于串行组合的 k·ε。

3.4 RDP的精确组合

RDP 在组合下精确加性：

定理11（RDP 组合）：若 M_1 是 (α, ε_1)-RDP，M_2 是 (α, ε_2)-RDP，则组合是 (α, ε_1 + ε_2)-RDP。

DP-SGD 的 RDP 累计：DP-SGD 每步的 RDP 损失为：

ε_step(α) = (q²·α / (σ² - q·α)) &nbsp; 对 α < σ²/q

其中 q = batch_size/n 为采样率，σ 为噪声系数。

T 步累计：ε_total(α) = T · ε_step(α)

转换为 DP：ε = min_α [ε_total(α) + log(1/δ)/(α-1)]

优势：RDP 给出的 ε 比高级组合更紧，是 DP-SGD 隐私会计的当前最优方法。

四、DP-SGD的理论分析

4.1 Abadi的矩会计方法

矩会计（Moments Accountant）是 RDP 的具体实现，对 DP-SGD 给出精确隐私预算：

定理12（Abadi等）：DP-SGD 在 T 步、采样率 q、噪声 σ 下，满足 (ε, δ)-DP，其中：

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：安全分析与研究 pandazhengzheng pandazhengzheng《差分隐私的信息论基础与最优机制》