Paper 2017/1034

Tight on Budget? Tight Bounds for r-Fold Approximate Differential Privacy

Sebastian Meiser and Esfandiar Mohammadi


Many applications, such as anonymous communication systems, privacy-enhancing database queries, or privacy-enhancing machine-learning methods, require robust guarantees under thousands and sometimes millions of observations. The notion of r-fold approximate differential privacy (ADP) offers a well-established framework with a precise characterization of the degree of privacy after r observations of an attacker. However, existing bounds for r-fold ADP are loose and, if used for estimating the required degree of noise for an application, can lead to over-cautious choices for perturbation randomness and thus to suboptimal utility or overly high costs. We present a numerical and widely applicable method for capturing the privacy loss of differentially private mechanisms under composition, which we call privacy buckets. With privacy buckets we compute provable upper and lower bounds for ADP for a given number of observations. We compare our bounds with state-of-the-art bounds for r-fold ADP, including Kairouz, Oh, and Viswanath's composition theorem (KOV), concentrated differential privacy and the moments accountant. While KOV proved optimal bounds for heterogeneous adaptive k-fold composition, we show that for concrete sequences of mechanisms tighter bounds can be derived by taking the mechanisms' structure into account. We compare previous bounds for the Laplace mechanism, the Gauss mechanism, for a timing leakage reduction mechanism, and for the stochastic gradient descent and we significantly improve over their results (except that we match the KOV bound for the Laplace mechanism, for which it seems tight). Our lower bounds almost meet our upper bounds, showing that no significantly tighter bounds are possible.

Note: Updated abstract and keywords.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.The 25th ACM Conference on Computer and Communications Security
differential privacyr-fold compositioncontinual observation
Contact author(s)
s meiser @ ucl ac uk
2018-09-05: last of 4 revisions
2017-10-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian Meiser and Esfandiar Mohammadi},
      title = {Tight on Budget? Tight Bounds for r-Fold Approximate Differential Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1034},
      year = {2017},
      doi = {10.1145/3243734.3243765},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.