Privacy and Utility Tradeoff in Approximate Differential Privacy
Privacy and Utility Tradeoff in Approximate Differential Privacy
复制标题
近似差分隐私中的隐私和效用权衡
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sanjiv Kumar
中科院分区：
文献类型：
--
作者：
Quan Geng;Wei Ding;Ruiqi Guo;Sanjiv Kumar
我们描述了最小噪声幅度和功率的噪声添加机制在$（Δ，δ）$-差分隐私单个实值查询函数。我们推导出新的下限使用线性规划的对偶，和新的上限，提出了一个新的类的$（δ，δ）$-差分私有机制，截断拉普拉斯}机制。我们发现，乘法差距的下限和上限在各种高隐私制度为零，证明了紧的下限和上限，从而建立截断拉普拉斯机制的最优性。特别是，我们的研究结果关闭了以前的常数乘法的离散设置的差距。数值实验表明，截断拉普拉斯机制的最佳高斯机制在所有的隐私机制的改善。
We characterize the minimum noise amplitude and power for noise-adding mechanisms in $(epsilon, delta)$-differential privacy for single real-valued query function. We derive new lower bounds using the duality of linear programming, and new upper bounds by proposing a new class of $(epsilon,delta)$-differentially private mechanisms, the emph{truncated Laplacian} mechanisms. We show that the multiplicative gap of the lower bounds and upper bounds goes to zero in various high privacy regimes, proving the tightness of the lower and upper bounds and thus establishing the optimality of the truncated Laplacian mechanism. In particular, our results close the previous constant multiplicative gap in the discrete setting. Numeric experiments show the improvement of the truncated Laplacian mechanism over the optimal Gaussian mechanism in all privacy regimes.