2026-07-25T13:22:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23139 2025-10-02T12:35:01Z ddc:004 open_access

Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High ε Regime Harrison, Charlie Manurangsi, Pasin Differential Privacy Distributed Noise Addition Differential privacy (DP) can be achieved in a distributed manner, where multiple parties add independent noise such that their sum protects the overall dataset with DP. A common technique here is for each party to sample their noise from the decomposition of an infinitely divisible distribution. We analyze two mechanisms in this setting: 1) the generalized discrete Laplace (GDL) mechanism, whose distribution (which is closed under summation) follows from differences of i.i.d. negative binomial shares, and 2) the multi-scale discrete Laplace (MSDLap) mechanism, a novel mechanism following the sum of multiple i.i.d. discrete Laplace shares at different scales. For ε ≥ 1, our mechanisms can be parameterized to have O(Δ³ e^{-ε}) and O(min(Δ³ e^{-ε}, Δ² e^{-2ε/3})) MSE, respectively, where Δ denote the sensitivity; the latter bound matches known optimality results. Furthermore, the MSDLap mechanism has the optimal MSE including constants as ε → ∞. We also show a transformation from the discrete setting to the continuous setting, which allows us to transform both mechanisms to the continuous setting and thereby achieve the optimal O(Δ² e^{-2ε / 3}) MSE. To our knowledge, these are the first infinitely divisible additive noise mechanisms that achieve order-optimal MSE under pure DP for either the discrete or continuous setting, so our work shows formally there is no separation in utility when query-independent noise adding mechanisms are restricted to infinitely divisible noise. For the continuous setting, our result improves upon Pagh and Stausholm’s Arete distribution which gives an MSE of O(Δ² e^{-ε/4}) [Pagh and Stausholm, 2022]. Furthermore, we give an exact sampler tuned to efficiently implement the MSDLap mechanism, and we apply our results to improve a state of the art multi-message shuffle DP protocol from [Balle et al., 2020] in the high ε regime. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Charlie Harrison and Pasin Manurangsi 2025 Is Part Of LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FORC.2025.12 urn:nbn:de:0030-drops-231396 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode