How Well Can Differential Privacy Be Audited in One Run?

这是一篇关于差分隐私（Differential Privacy, DP）审计的学术论文，题为《单次运行中差分隐私的审计效果如何？》（HOW WELL CAN DIFFERENTIAL PRIVACY BE AUDITED IN ONE RUN?）。作者来自耶路撒冷希伯来大学，论文计划发表于 NeurIPS 2025。

以下是对该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 背景：差分隐私是保护机器学习训练数据隐私的核心技术。然而，理论上的隐私参数上界（Upper Bound）往往过于宽松，或者由于实现中的 Bug 导致上界不准确。因此，隐私审计（Privacy Auditing） 变得至关重要，旨在通过实验提供隐私参数的下界（Lower Bound）。
• 现有方法局限：
  • 经典审计（Classic Auditing）：通过多次运行算法（数百或数千次），比较相邻数据集（仅差一个样本）的输出分布差异。虽然理论上紧确（Asymptotically Tight），但计算成本极高，不切实际。
  • 单次运行审计（One-Run Auditing, ORA）：由 Steinke 等人提出，通过在单次训练运行中同时干预多个训练样本（例如，随机选择每个样本是 $x$ 还是 $y$），利用猜测游戏（Guessing Game）来推断隐私下界。这种方法计算效率高，且已被证明是有效的（Valid）。
• 核心问题：虽然 ORA 是有效的，但它是否紧确（即审计得到的下界能否无限接近真实的隐私参数）？如果存在差距，差距的来源是什么？如何优化 ORA 以缩小这些差距？

2. 方法论与理论框架 (Methodology)

论文建立了一个基于**猜测（Guessing-based）**的审计框架，并引入了新的理论工具来分析 ORA 的局限性。

2.1 审计设置

• 输入：审计器拥有算法 $M$ 的 Oracle 访问权。
• 策略：
  1. 构造一个“对向量”（Pair Vector）$Z = (x_1, y_1, ..., x_n, y_n)$。
  2. 随机生成比特串 $S \in \{-1, 1\}^n$，根据 $S$ 选择 $Z$ 中的元素构成数据集 $D$。
  3. 运行 $M(D)$ 得到输出 $O$。
  4. 猜测器 $G$ 根据 $O$ 猜测 $S$ 的每一位（$T_i \in \{-1, 0, 1\}$，0 表示放弃猜测）。
• 指标：统计正确猜测数 $v$ 和总猜测数 $r$，据此计算隐私下界 $\epsilon'$。

2.2 核心概念：分布性隐私损失 (Distributional Privacy Loss)

为了量化 ORA 的效能，作者引入了分布性隐私损失 $\ell_{M,Z,i}(o)$，即给定输出 $o$，区分第 $i$ 个样本是 $x_i$ 还是 $y_i$ 的对数似然比。这考虑了审计器对其他样本的不确定性。

2.3 三种新的隐私概念

为了刻画 ORA 的效能上限，作者定义了三种放松的隐私概念，分别对应三种“差距”：

1. 分布性差分隐私 (DDP)：$\epsilon_D$。对应干扰差距。
2. 平均情况分布性差分隐私 (AC-DDP)：$\epsilon_{AC}$。对应非最坏情况输出差距。
3. 平均元素 - 平均情况分布性差分隐私 (AE-AC-DDP)：$\epsilon_{AE-AC}$。对应非最坏情况元素隐私差距。

3. 主要贡献与发现 (Key Contributions & Results)

3.1 揭示了 ORA 的三大根本差距 (The Three Gaps)

论文证明，即使拥有最优的审计策略，ORA 也无法达到紧确性，主要受限于以下三个因素：

1. 非最坏情况元素隐私 (Non-worst-case privacy for elements)：
   • 原因：DP 定义关注最坏情况，但 ORA 需要大量猜测，必须包含那些隐私损失较小的样本。
   • 例子：Name and Shame 算法（随机输出一个输入元素）。ORA 必须猜测所有元素，但只有 1 个被暴露，导致整体猜测准确率接近随机猜测（1/2）。
2. 非最坏情况输出 (Non-worst-case outputs)：
   • 原因：DP 考虑最坏输出，但 ORA 只运行一次，可能恰好遇到“安全”的输出。
   • 例子：All or Nothing 算法（以概率 $p$ 输出全部输入，否则输出空）。如果 $p$ 很小，ORA 很难捕捉到泄露隐私的时刻。
