Paper 2018/820

Privacy Loss Classes: The Central Limit Theorem in Differential Privacy

David Sommer, Sebastian Meiser, and Esfandiar Mohammadi

Abstract

Quantifying the privacy loss of a privacy-preserving mechanism on potentially sensitive data is a complex and well-researched topic; the de-facto standard for privacy measures are $\varepsilon$-differential privacy (DP) and its versatile relaxation $(\varepsilon,\delta)$-approximate differential privacy (ADP). Recently, novel variants of (A)DP focused on giving tighter privacy bounds under continual observation. In this paper we unify many previous works via the \emph{privacy loss distribution} (PLD) of a mechanism. We show that for non-adaptive mechanisms, the privacy loss under sequential composition undergoes a convolution and will converge to a Gauss distribution (the central limit theorem for DP). We derive several relevant insights: we can now characterize mechanisms by their \emph{privacy loss class}, i.e., by the Gauss distribution to which their PLD converges, which allows us to give novel ADP bounds for mechanisms based on their privacy loss class; we derive \emph{exact} analytical guarantees for the approximate randomized response mechanism and an \emph{exact} analytical and closed formula for the Gauss mechanism, that, given $\varepsilon$, calculates $\delta$, s.t., the mechanism is $(\varepsilon, \delta)$-ADP (not an over-approximating bound).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. Proceedings on Privacy Enhancing Technologies, Volume 2019: Issue 2
DOI
10.2478/popets-2019-0029
Keywords
differential privacyprivacy loss
Contact author(s)
s meiser @ ucl ac uk
david sommer @ inf ethz ch
History
2020-08-12: last of 3 revisions
2018-09-06: received
See all versions
Short URL
https://ia.cr/2018/820
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/820,
      author = {David Sommer and Sebastian Meiser and Esfandiar Mohammadi},
      title = {Privacy Loss Classes: The Central Limit Theorem in Differential Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2018/820},
      year = {2018},
      doi = {10.2478/popets-2019-0029},
      note = {\url{https://eprint.iacr.org/2018/820}},
      url = {https://eprint.iacr.org/2018/820}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.