Optimal Noise-Adding Mechanism in Additive Differential Privacy
Optimal Noise-Adding Mechanism in Additive Differential Privacy
复制标题
加性差分隐私中的最优加噪机制
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sanjiv Kumar
中科院分区：
文献类型：
--
作者：
Quan Geng;Wei Ding;Ruiqi Guo;Sanjiv Kumar
在一般的代价最小化框架下，针对单个实值查询函数，推导出最优的$（0，\delta）$-差分私有查询输出无关噪声添加机制.在较温和的技术条件下，我们证明了最优噪声概率分布是一个在原点具有概率质量的均匀分布。我们显式地推导出一般$\ell^p$代价函数的最优噪声分布，包括$\ell ^1 $（噪声幅度）和$\ell ^2 $（噪声功率）代价函数，并表明当$\delta > \frac{p}{p+1}$时，发生在原点的概率集中。我们的研究结果表明，在现有的高斯机制的改进的两个和三个因素的$（0，\delta）$-差分隐私在高隐私制度的背景下，最大限度地减少噪声幅度和噪声功率，和增益是更明显的低隐私制度。我们的结果是一致的现有的结果为$（0，\delta）$-差分隐私在离散设置，并确定在连续设置的概率集中现象。
We derive the optimal $(0, \delta)$-differentially private query-output independent noise-adding mechanism for single real-valued query function under a general cost-minimization framework. Under a mild technical condition, we show that the optimal noise probability distribution is a uniform distribution with a probability mass at the origin. We explicitly derive the optimal noise distribution for general $\ell^p$ cost functions, including $\ell^1$ (for noise magnitude) and $\ell^2$ (for noise power) cost functions, and show that the probability concentration on the origin occurs when $\delta > \frac{p}{p+1}$. Our result demonstrates an improvement over the existing Gaussian mechanisms by a factor of two and three for $(0,\delta)$-differential privacy in the high privacy regime in the context of minimizing the noise magnitude and noise power, and the gain is more pronounced in the low privacy regime. Our result is consistent with the existing result for $(0,\delta)$-differential privacy in the discrete setting, and identifies a probability concentration phenomenon in the continuous setting.