第二讲：差分隐私的基本定义

好，咱们直接进入正题。

上一章我聊了为什么需要差分隐私——说白了，就是防止“根据查询结果倒推出某个人在不在数据集里”。这一章我们来啃定义。我知道很多人一看到数学公式就头疼，但差分隐私的核心定义其实没那么复杂。

我个人习惯把形式化定义拆成两层来理解：纯ε-差分隐私和它的“兄弟”(ε,δ)-差分隐私。前者是理想标准，后者是现实工程中的妥协方案。

差分隐私形式化定义体系 差分隐私 纯 ε-差分隐私 Pr[M(D)∈S] ≤ e^ε · Pr[M(D')∈S] (ε,δ)-差分隐私 Pr[M(D)∈S] ≤ e^ε·Pr[M(D')∈S] + δ 典型机制 拉普拉斯机制 · 指数机制 典型机制 高斯机制 · 自适应组合 理想vs现实：纯DP保障隐私边界，(ε,δ)-DP让方案更灵活

2.1 纯 ε-差分隐私：最干净的定义

我们先来看最原始、最严格的形式。

形式化定义（ε-差分隐私）

给定一个随机算法 M: D → R，对于任意两个相邻数据集 D 和 D'（相差一条记录），以及任意输出子集 S ⊆ R，如果满足：

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S]

则称算法 M 满足 ε-差分隐私。

这里面的几个关键词我得给你讲透。

  • “相邻数据集”：D 和 D' 只有一条记录不同。这是我做项目时最容易搞混的地方——是“相差一条”，不是“完全不一样”。
  • “随机算法 M”：为什么强调随机？如果算法是确定性的，比如直接输出“张三患病”，那改一条记录就能看出差异。差分隐私靠的是随机扰动，让输出“飘忽不定”。
  • “隐私预算 ε”：这个参数决定隐私保护力度。ε 越小，保护越强——输出对单条记录变化越不敏感。反之，ε 越大，保护越弱。

我刚开始做差分隐私时，曾误解过 ε 的含义。以为 ε=0 才安全。后来才发现，ε=0 意味着输出完全独立于数据——那你还查什么？ε 是一个权衡参数。实际操作中，ε 在 0.1 到 10 之间比较常见，取决于场景敏感度。

速记技巧

你可以把 e^ε 理解成“隐私损失比”。比如 ε=ln2≈0.693，意味着任意两个人的查询结果概率差异不超过 2 倍。差异越小，攻击者越难区分。

2.2 插曲：为什么需要 (ε,δ)-差分隐私？

纯 ε-DP 很漂亮，但现实世界不给面子。

我遇到过这样一个场景：数据集统计量分布特别稀疏，某些查询的敏感度极高。如果用纯 ε-DP，噪声会大到结果毫无意义。另外，像高斯机制这种噪声分布——它有无穷支撑，理论上总有一个微小的概率会让隐私保护“失效”。

这时候，我们需要允许“一点点的失败概率”。这就是 δ 存在的意义。

2.3 (ε,δ)-差分隐私：工程视角的妥协

形式化定义（(ε,δ)-差分隐私）

如果对于任意相邻数据集 D 和 D'，以及任意输出子集 S ⊆ R，满足：

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S] + δ

则称算法 M 满足 (ε,δ)-差分隐私。

区别在哪？多了一个加项 δ。δ 表示“允许违反 ε-差分隐私的最大概率”。

你想想看，纯 ε-DP 要求对 所有可能的输出事件，概率比都严格不超过 e^ε。而 (ε,δ)-DP 允许有 δ 概率的输出事件，其概率比可以大于 e^ε，甚至无穷大。但这不是无限放纵——δ 必须足够小，通常取 1/n² 甚至更小，其中 n 是数据集大小。

特征 ε-差分隐私 (ε,δ)-差分隐私
保证强度 ，零例外 概率性，允许 δ 概率例外
主要机制 拉普拉斯、指数 高斯、高效组合
适用场景 高敏感度、审计合规 高维数据、频繁查询
δ 典型取值 无 1/n² 或 10⁻⁶ 以下

