Optimal Noise Adding Mechanisms for Approximate Differential Privacy
This work provides theoretical insights into privacy-utility trade-offs for differential privacy mechanisms, which is incremental but important for researchers and practitioners in privacy-preserving data analysis.
The paper tackles the problem of designing optimal noise-adding mechanisms for approximate differential privacy, showing that in high privacy regimes, the optimal noise magnitude and power scale as Θ(min(1/ε, 1/δ)) and Θ(min(1/ε², 1/δ²)), respectively, and that uniform noise and discrete Laplacian mechanisms are near-optimal.
We study the (nearly) optimal mechanisms in $(ε,δ)$-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 $ε$ and $δ$ in utility and privacy analysis for histogram-like query functions ($\ell^1$ sensitivity), and show that the $(ε,δ)$-differential privacy is a framework not much more general than the $(ε,0)$-differential privacy and $(0,δ)$-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 $(ε,δ) \to (0,0)$). We conclude that in $(ε,δ)$-differential privacy, the optimal noise magnitude and noise power are $Θ(\min(\frac{1}ε,\frac{1}δ))$ and $Θ(\min(\frac{1}{ε^2},\frac{1}{δ^2}))$, respectively, in the high privacy regime.