Calibrating Noise to Sensitivity in Private Data Analysis
By Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam D. Smith. 2006
9,575 citations recorded by the source corpus.
We continue a line of research initiated in [10, 11] on privacy-preserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query function f mapping databases to reals, the so-called true answer is the result of applying f to the database. To protect privacy, the true answer is perturbed by the addition of random noise generated according to a carefully chosen distribution, and this response, the true answer plus noise, is returned to the user. Previous work focused on the case of noisy sums, in which f = Σ i g(x i ), where x i denotes the ith row of the database and g maps database rows to [0,1]. We extend the study to general functions f, proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f. Roughly speaking, this is the amount that any single argument to f can change its output. The new analysis shows that for several particular applications substantially less noise is needed than was previously understood to be the case. The first step is a very clean characterization of privacy in terms of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive.
Subfields: Artificial Intelligence, Statistics and Probability, 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
- Percy Liang
- Yoshua Bengio
- Mohit Bansal
- Philip S. Yu
- Quoc V. Le
- Jianfeng Gao
- Luke S. Zettlemoyer
- Sergey Levine
In Statistics and Probability
- Yu-Xiang Wang
- Jonathan Ullman
- Adam D. Smith
- Jayadev Acharya
- Vitaly Feldman
- Kamalika Chaudhuri
- Michael I. Jordan
- John C. Duchi
In Privacy & Security
- Jonathan Ullman
- Abhradeep Thakurta
- Peter Kairouz
- Adam D. Smith
- Kunal Talwar
- Daniel Kifer
- Vitaly Feldman
- Kamalika Chaudhuri
Citations in the corpus
- Ethical and social risks of harm from Language Models (2021, background): “This risk may occur regardless of the task the model is being used for and solutions may be technical, building for example on differential privacy (Dwork et al., 2006).”
- Quantifying Memorization Across Neural Language Models (2022, background): “Some memorization definitions, including lower-bounds on differential privacy (Dwork et al., 2006; Jagielski et al., 2020; Nasr et al., 2021) or counterfactual memorization (Feldman and Zhang, 2020; Zhang et al., 2021), require training hundreds or thousands of models, which is impractical for large…”
- Deduplicating Training Data Mitigates Privacy Risks in Language Models (2022, background): “Privacy Defenses Training data privacy can be protected using the differential privacy (DP) framework (Dwork et al., 2006), which guarantees that the effect of any single training example on the trained model is not too large.”
- Extracting Training Data from Large Language Models (2020, background): “Differential privacy (DP) [13,14] is a well-established notion of privacy that offers strong guarantees on the privacy of individual records in the training dataset.”
- MixMatch: A Holistic Approach to Semi-Supervised Learning (2019, background): “Indeed, protecting the privacy of training data amounts to proving that the model does not overfit: a learning algorithm is said to be differentially private (the most widely accepted technical definition of privacy) if adding, modifying, or removing any of its training samples is guaranteed not to ”
- Privacy-Preserving Generative Deep Neural Networks Support Clinical Data Sharing (2017, background): “Privacy Analysis We evaluate privacy based on the (ε, δ) formulation of differential privacy [15].”
- The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks (2018, background): “Differential privacy [13,15,16] is a property that an algorithm can satisfy which bounds the information it can leak about its inputs.”
- Fairness through awareness (2011, background): “Our notion of fairness may be viewed as a generalization of di ff erential privacy [Dwo06, DMNS06].”
- Deep Learning with Differential Privacy (2016, background): “Differential privacy [21, 18, 22] constitutes a strong standard for privacy guarantees for algorithms on aggregate databases.”
- Membership Inference Attacks Against Machine Learning Models (2016, background): “This motivation is closely related to the original goals of differential privacy [13].”
- Advances and Open Problems in Federated Learning (2019, background): “However, since privacy guarantees degrade as additional information is published about the same data [147, 148], these updates must be less frequent to still preserve both privacy and accuracy of the overall analysis.”
- Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data (2016, background): “Differential privacy (Dwork et al., 2006b; Dwork, 2011) It will be useful to define the privacy loss and the privacy loss random variable .”
- Federated Learning: Collaborative Machine Learning without Centralized Training Data (2022, neutral): “A relatively recent branch of privacy research is that of differential privacy, introduced in 2006 [9], which we will investigate in more detail in 5.3.1.”
- Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “Similar to the traditional add/remove notion [71], Definition 1.1 can capture the regular replacement version of DP (originally defined in [21], where the notion of neighborhood is defined by replacing any data record with its worst-case alternative), by incurring up to a factor of two in the privacy…”
- The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “The closest work to ours is cpSGD (Agarwal et al., 2018), which also serves as an inspiration for much of our work. cpSGD uses a distributed version of the binomial mechanism (Dwork et al., 2006a) to achieve distributed DP.”
- Privacy Amplification by Decentralization (2020, methodology): “To control the privacy leakage, the prominent approach is based on the standard notion of Differential Privacy (DP) [15].”
- Differentially Private Learning Needs Better Features (or Much More Data) (2020, methodology): “…observation that model gradients lie in a low-dimensional subspace (Kairouz et al., 2020; Zhou et al., 2020b). satisfies (ε, δ)-differential privacy (Dwork et al., 2006a), if for any datasets D,D′ that differ in one record, and any set of models S: Pr[A(D) ∈ S] ≤ eε Pr[A(D′) ∈ S] + δ. DP bounds…”
- Secure Single-Server Aggregation with (Poly)Logarithmic Overhead (2020, background): “Differential privacy (DP) [13] has become the de facto notion of individual privacy in data analysis.”
- On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “Differential privacy (DP) [20, 19] has become a leading framework for private-data analysis, with several recent practical deployments [25, 39, 28, 3, 16, 1].”