Better Gaussian Mechanism using Correlated Noise
<|reference_start|>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 $(\sqrt{d} + 1)/4$ to all counts allows us to reduce the variance of the independent Gaussian noise samples to scale only with $(d + \sqrt{d})/4$. The total noise added to each counting query follows a Gaussian distribution with standard deviation scaled by $(\sqrt{d} + 1)/2$ rather than $\sqrt{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.<|reference_end|>
@article{lebeda2024better,
    title={Better Gaussian Mechanism using Correlated Noise},
    author={Christian Janos Lebeda},
    journal={arXiv preprint arXiv:2408.06853},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.06853},
    primaryClass={cs.CR cs.DS}
}