Privacy Loss Classes: The Central Limit Theorem in Differential Privacy

Abstract

In recent years, privacy enhancing technologies have gained tremendous momentum and they are expected to keep a sustained importance. Quantifying the degree of privacy offered by any mechanism working on potentially sensitive data is a complex and well-researched topic; epsilon-differential privacy (DP) and its slightly weaker and more versatile variant (epsilon,delta)-approximate differential privacy (ADP) have become the de-facto standard for privacy measures in the literature. Recently, novel variants of (A)DP focused on giving tighter privacy bounds under continual observation. 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.