No free lunch in data privacy

By Daniel Kifer, Ashwin Machanavajjhala. 2011

730 citations recorded by the source corpus.

Subfields: Artificial Intelligence, 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 Privacy & Security

Citations in the corpus

Towards the Science of Security and Privacy in Machine Learning (2016, neutral): “Note that this result (presented below) is analogous to the no free lunch result in data privacy that captures the tension between utility and privacy [115], [116].”
Foundation Models and Fair Use (2023, background): “See, e.g., Kifer & Machanavajjhala (2011) for examples in social networks. guarantee (both leverage indistinguishability as the core concept), but is different in their precise semantics as well as the algorithmic primitives.”
Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning (2017, background): “Researchers can keep arguing about the proper use of DP or what DP is supposed to protect [39, 51, 52, 56], but ultimately, in the context of this work, one should ask: Would I use a system that let casual users recover images that are effectively indistinguishable from the ones in my picture folder”
A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, background): “Privacy of data subjects is defined by differential privacy, which is the state-of-the-art privacy notion [21], [22], [36] that assures a strong and provable privacy guarantee for aggregated data.”
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, background): “This said, if a and b are correlated, the attacker may still learn more than they otherwise would have; maintaining privacy in the face of any such correlation is discussed further in Sections 3 and 6 (see also [19]).”
Privacy in Pharmacogenetics: An End-to-End Case Study of Personalized Warfarin Dosing (2014, neutral): “Kifer and Machanavajjhala [25] addressed several common misconceptions about the topic, and showed that under certain conditions, it fails to achieve a privacy goal related to Dwork’s: nearly all evidence of an individual’s participation should be removed.”
Differential Privacy Preservation for Deep Auto-Encoders: an Application of Human Behavior Prediction (2016, background): “Differential privacy research has been significantly studied from the theoretical perspective, e.g., (Chaudhuri and Monteleoni 2008; Kifer and Machanavajjhala 2011).”
Differentially Private Password Frequency Lists (2016, background): “Kifer and Machanavajjhala [22] argued that even differential privacy might not provide sufficient privacy guarantees whenever we want to hide the influence of an individual.”
Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples (2016, methodology): “A user’s susceptibility to a contagious disease can be easily inferred by an adversary who has access to noisy query results and is aware of the fact that the user’s immediate family members are part of the database being queried [24].”
SoK: Security and Privacy in Machine Learning (2018, methodology): “ity to model the underlying distribution. Note that this result (presented below) is analogous to the no free lunch result in data privacy that captures the tension between utility and privacy [115], [116]. In the PAC learning model, data x;y is sampled from a distribution D. Recall that the learner”
Differentially Private Model Publishing for Deep Learning (2019, background): “The characteristics of input data, for example, dependency among training instances or dependency in the presence of training instances can render a differentially private mechanism ineffective for protecting the privacy of individuals [24], [25], [28].”
Hiding in the Crowd: A Massively Distributed Algorithm for Private Averaging with Malicious Adversaries (2018, background): “This is related to the “no free lunch” theorem in data privacy (Kifer and Machanavajjhala, 2011), see also the discussions in Kasiviswanathan and Smith (2014); Li et al. (2013).”
Edge Computing Security: State of the Art and Challenges (2019, background): “More generally speaking, differential privacy may not be applicable when the data have a high global sensitivity, which requires strong noises to perturb the data for privacy guarantees, thus sacrificing the utility of the data [87].”
Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy (2013, background): “• Analyzing existing mechanisms: A broader goal is to understand what privacy guarantees are achieved by methods in use today (e.g., disclosure-control methods currently used by statistical agencies, or releases that are mandated by law) that were not designed with specific privacy definitions in…”
Differentially Private Bayesian Inference for Exponential Families (2018, background): “(2)This variant assumes n remains fixed, which is sometimes called bounded differential privacy [23].”
Analyzing Graphs with Node Differential Privacy (2013, methodology): “Using such projections we get algorithms for accurately releasing the number of edges in a graph, and counts of small subgraphs such as triangles, k-cycles, and k-stars (used as sufficient statistics for popular graph models) in a graph, and certain estimators for power law graphs (see Sections 4…”
Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges (2016, background): “We will discuss the No Free Lunch Theorem in data privacy [25], and present alternate privacy definitions that can be customized to match the structure of the data [16, 21, 26].”
Technical Privacy Metrics (2015, background): “A no-free-lunch theorem shows that differential privacy’s guarantees degrade in the case of correlated data, for example, when nodes are added to a social network graph [75].”
Differentially Private Confidence Intervals (2020, background): “A query f is ( ε, δ ) - diﬀerentially private if for all neighboring x, x (cid:48) ∈ X , and for all sets S of possible outputs, This deﬁnition, sometimes called bounded diﬀerential privacy [12], is one of two common variants.”