The Algorithmic Foundations of Differential Privacy

Cynthia Dwork; Aaron Roth

doi:10.1561/0400000042

journal article Aug 11, 2014

The Algorithmic Foundations of Differential Privacy

Cynthia Dwork Aaron Roth

Foundations and Trends® in Theoretical Computer Science Vol. 9 No. 3-4 pp. 211-487 · Emerald

View at Publisher Save 10.1561/0400000042

Abstract

The problem of privacy-preserving data analysis has a long history spanning multiple disciplines. As electronic data about individuals becomes increasingly detailed, and as technology enables ever more powerful collection and curation of these data, the need increases for a robust, meaningful, and mathematically rigorous definition of privacy, together with a computationally rich class of algorithms that satisfy this definition. Differential Privacy is such a definition.
After motivating and discussing the meaning of differential privacy, the preponderance of this monograph is devoted to fundamental techniques for achieving differential privacy, and application of these techniques in creative combinations, using the query-release problem as an ongoing example. A key point is that, by rethinking the computational goal, one can often obtain far better results than would be achieved by methodically replacing each step of a non-private computation with a differentially private implementation. Despite some astonishingly powerful computational results, there are still fundamental limitations — not just on what can be achieved with differential privacy but on what can be achieved with any method that protects against a complete breakdown in privacy. Virtually all the algorithms discussed herein maintain differential privacy against adversaries of arbitrary computational power. Certain algorithms are computationally intensive, others are efficient. Computational complexity for the adversary and the algorithm are both discussed.
We then turn from fundamentals to applications other than queryrelease, discussing differentially private methods for mechanism design and machine learning. The vast majority of the literature on differentially private algorithms considers a single, static, database that is subject to many analyses. Differential privacy in other models, including distributed databases and computations on data streams is discussed.
Finally, we note that this work is meant as a thorough introduction to the problems and techniques of differential privacy, but is not intended to be an exhaustive survey — there is by now a vast amount of work in differential privacy, and we can cover only a small portion of it.

Topics

No keywords indexed for this article. Browse by subject →

References

85

[1]

Arora "The multiplicative weights update method: A meta-algorithm and applications" Theory of Computing (2012) 10.4086/toc.2012.v008a006

[2]

Balcan "Mechanism design via machine learning" Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on (2005)

[3]

Beimel "Bounds on the sample complexity for private learning and private data release" Theory of Cryptography (2010)

[4]

Beimel "Characterizing the sample complexity of private learners" Proceedings of the Conference on Innovations in Theoretical Computer Science (2013)

[5]

Bhaskara "Unconditional differentially private mechanisms for linear queries" Proceedings of the Symposium on Theory of Computing Conference, Symposium on Theory of Computing, New York, NY, USA, May 19-22, 2012 (2012)

[6]

Blum "Practical privacy: the SuLQ framework" Principles of Database Systems (2005)

[7]

Blum "Practical privacy: the sulq framework" Principles of Database Systems

[8]

Blum "A learning theory approach to noninteractive database privacy" Symposium on Theory of Computing (2008) 10.1145/1374376.1374464

[9]

Blum Learning, regret minimization, and equilibria (2007)

[10]

Casti Five Golden Rules: Great Theories of 20th-Century Mathematics and Why They Matter

[11]

Hubert "Private and continual release of statistics" Automata, Languages and Programming (2010) 10.1007/978-3-642-14162-1_34

[12]

Chaudhuri "Sample complexity bounds for differentially private learning" Proceedings of the Annual Conference on Learning Theory (COLT 2011)

[13]

Chaudhuri "Differentially private empirical risk minimization" Journal of machine learning research: JMLR

[14]

Chaudhuri "Near-optimal differentially private principal components" Advances in Neural Information Processing Systems 25 (2012)

[15]

Chen "Truthful mechanisms for agents that value privacy" Association for Computing Machinery Conference on Electronic Commerce (2013)

[16]

Dandekar "Privacy auctions for recommender systems" Internet and Network Economics (2012) 10.1007/978-3-642-35311-6_23

[17]

De "Lower bounds in differential privacy" Theory of Cryptography Conference (2012)