避坑指南：δ 不是廉价参数

我曾经在项目中看到有人把 δ 设为 0.01，觉得“就 1% 的风险，没事”。这是灾难。对于包含 10 万条记录的数据集，1% 意味着 1000 条记录可能被完全暴露。实际操作中，δ 必须远小于 1/n，这是个硬性规则。

2.4 两种定义的关系与实际选择

两种定义之间其实有个包含关系：

  • ε-差分隐私 ⇔ (ε,0)-差分隐私（δ=0 的特例）
  • 所有 ε-DP 算法自动满足 (ε,δ)-DP
  • 但反过来不成立

我做实际系统时，会这样选：

  1. 优先尝试纯 ε-DP——如果噪声大小可以接受，直接用拉普拉斯机制。
  2. 如果噪声太大——改用高斯机制并引入 δ。嗯，这里要注意 δ 与组合次数有关，组合越多 δ 会迅速累积。
  3. 高维或复杂查询——考虑 (ε,δ)-DP 下的高级组合定理，比如 Rényi 差分隐私或集中差分隐私，但那是后面章节的内容。

2.5 代码实例：两种机制的伪代码对比

光说不练假把式。咱们写两段简化的伪代码，让你看看区别。

# ----- 纯 ε-差分隐私：拉普拉斯机制 -----
import random, math

def laplace_mechanism(true_count, epsilon):
    # 敏感度：计数查询为 1
    sensitivity = 1
    scale = sensitivity / epsilon
    noise = random.laplace(0, scale)
    return true_count + noise

# ----- (ε,δ)-差分隐私：高斯机制 -----
def gaussian_mechanism(true_count, epsilon, delta):
    sensitivity = 1
    # 高斯噪声尺度，由 (ε,δ) 共同决定
    sigma = math.sqrt(2 * math.log(1.25 / delta)) * sensitivity / epsilon
    noise = random.gauss(0, sigma)
    return true_count + noise

# 对比：同一数据集，同一 ε
true_val = 1000
print("拉普拉斯（ε=1.0）：", laplace_mechanism(true_val, 1.0))
print("高斯（ε=1.0, δ=1e-6）：", gaussian_mechanism(true_val, 1.0, 1e-6))

你看，拉普拉斯机制没有 δ，直接基于 ε 和敏感度。高斯机制多了一个 δ，噪声尺度公式里有一个 ln(1.25/δ) 项。δ 越小，ln(1.25/δ) 越大，噪声也越大。所以 δ 选太小，高斯噪声也会变大，这是工程上的权衡。

2.6 一个容易翻车的细节：δ 的累积

我曾经因为这个问题踩过坑，分享出来大家别重复。

假设你发布了 k 次 (ε,δ)-DP 查询，每次 δ=10⁻⁶，k=1000。你以为总 δ 还是 10⁻⁶？错，基本组合定理下，总 δ ≤ k·δ = 0.001。对于敏感数据集，0.1% 的概率泄露已经很高了。更可怕的是高级组合定理下，δ 会平方根增长，但绝不会消失。

实用经验

如果项目要求总隐私预算 ε=1, δ=10⁻⁶，分 100 次查询：
→ 简单组合：每次 ε=0.01, δ=10⁻⁸
→ 高级组合：每次 ε≈0.1, δ=10⁻⁶（但需验证）
我通常先按简单组合上界计算，再让安全审核团队按高级组合精算。

2.7 小结

这章讲完了两个核心定义。我帮你理一下思路：

  • ε-DP：保证，最适合理论研究和高安全场景
  • (ε,δ)-DP：概率保证，更灵活，适合实际工程部署
  • δ 不是免费午餐——它是概率泄露的容忍度，需要严格控制
  • 选择取决于：噪声可接受度、查询数量、合规要求
← 上一章 📖 返回目录 下一章 →