第五章：差分隐私（Differential Privacy）笔记

5.1 差分隐私的定义

  • 差分隐私是算法的性质，不是数据的性质。要说明一个数据集满足差分隐私，必须说明生成它的算法满足差分隐私。
  • 机制（Mechanism）：满足差分隐私的随机化函数，通常记为 (F)。
  • 相邻数据集：只差一个隐私单位的数据集。常见假设是“每个人的数据恰好在一行”，此时相邻数据集只差一行。
  • (\epsilon)-差分隐私形式化定义：

[
\frac{\Pr[F(x)\in S]}{\Pr[F(x’)\in S]} \le e^\epsilon
]

对任意相邻数据集 (x,x’) 和任意输出集合 (S) 都成立。

  • 若输出是离散的，也可写成单点形式：

[
\frac{\Pr[F(x)=s]}{\Pr[F(x’)=s]} \le e^\epsilon
]

  • 隐私参数 (\epsilon)：
    • (\epsilon) 越小，两个输出分布越接近，隐私保护越强；
    • 但需要加入更大的噪声，数据可用性越低；
    • 通常建议 (\epsilon) 取 1 左右或更小，大于 10 可能保护有限。

5.2 多少噪声才够？

  • 书中用恶意查询验证噪声是否足够：查询 Karrie 的收入是否 (\le 50K)。
  • 真实答案是 1；用拉普拉斯机制加噪后得到 5.43，攻击者无法判断真实是 0 还是 1。
  • 结论：差分隐私不拒绝恶意查询，而是加噪让所有查询结果都变得不可靠。
  • 随机性与可复现性：
    • 差分隐私依赖随机性，每次运行结果不同；
    • 这是隐私保护的必要条件；
    • 如需复现实验可设随机种子，但实际部署中不应公开或固定种子。

5.3 拉普拉斯机制

  • 公式：

[
F(x) = f(x) + \operatorname{Lap}\left(\frac{s}{\epsilon}\right)
]

  • (f(x))：真实查询结果；
  • (s)：查询的敏感度；
  • (\epsilon)：隐私预算；
  • (\operatorname{Lap}(s/\epsilon))：从中心 0、尺度 (b=s/\epsilon) 的拉普拉斯分布采样噪声。
  • 敏感度 (s)：相邻数据集上，函数输出的最大变化量。
    • 计数查询的敏感度通常为 1；
    • 求和查询若属性无上下界，敏感度无界，需先裁剪；
    • 均值查询通常拆成“噪声求和 / 噪声计数”，再相除，按顺序组合消耗预算。
  • 拉普拉斯分布 PDF：

[
p(z)=\frac{1}{2b}\exp\left(-\frac{|z|}{b}\right)
]

  • 密度比证明思路：

[
\frac{p_{F(x)}(y)}{p_{F(x’)}(y)}

\exp\left(\frac{|y-f(x’)|-|y-f(x)|}{b}\right)
\le
\exp\left(\frac{s}{b}\right)

e^\epsilon
]

因此拉普拉斯机制满足 (\epsilon)-差分隐私。

5.4 隐私单位

  • 隐私单位：定义“相邻数据集”中到底相差多少数据。
  • 最常见：一个人（user-level privacy），保护整个人的全部数据，永久有效。
  • Apple 使用 person-day，只保护一个人一天提交的数据；跨天趋势不受保护。
  • 通常假设“每个人的数据恰好在一行”，以便形式化。
  • 如果假设不成立，应转换数据或查询，尽量保持“一个人”的隐私单位。

5.5 替换相邻与增删相邻

  • 替换相邻（Substitution Adjacency）：
    • 两个数据集大小相同；
    • 修改一行得到另一个；
    • 对应“某个人的数据被改成另一个值”。
  • 增删相邻（Add-Remove Adjacency）：
    • 两个数据集大小相差 1；
    • 增加或删除一行得到另一个；
    • 对应“某个人的数据存在或不存在”。
  • 在对称差距离下：
    • 增加或删除一行 → 距离为 1；
    • 修改一行 → 距离为 2。
  • 两种定义会影响敏感度计算和差分隐私的具体形式，需在整个隐私分析中保持一致。

总结

  • 差分隐私是算法性质，不是数据性质。
  • 机制是满足差分隐私的随机化函数。
  • 实现差分隐私的一种基本方法是加随机噪声，如拉普拉斯机制。
  • 噪声大小由敏感度和 (\epsilon) 决定：(\epsilon) 越小，噪声越大，隐私越强，可用性越低。
  • 隐私单位决定“相邻”的含义，默认应使用“一个人”。
  • 替换相邻和增删相邻是两种相邻数据集定义，影响敏感度计算。

Q&A

差分隐私是数据属性还是算法属性？

算法属性。它描述的是随机化机制在相邻数据集上的输出分布不可区分。

拉普拉斯机制为什么满足 (\epsilon)-差分隐私？

因为拉普拉斯分布的密度比可以用敏感度 (s) 控制，当噪声尺度 (b=s/\epsilon) 时，密度比不超过 (e^\epsilon)。

(\epsilon) 越小越好吗？

不是。(\epsilon) 越小隐私越强，但噪声越大，数据可用性越低。需要根据场景权衡。

什么是隐私单位？

隐私单位定义相邻数据集相差多少数据，比如一个人、一行、一张图像、一天的数据等。

替换相邻和增删相邻有什么区别？

替换相邻是修改一行，数据集大小不变；增删相邻是增加或删除一行，数据集大小相差 1。

为什么计数查询的敏感度通常是 1？

因为增加或删除一行，计数最多变化 1：新行满足条件则加 1，不满足则不变。

词汇表

术语 说明
差分隐私 算法性质，相邻数据集输出分布不可区分
机制 满足差分隐私的随机化函数
相邻数据集 只差一个隐私单位的数据集
隐私参数 (\epsilon) 控制隐私强度，越小隐私越强，噪声越大
敏感度 相邻数据集上函数输出的最大变化量
拉普拉斯机制 加拉普拉斯噪声的差分隐私机制
拉普拉斯分布 中心 0、尺度 (b) 的对称指数分布
隐私单位 相邻数据集相差的数据量，如一个人、一天
替换相邻 修改一行，数据集大小相同
增删相邻 增加或删除一行，数据集大小相差 1
随机性 差分隐私机制内部噪声的来源，保证输出不可预测