In this paper, we unify many of these previous works in a common core theory, focused on the privacy loss of a mechanism. We show that in sequential composition of the mechanism, the privacy loss (represented as a distribution) undergoes a convolution, which in turn enables us to show the central limit theorem for differential privacy: the privacy loss of any mechanism will converge to a Gauss distribution. This observation leads us to several practically relevant insights: 1) we show that several of the novel DP-variants are equally expressive as ADP, 2) we improve existing bounds, such as the moments accountant bound, 3) we derive exact ADP guarantees for the Gauss mechanism, i.e., an analytical and simple formula to directly calculate ADP (not an over-approximating bound), 4) we derive exact ADP guarantees for the Randomized Response, and, 5) we characterize the privacy guarantees of a mechanism by the Gauss distribution to which it converges, its privacy class, and using normal approximation theorems derive novel upper and lower ADP bounds for arbitrary mechanisms.
Category / Keywords: foundations / differential privacy, privacy loss Date: received 3 Sep 2018 Contact author: s meiser at ucl ac uk Available format(s): PDF | BibTeX Citation Version: 20180906:194029 (All versions of this report) Short URL: ia.cr/2018/820