The Algorithmic Foundations of Differential Privacy
The DOI matches its Crossref record; 74 of the 75 references it cites were found in a registry or an index.
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. The Algorithmic Foundations of Differential Privacy starts out by motivating and discussing the meaning of differential privacy, and proceeds to explore the fundamental techniques for achieving differential privacy, and the 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 powerful computational results, there are still fundamental limitations. 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. The monograph then turns from fundamentals to applications other than query-release,…
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“DP [9, 16, 39, 49, 55] guarantees that any single data sample in a dataset has limited impact on the output.”
From When Machine Unlearning Jeopardizes Privacy (2021) · cites this paper as [16]
In the citing paper
“Differential privacy provides a promising lightweight privacy-preserving mechanism to guarantee a level of privacy disclosure for local datasets by adding random perturbations [42].”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [42]
Citations
Cites
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Self-citationDwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
Self-citationRandomized Response: A Survey Technique for Eliminating Evasive Answer Bias
Warner, S. L. (1965) · Journal of the American Statistical Association · doi:10.1080/01621459.1965.10480775 · Cited by 3,255
Robust De-anonymization of Large Sparse Datasets
Narayanan, A., & Shmatikov, V. (2008) · 2008 IEEE Symposium on Security and Privacy (sp 2008) · doi:10.1109/sp.2008.33 · Cited by 2,372
The Boosting Approach to Machine Learning: An Overview
Schapire, R. E. (2003) · Lecture Notes in Statistics · doi:10.1007/978-0-387-21579-2_9 · Cited by 2,003
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835
Self-citationA Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Towards Sharp Inapproximability For Any 2-CSP
Austrin, P. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.41 · Cited by 1,294
Homer, N., Szelinger, S., Redman, M., Duggan, D., Tembe, W., Muehling, J., Pearson, J. V., Stephan, D. A., Nelson, S. F., & Craig, D. W. (2008) · PLoS Genetics · doi:10.1371/journal.pgen.1000167 · Cited by 1,221
Privacy integrated queries: an extensible platform for privacy-preserving data analysis
McSherry, F. D. (2009) · Proceedings of the 2009 ACM SIGMOD International Conference on Management of data · doi:10.1145/1559845.1559850 · Cited by 1,124
(2011) · PubMed · Cited by 990
Revealing information while preserving privacy
Dinur, I., & Nissim, K. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773173 · Cited by 980
Smooth sensitivity and sampling in private data analysis
Nissim, K., Raskhodnikova, S., & Smith, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250803 · Cited by 974
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898
Practical privacy: the SuLQ framework
Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005) · Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1065167.1065184 · Cited by 797
Self-citationBoosting and Differential Privacy
Dwork, C., Rothblum, G. N., & Vadhan, S. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.12 · Cited by 784
Self-citationEfficient noise-tolerant learning from statistical queries
Kearns, M. (1998) · Journal of the ACM · doi:10.1145/293347.293351 · Cited by 665
Differential privacy and robust statistics
Dwork, C., & Lei, J. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536466 · Cited by 611
Self-citationDifferential privacy under continual observation
Dwork, C., Naor, M., Pitassi, T., & Rothblum, G. N. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806787 · Cited by 583
Self-citationA learning theory approach to non-interactive database privacy
Blum, A., Ligett, K., & Roth, A. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374464 · Cited by 505
Self-citationWeaving Technology and Policy Together to Maintain Confidentiality
Sweeney, L. (1997) · Journal of Law, Medicine & Ethics · doi:10.1111/j.1748-720x.1997.tb01885.x · Cited by 375
On the complexity of differentially private data release: efficient algorithms and hardness results
Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., & Vadhan, S. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536467 · Cited by 358
Self-citationPrivacy-Preserving Datamining on Vertically Partitioned Databases
Dwork, C., & Nissim, K. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28628-8_32 · Cited by 348
Self-citationA Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis
Hardt, M., & Rothblum, G. N. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.85 · Cited by 319
On the geometry of differential privacy
Hardt, M., & Talwar, K. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806786 · Cited by 314
The weighted majority algorithm
Littlestone, N., & Warmuth, M. K. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63487 · Cited by 295
A simple and practical algorithm for differentially private data release
Hardt, M., Ligett, K., & McSherry, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.4763 · Cited by 283
Ghosh, A., & Roth, A. (2011) · Proceedings of the 12th ACM conference on Electronic commerce · doi:10.1145/1993574.1993605 · Cited by 250
Self-citationInteractive privacy via the median mechanism
Roth, A., & Roughgarden, T. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806794 · Cited by 226
Self-citationLearning, Regret Minimization, and Equilibria
Blum, A., & Mansour, Y. (2007) · Algorithmic Game Theory · doi:10.1017/cbo9780511800481.006 · Cited by 180
Private Convex Empirical Risk Minimization and High-dimensional Regression
Kifer, D., Smith, A., & Thakurta, A. (2012) · Cited by 180
On significance of the least significant bits for differential privacy
Mironov, I. (2012) · Proceedings of the 2012 ACM conference on Computer and communications security · doi:10.1145/2382196.2382264 · Cited by 176
Analyze gauss: optimal bounds for privacy-preserving principal component analysis
Dwork, C., Talwar, K., Thakurta, A., & Zhang, L. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591883 · Cited by 173
Self-citationIterative Constructions and Private Data Release
Gupta, A., Roth, A., & Ullman, J. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-28914-9_19 · Cited by 164
Self-citationLocal Privacy, Data Processing Inequalities, and Statistical Minimax RatesPreprint
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.3203 · Cited by 150
Differentially Private Online LearningPreprint
Jain, P., Kothari, P. K., & Thakurta, A. (2012) · Cited by 149
Approximately optimal mechanism design via differential privacy
Kobbi Nissim, B., Smorodinsky, R., & Tennenholtz, M. (2012) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2090236.2090254 · Cited by 135
Mechanism Design via Machine Learning
Balcan, M.-F., & Blum, A. L. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.50 · Cited by 129
Pan-Private Streaming Algorithms
Dwork, C., Naor, M., Pitassi, T., Rothblum, G. N., & Yekhanin, S. (2010) · Cited by 127
Self-citationApproximately optimal auctions for selling privacy when costs are correlated with data
Fleischer, L. K., & Lyu, Y.-H. (2012) · Proceedings of the 13th ACM Conference on Electronic Commerce · doi:10.1145/2229012.2229054 · Cited by 122
Bounds on the Sample Complexity for Private Learning and Private Data Release
Beimel, A., Kasiviswanathan, S. P., & Kobbi Nissim, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11799-2_26 · Cited by 119
The Limits of Two-Party Differential Privacy
McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., & Vadhan, S. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.14 · Cited by 119
Dwork, C., & Naor, M. (2010) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.v2i1.585 · Cited by 115
Self-citationPrivately releasing conjunctions and the statistical query barrier
Gupta, A., Hardt, M., Roth, A., & Ullman, J. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993742 · Cited by 115
Self-citationMechanism design in large games: incentives and privacy
Kearns, M., Pai, M., Roth, A., & Ullman, J. (2014) · Proceedings of the 5th conference on Innovations in theoretical computer science · doi:10.1145/2554797.2554834 · Cited by 112
Self-citationDifferentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso
Thakurta, A., & Smith, A. (2013) · Conference on Learning Theory · Cited by 111
Near-optimal Differentially Private Principal Components
Chaudhuri, K., Sarwate, A. D., & Sinha, K. P. (2012) · Cited by 104
Truthful mechanisms for agents that value privacy
Chen, Y., Chong, S., Kash, I. A., Moran, T., & Vadhan, S. (2013) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/2482540.2482549 · Cited by 101
Lower Bounds in Differential Privacy
De, A. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-28914-9_18 · Cited by 98
The Geometry of Differential Privacy: the Sparse and Approximate Cases
Nikolov, A., Talwar, K., & Zhang, L. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1212.0297 · Cited by 94
Beyond worst-case analysis in private singular vector computation
Hardt, M., & Roth, A. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488650 · Cited by 90
Self-citationThe Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
Huang, Z., & Kannan, S. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.36 · Cited by 90
Private and Continual Release of Statistics
Chan, T.-H. H., Shi, E., & Song, D. X. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14162-1_34 · Cited by 87
Pai, M. M., & Roth, A. (2013) · ACM SIGecom Exchanges · doi:10.1145/2509013.2509016 · Cited by 83
Self-citationIs privacy compatible with truthfulness?
Xiao, D. (2013) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2422436.2422448 · Cited by 82
Sample Complexity Bounds for Differentially Private Learning.
Chaudhuri, K., & Hsu, D. (2011) · PubMed · Cited by 81
Private matchings and allocations
Hsu, J., Huang, Z., Roth, A., Roughgarden, T., & Wu, Z. S. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591826 · Cited by 80
Self-citationBeating randomized response on incoherent matrices
Hardt, M., & Roth, A. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2214088 · Cited by 78
Self-citationPan-private algorithms via statistics on sketches
Mir, D., Muthukrishnan, S., Nikolov, A., & Wright, R. N. (2011) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1989284.1989290 · Cited by 72
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations
Dwork, C., Nikolov, A., & Talwar, K. (2015) · Discrete & Computational Geometry · doi:10.1007/s00454-015-9678-x · Cited by 65
Self-citationPrivacy and coordination: computing on databases with endogenous participation
Ghosh, A., & Ligett, K. (2013) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/2482540.2482585 · Cited by 55
Asymptotically truthful equilibrium selection in large congestion games
Rogers, R., & Roth, A. (2014) · ACM Conference on Economics and Computation (EC) · doi:10.1145/2600057.2602856 · Cited by 52
Self-citationCharacterizing the sample complexity of private learners
Beimel, A., Nissim, K., & Stemmer, U. (2013) · Proceedings of the 4th conference on Innovations in Theoretical Computer Science · doi:10.1145/2422436.2422450 · Cited by 49
Answering n {2+o(1)} counting queries with differential privacy is hard
Ullman, J. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488653 · Cited by 49
Unconditional differentially private mechanisms for linear queries
Bhaskara, A., Dadush, D., Krishnaswamy, R., & Talwar, K. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2214089 · Cited by 43
Buying private data at auction: the sensitive surveyor's problem
Roth, A. (2012) · ACM SIGecom Exchanges · doi:10.1145/2325713.2325714 · Cited by 37
Self-citationThe Privacy of the Analyst and the Power of the State
Dwork, C., Naor, M., & Vadhan, S. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.87 · Cited by 36
Self-citationDifferential privacy for the analyst via private equilibrium computation
Hsu, J., Roth, A., & Ullman, J. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488651 · Cited by 27
Self-citationLimits of Computational Differential Privacy in the Client/Server Setting
Groce, A., Katz, J. I., & Yerukhimovich, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19571-6_25 · Cited by 25
Five golden rules: great theories of 20th-century mathematics--and why they matter
(1996) · Choice Reviews Online · doi:10.5860/choice.33-5154 · Cited by 23
Privacy Auctions for Recommender Systems
Dandekar, P., Fawaz, N., & Ioannidis, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-35311-6_23 · Cited by 18
Take it or Leave it: Running a Survey when Privacy Comes at a CostPreprint
Ligett, K., & Roth, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.4741 · Cited by 14
Self-citationDifferential Privacy and the Fat-Shattering Dimension of Linear Queries
Roth, A. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15369-3_51 · Cited by 11
Self-citationValiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Deep Learning with Differential Privacy
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978318 · Cited by 6,578
Federated learning: Challenges, methods, and future directions
Li, T., Sahu, A. K., Talwalkar, A., & Smith, V. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2975749 · Cited by 6,210
Practical Secure Aggregation for Privacy-Preserving Machine Learning
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., & Seth, K. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3133982 · Cited by 3,956
Traumatic brain injury: integrated approaches to improve prevention, clinical care, and research
Maas, A. I. R., Menon, D. K., Adelson, P. D., Andelic, N., Bell, M. J., Belli, A., Bragge, P., Brazinova, A., Büki, A., Chesnut, R. M., et al. (2017) · The Lancet Neurology · doi:10.1016/s1474-4422(17)30371-x · Cited by 2,609
Metadata
- Authors
- Dwork, C., & Roth, A.
- Affiliations
- Microsoft (United States) (US)
- University of Pennsylvania (US)
- Venue
- now publishers, Inc. eBooks
- Publisher
- now Publishers Inc
- Published
- 2013
- OpenAlex
- W2027595342
- Cited by
- 3,856
- References
- 75
- Citations by year
- 2026: 180 · 2025: 269 · 2024: 391 · 2023: 290 · 2022: 327 · 2021: 729 · 2020: 596 · 2019: 435 · 2018: 250 · 2017: 194 · 2016: 122 · 2015: 56 · 2014: 12 · 2013: 3
- FWCI
- 23.36
- Type
- book
- Language
- en
- Open access
- closed
- Locations
- now publishers, Inc. eBooks (publishedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Keywords
- differential privacy, privacy-preserving data analysis, computational complexity, mechanism design, distributed databases, data streams
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.