Reviewing and Improving the Gaussian Mechanism for Differential Privacy

Differential privacy provides a rigorous framework to quantify data privacy, and has received considerable interest recently. A randomized mechanism satisfying (ε, δ)-differential privacy (DP) roughly means that, except with a small probability δ, altering a record in a dataset cannot change the probability that an output is seen by more than a multiplicative factor eε . A well-known solution to (ε, δ)-DP is the Gaussian mechanism initiated by Dwork et al. [1] in 2006 with an improvement by Dwork and Roth [2] in 2014, where a Gaussian noise amount √2ln frac2δ × fracDeltaε of [1] or √2ln frac1.25δ × fracDeltaε of [2] is added independently to each dimension of the query result, for a query with ℓ2-sensitivity Delta. Although both classical Gaussian mechanisms [1,2] assume 0 < ε ≤ 1, our review finds that many studies in the literature have used the classical Gaussian mechanisms under values of ε and δ where the added noise amounts of [1,2] do not achieve (ε,δ)-DP. We obtain such result by analyzing the optimal noise amount σDP-OPT for (ε,δ)-DP and identifying ε and δ where the noise amounts of classical mechanisms are even less than σDP-OPT. Since σDP-OPT has no closed-form expression and needs to be approximated in an iterative manner, we propose Gaussian mechanisms by deriving closed-form upper bounds for σDP-OPT. Our mechanisms achieve (ε,δ)-DP for any ε, while the classical mechanisms [1,2] do not achieve (ε,δ)-DP for large ε given δ. Moreover, the utilities of our mechanisms improve those of [1,2] and are close to that of the optimal yet more computationally expensive Gaussian mechanism.