Optimal Noise Adding Mechanisms for Approximate Differential Privacy
Quan Geng, and Pramod Viswanath Coordinated Science Laboratory and Dept. of ECE University of Illinois, Urbana-Champaign, IL 61801 Email: {geng5,
Abstract
We study the (nearly) optimal mechanisms in $(\epsilon,\delta)$ -approximate differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. We characterize the tradeoff between $\epsilon$ and $\delta$ in utility and privacy analysis for histogram-like query functions ( $\ell^{1}$ sensitivity), and show that the $(\epsilon,\delta)$ -differential privacy is a framework not much more general than the $(\epsilon,0)$ -differential privacy and $(0,\delta)$ -differential privacy in the context of $\ell^{1}$ and $\ell^{2}$ cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of $\ell^{1}$ and $\ell^{2}$ cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as $(\epsilon,\delta)\to(0,0)$ ). We conclude that in $(\epsilon,\delta)$ -differential privacy, the optimal noise magnitude and noise power are $\Theta(\min(\frac{1}{\epsilon},\frac{1}{\delta}))$ and $\Theta(\min(\frac{1}{\epsilon^{2}},\frac{1}{\delta^{2}}))$ , respectively, in the high privacy regime.
中文速览
差分隐私（differential privacy）领域长期存在一个悬而未决的问题：放宽的 (ε,δ)-差分隐私比严格的 ε-差分隐私究竟能"省"多少噪声？这篇论文针对整数值和直方图类（histogram-like）查询函数，在最小化噪声代价（ℓ¹和ℓ²损失）的框架下，系统推导了 (ε,δ)-差分隐私下的最优噪声机制及其理论下界。研究发现，均匀噪声机制和离散拉普拉斯（discrete Laplacian）机制在高隐私极限（(ε,δ)→(0,0)）下均接近最优，且最优噪声幅度和噪声功率分别为 Θ(min(1/ε, 1/δ)) 和 Θ(min(1/ε², 1/δ²))。这一结果揭示了一个出人意料的结论：在 ℓ¹ 敏感度模型中，(ε,δ)-差分隐私相比纯粹的 ε-差分隐私或 δ-差分隐私，实际上只带来常数倍的改善，并没有本质上的噪声量级优势——这与 ℓ∞ 敏感度下近似差分隐私能显著降低噪声方差的结论形成鲜明对比，为实际系统选择隐私机制提供了重要的理论依据。
原文 arXiv:1305.1330;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1305.1330v3