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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Algorithmic Foundations of Differential Privacy. https://app.cochat.ai/papers/10.1561/9781601988195
- The paper
- Dwork, C., & Roth, A. (2013). The Algorithmic Foundations of Differential Privacy. now publishers, Inc. eBooks. https://doi.org/10.1561/9781601988195
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.