3. 干扰 (Interference)：
   • 原因：这是 ORA 特有的核心障碍。当算法聚合多个输入（如求和、XOR）时，单个输入的影响被其他输入掩盖。审计器在猜测第 $i$ 个元素时，不知道其他元素的真实值，导致无法区分。
   • 例子：XOR 算法。无论输出什么，审计器在不知道其他位的情况下，猜测任意一位的准确率都是 1/2。

3.2 理论刻画 (Theoretical Characterization)

• 定理 5.1 & 5.2：给出了 ORA 最优效能的数学刻画。
  • 如果不允许放弃猜测，最优效能由 AE-AC-DDP 决定。
  • 如果允许放弃猜测（Abstention），最优效能由 $\epsilon^k_{AE-AC}$ 决定（仅考虑隐私损失最高的 $k$ 个元素）。
• 定理 5.3 (紧确性条件)：ORA 是渐近紧确的，当且仅当存在足够多的元素，其分布性隐私损失接近算法的真实隐私水平 $\epsilon(M)$。
  • 推论：对于局部算法（Local Algorithms，如独立处理每个样本的机制），ORA 是紧确的，因为不存在干扰。
  • 反例：对于对称算法（如计数查询），由于干扰和非最坏情况输出，ORA 效能趋近于随机猜测（1/2），不紧确。

3.3 案例研究：DP-SGD

• 问题：DP-SGD 是隐私保护机器学习的核心算法，其梯度聚合过程引入了严重的干扰。
• 现有方法：Dirac Canary 攻击（每个坐标只放一个审计梯度）虽然消除了干扰，但限制了可审计的样本数量，导致统计功效不足。
• 新发现：
  • 每个坐标放置多个审计梯度（Multiple elements per coordinate）可以在“更多猜测机会”和“增加干扰”之间取得更好的平衡，从而获得比 Dirac Canary 更紧的界限。
  • 实验表明，当每个坐标有 8 个元素时，审计界限（0.62）优于 1 个元素时（0.49）。

3.4 提出新方法：自适应单次运行审计 (Adaptive ORA, AORA)

• 核心思想：允许猜测器利用已猜出的真实值来辅助猜测后续元素。
• 机制：猜测器按顺序猜测，每猜出一个元素，就将其真实值（从 $S$ 中获取）作为已知信息，重新计算剩余元素的分布性隐私损失。
• 优势：
  • 有效性：证明了 AORA 仍然是有效的（Valid），即其下界依然成立。
  • 消除干扰：通过利用已知信息，AORA 能够消除干扰带来的不确定性。
  • 效果：
    • 对于 XOR 类算法，AORA 能达到完美效能（1.0），而 ORA 仅为 0.5。
    • 对于 DP-SGD，AORA 在增加每个坐标元素数量时，界限依然收紧，而 ORA 的界限会因干扰增加而变松。

4. 实验结果 (Experiments)

• DP-SGD 审计：
  • 在 $d=1000$ 维、$T=100$ 步的设置下，实验验证了理论预测。
  • 图 2：展示了每个坐标元素数量（$n/d$）对审计结果的影响。增加元素数量起初提升界限，但超过一定阈值后，非自适应 ORA 因干扰加剧而性能下降；而 AORA 则持续受益。
  • 图 3：直接对比 ORA 和 AORA。AORA 产生的界限显著高于 ORA，且随着元素密度增加，AORA 的优势更加明显。
• Count-In-Sets 算法：
  • 模拟了 DP-SGD 的聚合特性。结果显示，随着集合大小 $s(n)$ 增加，AORA 的界限保持紧致，而 ORA 迅速恶化。

5. 意义与结论 (Significance & Conclusion)

1. 理论突破：首次严格刻画了单次运行审计（ORA）的根本局限性，明确了“干扰”是限制其精度的关键因素，并给出了紧确性的充要条件。
2. 实践指导：
   • 解释了为什么某些算法（如 DP-SGD）在单次运行审计中表现不佳。
   • 提出了**多元素每坐标（Multiple elements per coordinate）**的策略，优化了审计设置。
   • 提出了自适应审计（AORA），这是一种新的、更强大的审计范式，能够显著缓解干扰问题，获得更紧的隐私下界。
3. 警示作用：提醒研究者和从业者，如果审计结果不理想，可能是因为算法本身存在干扰或审计方法未优化，而不仅仅是算法隐私保护不足。同时，防止将宽松的审计结果误读为算法是安全的（避免“绿布”效应）。

总结：这篇论文通过深入的理论分析和实验验证，揭示了单次运行隐私审计的内在瓶颈，并提出了通过自适应策略和优化样本配置来突破这些瓶颈的新方法，为高效、精确的隐私审计提供了重要的理论依据和技术路径。