Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds

By Mark Bun, Thomas Steinke. 2016

1,008 citations recorded by the source corpus.

"Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Renyi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of "approximate concentrated differential privacy."

Subfields: Artificial Intelligence, Sociology and Political Science, 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 Sociology and Political Science

In Privacy & Security

Citations in the corpus

Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning (2017, background): “Several works have adopted DP as an efficient defense mechanism such as [5, 7, 11, 12, 18, 23, 24, 37, 53, 60, 65, 72, 86].”
Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data (2016, methodology): “The moments accountant was introduced by Abadi et al. (2016), building on previous work (Bun & Steinke, 2016; Dwork & Rothblum, 2016; Mironov, 2016).”
Privacy-Preserving Tensor Factorization for Collaborative Health Data Analysis (2019, methodology): “((Serial composition [4])) Let A : Dn → Y andA ′ : Dn →Z be randomized algorithms.”
AdaCliP: Adaptive Clipping for Private SGD (2019, background): “For the Gaussian mechanism, [14] introduced moments accountant, which provides tighter privacy bounds compared to other composition theorems [33, 34, 35, 34, 36].”
The structure of optimal private tests for simple hypotheses (2018, background): “For hypothesis tests with constant error probabilities, sample complexity bounds for differential privacy are equivalent, up to constant factors, to sample complexity bounds for other notions of distributional algorithmic stability, such as (ε,δ )-DP [31], concentrated DP [14, 34], KL- and TV-stabil”
Privacy Amplification by Iteration (2018, background): “The notions of zCDP [34], Moments Accountant [8], and Rényi differential privacy (RDP) [35] capture versions of this definition.”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “It offers a unified view of the -differential privacy (pure DP), ( , δ)-differential privacy (approximate DP), and the related notion of Concentrated Differential Privacy (Dwork and Rothblum, 2016; Bun and Steinke, 2016).”
Differentially-Private "Draw and Discard" Machine Learning (2018, methodology): “ in the DDML client-side Algorithm 1, further precision of adversary modeling, and in performing the analyses using the variant of Renyi Differential Privacy [34] or Concentrated Differential Privacy [7]. The optimism for the first claim stems from experience with other differentially private applic”
Detecting Violations of Differential Privacy (2018, background): “The term differential privacy covers a family of privacy definitions that include pure ε-differential privacy (the topic of this paper) [17] and its relaxations: approximate (ε,δ )differential privacy [16], concentrated differential privacy [8, 20], and Renyi differential privacy [31].”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “1] for the analysis) to repeatedly “peel off” the column of x with the approximately largest mean x , and applying the composition theorem for differential privacy [12], [42], [43].”
Rényi Differential Privacy (2017, methodology): “The closely related work by Dwork and Rothblum [9], followed by Bun and Steinke [10], explore privacy definitions—Concentrated Differential Privacy and zero-Concentrated Differential Privacy—that are framed using the language of, respectively, subgaussian tails and the Rényi divergence.”
Scalable Private Learning with PATE (2018, methodology): “To capture this effect quantitatively, Papernot et al. (2017) rely on the moments accountant, introduced by Abadi et al. (2016) and building on previous work (Bun & Steinke, 2016; Dwork & Rothblum, 2016).”