先回顾一下隐私损失随机变量PLRV背后的直觉。假设秘密机制返回输出。攻击者试图判断输入是还是两者只差一个人的数据。PLRV有点像攻击者手中的实际值就是他在观察到输出后获得的优势。这给了我们-DP 的另一种表述——作为这个值的上界。如果是-DP那么对于和的所有可能选择以及所有可能的输出怎么把这个最坏情况属性转成平均情况定义有两个方向对可能的数据库和取平均…………或者对可能的输出取平均。第一个方向是个糟糕的主意™其中有些微妙原因这里就不展开了。第二个方向则很有意义。这跟-DP 的近似放松是同一类思路有一小部分概率会出现比预期更糟的情况。重要的是这个概率不依赖于攻击者完全来自算法本身的随机性不需要额外假设。不过有一个关键区别。在-DP 中允许有一小部分概率最多出现无限隐私损失。但当我们对隐私损失取平均时这就不行了。如果 99.99% 的时间里隐私损失非常低但 0.01% 的概率下是无穷大……那平均值还是无穷大。所以限制平均 PLRV 是一种放松 DP 的方式但不允许出现无限糟糕的事件。任意糟糕的事件仍可能发生但只能以趋于零的概率发生。下面来形式化这个想法。Rényi 差分隐私这是捕捉平均风险直觉的第一次尝试。对于每对在单条记录上不同的数据库和我们要求这里是期望值根据每个可能事件的概率进行加权。一个非常糟糕的事件如果几乎不发生那就还可以接受。看起来捕捉到了我们最初的直觉。但问题在于我们平均的对象不对。贝叶斯攻击者能获得的优势是不是所以平均隐私损失并不等于平均风险。用一张图来说明。下图展示了一个虚构机制中攻击者的增益分布根据随机输出投注赔率会怎么变化显示攻击者增益的虚构分布的图表。以 30% 的概率它的值为 150然后以离散但指数方式减少。在这个分布中的期望值平均约为。换算成攻击者增益大约是 30。与上面相同的图表在 y30 处有一条红色虚线。它看起来太低而无法表示平均值。这不对。实际风险通常比平均值大得多如果要平均风险应该取的平均值。这才更接近直觉。要求变成这就合理多了可以看作是风险的算术平均值。画出来的话对应的就是蓝线的平均值。带有虚构分布的图表在 y68.5 处有一条红色虚线但还是感觉有点随意。为什么不用别的平均函数呢隐私损失的大值对应最糟糕的事件这些事件特别可怕——也许我们该给它们更多权重比如用二次平均值。那就要求类似这样的东西这给了我们比以前更大的平均值。与之前相同的图表在 y90.4 处有一条红色虚线来推广一下。为了决定用哪种平均函数引入一个参数。这就是 Rényi 差分隐私。如果对上述不等式在和的所有选择上都成立我们就说它满足-Rényi 差分隐私。的一些特殊值对应常见的平均函数退化为的算术平均值等价于的几何平均值限制的算术平均值限制的二次平均值限制的三次平均值还可以取退化为的最大值此时等价于-DP。用之前的例子来可视化这些选项与之前相同的图表有四条红色虚线标记为 alpha1、2、3 和无穷大。无穷大线在 150对应于蓝线的最大值。Rényi DP 由 Ilya Mironov 提出有一系列漂亮的性质。特别是它的组合性质跟 DP 一样好如果机制是-Rényi DP机制是-DP那么同时发布两者的输出就是-DP。零集中差分隐私Rényi DP 很优美但它多了一个参数。这有点烦人。选已经很让人头疼了还要额外决定怎么平均风险感觉更难。但平均隐私损失这个想法确实很自然。理想情况下我们想保留这种直觉但只用一个参数。如果一次覆盖所有可能的值呢越大给坏事件的权重越多随着增大平均值也变大。那如果对平均值设一个上界……但这个上界也随增长呢这似乎是个好思路。问题是它应该增长多快递增函数有很多种但对数跟指数的表现可不一样既然有选择余地我们可以想想单参数定义还需要什么。前面我们看到高斯噪声是设计 DP 机制的好工具用新定义以简洁的方式描述其隐私保证就太好了。组合也很重要如果可能的话组合结果越简单越好。总结一下我们在找一个满足以下条件的表述只有一个参数越大对应的也越大能以简洁精确的方式描述高斯噪声的保证并且有简单的组合保证。这正是零集中差分隐私zCDP给出的。由 Mark Bun 和 Thomas Steinke 提出可以用简单的话解释给定单参数每个对应的最多为。用上面的形式化语言如果机制满足-zCDP很容易验证它满足上述所有要求单参数对应隐私损失的算术平均值。等价地对应的几何平均值。与之间最多是线性关系非常简洁。对高斯机制的描述很漂亮。假设你计算的统计数据灵敏度为给结果加上方差为的高斯噪声结果就满足-zCDP其中。比给出-DP 保证的公式清爽多了组合轻而易举。一个机制是-zCDP另一个是-zCDP同时发布两者就是-zCDP。最后两点对于分析多个高斯机制特别有用可以分别分析每个机制然后把对应的值加起来。即使它们用了很不同的噪声幅度也没关系。而且得到的保证比用-DP 来算要精确得多。这些优良性质使得 zCDP 在实践中被用于一些高知名度的场景比如 2020 年美国人口普查的重新分区数据。如果你要发布大量统计数据在隐私分析中使用 zCDP 很可能也会受益。简而言之能用推文长度的摘要概括我们目前看到的所有定义吗试试-DP绝对最坏情况就是。-DP最坏情况是几乎总是。-Rényi DP平均情况是告诉你用哪种平均函数。-zCDP多组-Rényi DP 保证同时成立精心选择以方便使用。很简单对吧注意本文为了简化做了取舍。我试图找到这些概念最简洁的直觉编了一个巧妙的故事把它们串起来。代价是牺牲了历史准确性。如果你的目标只是获得对这些定义的直观理解读到这里就够了。如果你对历史也感兴趣请继续往下看。跟上面的故事相反零集中 DP 实际上比 Rényi DP 更早出现。它本身建立在更早的定义集中 DP 之上由 Dwork 和 Rothblum 提出。集中 DP 说的是如果你取 PLRV 并减去它的均值会得到一个次高斯分布。集中 DP 是一个富有成果的概念被用来证明-DP 更紧密的组合定理也能以更简洁的方式描述高斯机制的隐私特性。但它也有缺点不对后处理封闭表述相当复杂。零集中 DP 就是为了修复这些问题而提出的它用更简洁的方式形式