Better Gaussian Mechanism using Correlated Noise

We present a simple variant of the Gaussian mechanism for answering differentially private queries when the sensitivity space has a certain common structure. Our motivating problem is the fundamental task of answering d counting queries under the add/remove neighboring relation. The standard Gaussian mechanism solves this task by adding noise distributed as a Gaussian with variance scaled by d independently to each count. We show that adding a random variable distributed as a Gaussian with variance scaled by (√d + 1)/4 to all counts allows us to reduce the variance of the independent Gaussian noise samples to scale only with (d + √d)/4. The total noise added to each counting query follows a Gaussian distribution with standard deviation scaled by (√d + 1)/2 rather than √d. The central idea of our mechanism is simple and the technique is flexible. We show that applying our technique to another problem gives similar improvements over the standard Gaussian mechanism.