Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost
This work solves the problem of high utility loss in local differential privacy for sum estimation, which is significant for researchers and practitioners working with privacy-preserving data aggregation.
This paper addresses the problem of privately estimating the sum of $n$ user-held values under local differential privacy. It demonstrates that by introducing correlations among locally added noise variables, the estimation cost can match the optimal cost achievable in the centralized differential privacy setting, up to an arbitrarily small error.
We study privately estimating the sum of $n$ user-held values in the presence of an honest-but-curious server. This motivates requiring privacy not only at data release but also throughout server-side computation. We therefore adopt the local (pure) differential privacy model, in which each user transmits a noise-perturbed value. It is well known that independent local noise typically incurs a substantial utility loss compared to the centralized model, where noise is added only after aggregation. We show that this gap is not fundamental. By carefully designing correlations among the locally added noise variables, we construct $\varepsilon$-DP mechanisms whose estimation cost matches the optimal cost achievable in the centralized setting, up to an arbitrarily small error.