[18]

Dinur "Revealing information while preserving privacy" Proceedings of the Association for Computing Machinery SIGACT- SIGMOD-SIGART Symposium on Principles of Database Systems (2003)

[19]

Duchi "Local privacy and statistical minimax rates" arXiv preprint arXiv:1302.3203 (2013)

[20]

Dwork "Differential privacy" Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP)(2) (2006)

[21]

Dwork "Our data, ourselves: Privacy via distributed noise generation" EUROCRYPT (2006)

[22]

Dwork "Differential privacy and robust statistics" Proceedings of the 2009 International Association for Computing Machinery Symposium on Theory of Computing (STOC)

[23]

Dwork "Calibrating noise to sensitivity in private data analysis" Theory of Cryptography Conference ’06 (2006)

[24]

Dwork "The price of privacy and the limits of lp decoding" Proceedings of the Association for Computing Machinery Symposium on Theory of Computing (2007)

[25]

Dwork "On the difficulties of disclosure prevention in statistical databases or the case for differential privacy" Journal of Privacy and Confidentiality (2010) 10.29012/jpc.v2i1.585

[26]

Dwork "Differential privacy under continual observation" Proceedings of the Association for Computing Machinery Symposium on Theory of Computing (2010)

[27]

Dwork "Pan-private streaming algorithms" Proceedings of International Conference on Super Computing

[28]

Dwork "On the complexity of differentially private data release: Efficient algorithms and hardness results" Symposium on Theory of Computing ’09 (2009) 10.1145/1536414.1536467

[29]

Dwork "The privacy of the analyst and the power of the state" Foundations of Computer Science

[30]

Dwork "Efficient algorithms for privately releasing marginals via convex relaxations" Proceedings of the Annual Symposium on Computational Geometry (SoCG)

[31]

Dwork "Privacy-preserving datamining on vertically partitioned databases" Proceedings of Cryptology 2004 (2004) 10.1007/978-3-540-28628-8_32

[32]

Dwork "Boosting and differential privacy" Foundations of Computer Science (2010)

[33]

Dwork "Analyze gauss: Optimal bounds for privacy-preserving pca" Symposium on Theory of Computing

[34]

Fleischer "Approximately optimal auctions for selling privacy when costs are correlated with data" Association for Computing Machinery Conference on Electronic Commerce (2012)

[35]

Ghosh "Privacy and coordination: Computing on databases with endogenous participation" Proceedings of the fourteenth ACM conference on Electronic commerce (EC) (2013) 10.1145/2482540.2482585

[36]

Ghosh "Selling privacy at auction" Association for Computing Machinery Conference on Electronic Commerce

[37]

Groce "Limits of computational differential privacy in the client/server setting" Proceedings of the Theory of Cryptography Conference

[38]

Gupta "Privately releasing conjunctions and the statistical query barrier" Symposium on Theory of Computing ’11 (2011)

[39]

Gupta "Iterative constructions and private data release" Theory of Cryptography Conference (2012)

[40]

Hastad "A pseudorandom generator from any one-way function" SIAM Journal of Computing

[41]

Hardt "A simple and practical algorithm for differentially private data release" Advances in Neural Information Processing Systems 25 (2012)

[42]

Hardt "Beating randomized response on incoherent matrices" Proceedings of the Symposium on Theory of Computing (2012) 10.1145/2213977.2214088

[43]

Hardt "Beyond worst-case analysis in private singular vector computation" Proceedings of the Symposium on Theory of Computing

[44]

Hardt "A multiplicative weights mechanism for privacy-preserving data analysis" Foundations of Computer Science (2010)

[45]

Hardt "On the geometry of differential privacy" Proceedings of the Association for Computing Machinery Symposium on Theory of Computing (2010)

[46]

Homer "Resolving individuals contributing trace amounts of dna to highly complex mixtures using high- density snp genotyping microarrays" PLoS Genet

[47]

Hsu (2013)

[48]

Hsu "Differential privacy for the analyst via private equilibrium computation" Proceedings of the Association for Computing Machinery Symposium on Theory of Computing (STOC) (2013)

