No Free Lunch in Data Privacy

Summary: No free lunch: a no-free-lunch theorem shows DP privacy-utility requires data-generation assumptions. Privacy hinges on limiting inference about an individual's participation, not mere tuple presence; DP can breach participation in social networks and tabular data without modeling assumptions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1005896266e61eda
Venue: SIGMOD
Year: 2011
Pagerank: 0.00011304781
Overall Rank: 1,256 | 91.59%
DOI: 10.1145/1989323.1989345

Incoming Non-self Citations Over Time

Authors

1. Daniel Kifer (Pennsylvania State University)
2. Ashwin Machanavajjhala (Yahoo)

BibTeX Citation

@inproceedings{kifer_sigmod11,
        title = {{No Free Lunch in Data Privacy}},
        author = {Kifer, Daniel and Machanavajjhala, Ashwin},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989345},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989345},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
279	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.00022277389
858	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013391977
1,851	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.4955175e-05
2,383	Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies	2014	SIGMOD	8.5292865e-05
3,089	Plausible Deniability for Privacy-Preserving Data Synthesis	2017	VLDB	7.6434886e-05
3,134	Bayesian Differential Privacy on Correlated Data	2015	SIGMOD	7.5944855e-05
5,025	Utility Cost of Formal Privacy for Releasing National Employer-Employee Statistics	2017	SIGMOD	6.2966621e-05
5,076	IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy	2022	SIGMOD	6.2720607e-05
5,171	A Rigorous and Customizable Framework for Privacy	2012	PODS	6.2321934e-05
5,698	Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges	2017	SIGMOD	6.0140309e-05
6,440	Privacy-Aware Data Management in Information Networks	2011	SIGMOD	5.7674913e-05
6,516	Differential Privacy in the Wild: A tutorial on current practices & open challenges	2016	VLDB	5.7432938e-05
6,576	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.7255624e-05
6,787	PrivGene: Differentially Private Model Fitting Using Genetic Algorithms	2013	SIGMOD	5.6656994e-05
6,823	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD	5.656894e-05
7,463	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS	5.505863e-05
7,662	Approximate DBSCAN under Differential Privacy	2025	SIGMOD	5.4565877e-05
8,030	Differentially Private Data Release over Multiple Tables	2023	PODS	5.3871505e-05
8,500	DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy	2021	SIGMOD	5.3131213e-05
10,069	Sypse: Privacy-first Data Management through Pseudonymization and Partitioning	2021	CIDR	5.0742132e-05
10,703	Defense against Poisoning Attacks under Shuffle-DP	2026	SIGMOD	4.9605343e-05
10,896	Composition for Pufferfish Privacy	2026	VLDB	4.9605343e-05
11,281	SPECIAL: SynoPsis AssistEd Secure CollaboratIve AnaLytics	2025	VLDB	4.9605343e-05
11,370	Calibrating Noise for Group Privacy in Subsampled Mechanisms	2025	VLDB	4.9605343e-05
11,411	Balancing Privacy and Utility in Correlated Data: A Study of Bayesian Differential Privacy	2025	VLDB	4.9605343e-05
12,666	Publishing Microdata with a Robust Privacy Guarantee	2012	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
123	Revealing Information while Preserving Privacy	2003	PODS	0.00030654879
525	Practical Privacy: The SuLQ Framework	2005	PODS	0.00016875512
880	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00013249752
4,441	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS	6.5824511e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,062	Epistemic Privacy	2008	PODS
2	858	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD
3	7,626	Privacy Amplification by Sampling under User-level Differential Privacy	2024	SIGMOD
4	10,866	Measuring Database Unfairness via Dependency Quantification Under Differential Privacy	2026	VLDB
5	8,351	Continual Observation of Joins under Differential Privacy	2024	SIGMOD
6	6,516	Differential Privacy in the Wild: A tutorial on current practices & open challenges	2016	VLDB
7	5,698	Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges	2017	SIGMOD
8	1,792	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB
9	4,441	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS
10	6,576	Differential Privacy in Data Publication and Analysis	2012	SIGMOD