知识卡片

普通读书笔记卡 · 2688.c.1.b.8.c

拉普拉斯机制的实现与局限

理解等级:高级

加噪公式:$DP(D) = f(D) + (Y_1, \dots, Y_n)$,每个维度的噪声 $Y_i$ 服从 $\mu=0$、$b = GS_f/\varepsilon$ 的拉普拉斯分布。

  • 全局敏感度 $GS_f = \max\lVert f(D)-f(D’)\rVert$:f 作用在所有临近数据集上的曼哈顿距离最大值(各维度距离之和,如二维为 $|sum_a-sum_a’|+|sum_b-sum_b’|$,像出租车在方块街区行驶的距离);临近数据集有很多对,取最大值才能避免泄露;
  • 局部敏感度:固定某个数据集 D 时与其所有临近数据集的最大距离;所有局部敏感度的最大值就是全局敏感度。

生成拉普拉斯噪声:$Y = \mu - b\,\mathrm{sgn}(U)\ln(1-2|U|)$,U 服从 (-0.5, 0.5) 均匀分布。书中 Python 实现:

def get_noisy_digit(GSf, epsilon):
    beta = GSf/epsilon
    u = np.random.random()-0.5
    noisy_digit = 0.0 - beta * np.sign(u) * np.log(1.0 - 2 * np.abs(u))
    return np.rint(noisy_digit)

实验:真实值 5000、GS = 10:

ε 结果
1 30 次中约 13 次误差在 5 以内;1000 次的分布符合拉普拉斯分布
0.1 噪声大、误差大,可能导致数据不可用
4 噪声小、更接近真实值,但泄露风险增大

局限:查询返回 (5000, 50)、GS 增至 12 时,第一维表现与之前差不多,第二维加噪后从小于 0 到大于 100 都可能出现,严重偏离真实的 50。原因是多个返回值的数值量级相差太大——全局敏感度适合单个返回值的场景,不太适合多返回值的复杂查询;改用局部敏感度又可能造成隐私泄露,这时可能需要新的敏感度或算法。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《数据安全架构设计与实战》第18章《第18章 隐私保护增强技术》18.3.3 数值型差分隐私;18.3.4 数值型差分隐私的局限性(源文件:extracted/数据安全架构设计与实战/_epub-src/OEBPS/text00023.html,来源项目 book-sources) - 结论依据:18.3.3节给出数值型差分隐私的加噪公式、全局与局部敏感度和曼哈顿距离、拉普拉斯分布噪声生成公式与Python实现,并以ε=1、0.1、4做对比实验;18.3.4节用二维查询(5000, 50)演示量级差异导致第二维误差过大,说明全局敏感度不适合多返回值复杂查询。 - 原始内容:这也表明差分隐私的全局敏感度对于单个返回值的场景表现较好,但不太适合复杂的具有多个返回值的复杂查询场景,特别是多个返回值不在同一量级时;