Better Gaussian Mechanism using Correlated Noise
Christian Janos Lebeda · Society for Industrial and Applied Mathematics eBooks · 2025
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 to all counts allows us to reduce the variance of the independent Gaussian noise samples to scale only with . The total noise added to each counting query follows a Gaussian distribution with standard deviation scaled by rather than . 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.