Composable and versatile privacy via truncated CDP

By Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke. 2018

191 citations recorded by the source corpus.

We propose truncated concentrated differential privacy (tCDP), a refinement of differential privacy and of concentrated differential privacy. This new definition provides robust and efficient composition guarantees, supports powerful algorithmic techniques such as privacy amplification via sub-sampling, and enables more accurate statistical analyses. In particular, we show a central task for which the new definition enables exponential accuracy improvement.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistical Learning Theory, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Rényi Differential Privacy of the Sampled Gaussian Mechanism (2019, methodology): “Theorem 5 holds for any additive noise whose distribution is centrally symmetric, which also includes Laplace, sinh-normal [BDRS18], their discretized and multi-dimensional variants.”
Privacy Amplification by Iteration (2018, background): “The only systematically studied instance of this phenomenon is privacy ampliﬁcation by sampling [KLN + 08, BBKN14, WFS15, BDRS18, WBK18, ACG + 16].”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, methodology): “For CDP, subsampling does not improve the privacy parameters (Bun et al., 2018).”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, background): “…from other notions of privacy deﬁned in terms of the moment generating function of the privacy loss random variable, including concentrated DP [Dwork and Rothblum, 2016], zero-concentrated DP [Bun and Steinke, 2016], Rényi DP [Mironov, 2017], and truncated concentrated DP [Bun et al., 2018].”
Federated Learning with Bayesian Differential Privacy (2019, background): “computational DP [18], mutual-information privacy [19], [20], different versions of concentrated DP (CDP [21], zCDP [22], tCDP [23]), and Rényi DP (RDP) [24].”
Locally Differentially Private Data Collection and Analysis (2019, background): “Also, novel privacy notions related to (ǫ, δ)-differential privacy such as concentrated differential privacy have also been studied recently [9, 37, 7].”
TAN without a burn: Scaling Laws of DP-SGD (2022, background): “Truncated CDP (tCDP) (Bun et al., 2018) is an extension of CDP, with improved properties of privacy amplification via sub-sampling, which is crucial for DP-SGD-style algorithms.”
Deep Learning with Gaussian Differential Privacy (2019, unknown): “From a diﬀerent angle, a substantial recent eﬀort has been devoted to relaxing diﬀerential privacy using divergences of probability distributions to overcome the weakness of ( ε, δ )-DP in handling composition [20, 10, 41, 11].”
Gaussian Di ↵ erential Privacy (2019, background): “While the same property holds for many divergence based measures of indistinguishability such as the R´enyi divergences used by the concentrated di ↵ erential privacy family of deﬁnitions [DR16, BS16, Mir17, BDRS18], a consequence of the following theorem is that trade-o ↵ functions o ↵ er the most ”
Poission Subsampled Rényi Differential Privacy (2019, background): “Finally, Bun et al. (2018) studies subsampling in CDP with a conclusion that subsampling does not amplify the CDP parameters in general.”
The limits of pan privacy and shuffle privacy for learning and estimation (2020, result): “Thus, our results imply essentially the same lower bounds for pure differential privacy, concentrated differential privacy [12, 25], truncated concentrated differential privacy [10], Rényi differential privacy [45], and Gaussian differential privacy [18], none of which were known prior to our work.”
Private-kNN: Practical Differential Privacy for Computer Vision (2020, methodology): “The above lemma is implied by the original statement about tCDP [1] for randomly selecting a subset of a fixed size γn, because (1) tCDP is an upper bound of RDP; (2) the exact RDP calculation for the Poisson-subsampled Gaussian mechanism matches the RDP lower bound of the (Random subset) subsampled”
CoinPress: Practical Private Mean and Covariance Estimation (2020, unknown): “Some a priori boundedness is necessary for algorithms like ours that satisfy concentrated DP [16, 6, 29, 4], or satisfy pure DP.”
Private Hypothesis Selection (2019, methodology): “The selection of H∗ in the final step is a GAP-MAX algorithm [23] and is (ε/2, δ)-differentially private.”