Dec, 2012
差分隐私中的最优机制
The Optimal Mechanism in Differential Privacy
Quan Geng, Pramod Viswanath
TL;DR本文提出了单一实值查询函数的最优 ε- 差分隐私机制，其噪声概率分布类具有楼梯形状、对称性、单调递减和几何衰减，可以被视为均匀概率分布的几何混合，并将此机制自然地推广到了离散查询输出环境和更抽象的环境中。通过将最优性能与拉普拉斯机制的性能进行比较，我们得出结论，当 ε 趋近于 0 时，拉普拉斯机制是渐近最优的；而在 ε 趋近于 +∞时，最小噪声振幅和最小噪声功率分别为 Θ(Δe^-ε/2) 和 Θ(Δ^2 e^-2ε/3)，而拉普拉斯机制的噪声振幅和功率期望分别为 Δ/ε 和 2Δ^2/ε^2，在低隐私保护级别下获得更明显的收益。