[49]

Huang "The exponential mechanism for so cial welfare: Private, truthful, and nearly optimal" IEEE Annual Symposium on the Foundations of Computer Science (FOCS) (2012)

[50]

Jain "Differentially private online learning" Journal of Machine Learning Research — Proceedings Track

Showing 50 of 85 references

Cited By

3,478

Differentially Private Sliced Inverse Regression in the Federated Paradigm

Shuaida He, Jiarui Zhang · 2026

Journal of the American Statistical...

The use of differential privacy for privacy-preserving record linkage: Protecting the bits but not the people

Sumayya Ziyad, Peter Christen · 2026

Information Systems

Federated machine learning for cross-bank credit card fraud detection: A privacy-preserving framework

Dhanveer Singh, Raja Chattopadhyay · 2026

African Journal of Science, Technol...

Outfitting the Quest for Spatial Spread of Infections: A Review of Mobility Datasets for Population Health Modelling

Nodira Tillayeva, Naoki Tamura · 2026

Infectious Disease Modelling

Versatile differentially private learning for general loss functions

Qilong Lu, Song Xi Chen · 2026

The Annals of Statistics

FedASU: Attention-guided sensitivity unlearning framework for multi-scenario federated graph unlearning

Jiaqi Chao, Xunkai Li · 2026

Expert Systems with Applications

Privacy Loss of Noise Perturbation via Concentration Analysis of A Product Measure

Shuainan Liu, Tianxi Ji · 2026

Proceedings of the ACM on Managemen...

Efficient and Effective Biclique Counting with Local Differential Privacy

Yizhang He, Wenjie Zhang · 2026

Proceedings of the ACM on Managemen...

A core safety substrate for human-centered AI systems: privacy-preserving behavioral risk signaling without persistent identity

Rasim Cetin · 2026

AI and Ethics

Adaptive Sensitivity-Aware Differential Privacy Accounting for Federated Smart-Meter Theft Detection

Diego Labate, Dipanwita Thakur · 2026

Big Data and Cognitive Computing

Redefining Surgical Health Economics: The Potential of TabPFN for Real-Time Precision Modelling

Enoch Chi Ngai Lim, Chi Eung Danforn Lim · 2025

Journal of Computer and Communicati...

Enhancing personalized model construction and privacy protection in federated learning with generative adversarial networks and parameter sparsification

Zhongyuan Jing, Ruyan Wang · 2025

The Journal of Supercomputing

Security and Privacy Challenges of Large Language Models: A Survey

Badhan Chandra Das, M. Hadi Amini · 2025

ACM Computing Surveys

Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic Survey

Lea Demelius, Roman Kern · 2025

ACM Computing Surveys

SPAS: Continuous Release of Data Streams under w-Event Differential Privacy

Xiaochen Li, Tianyu Li · 2025

Proceedings of the ACM on Managemen...

RM 2 : Answer Counting Queries Efficiently under Shuffle Differential Privacy

Qiyao Luo, Jianzhe Yu · 2025

Proceedings of the ACM on Managemen...

DA-FL: Blockchain Empowered Secure and Private Federated Learning With Anonymous Authentication

Hu Xiong, Yaxin Zhao · 2025

IEEE Transactions on Reliability

Make your data fair: A survey of data preprocessing techniques that address biases in data towards fair AI

Amal Tawakuli, Thomas Engel · 2025

Journal of Engineering Research

Hardening LLM Fine-Tuning: From Differentially Private Data Selection to Trustworthy Model Quantization

Zehang Deng, Ruoxi Sun · 2025

IEEE Transactions on Information Fo...

N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics

Yihua Hu, Hao Ding · 2025

Proceedings of the ACM on Managemen...

Metrics

3,478

Citations

85

References

Details

Published: Aug 11, 2014
Vol/Issue: 9(3-4)
Pages: 211-487

Authors

Microsoft Research

University of Pennsylvania

Cite This Article

Cynthia Dwork, Aaron Roth (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4), 211-487. https://doi.org/10.1561/0400000042

The Algorithmic Foundations of Differential Privacy

You May Also Like