Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910270753865728 |
|---|---|
| author | Pathegama, Madhura Avasarala, Srikanth Cadambe, Viveck R. Ziani, Juba |
| author_facet | Pathegama, Madhura Avasarala, Srikanth Cadambe, Viveck R. Ziani, Juba |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_30476 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost Pathegama, Madhura Avasarala, Srikanth Cadambe, Viveck R. Ziani, Juba Information Theory Cryptography and Security Machine Learning 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. |
| title | Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost |
| topic | Information Theory Cryptography and Security Machine Learning |
| url | https://arxiv.org/abs/2605.30476 |