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
Items 1,001–1,041 of 1,041
New SVD-based collaborative filtering algorithms with differential privacy
Xian, Z., Li, Q., Huang, X., & Li, L. (2017) · Journal of Intelligent & Fuzzy Systems · doi:10.3233/jifs-162053 · Cited by 35
Algorithmic and Ethical Aspects of Recommender Systems in e-Commerce
Paraschakis, D. (2018) · doi:10.24834/2043/24268 · Cited by 35
Federated learning vulnerabilities, threats and defenses: A systematic review and future directions
Almutairi, S., & Barnawi, A. (2023) · Internet of Things · doi:10.1016/j.iot.2023.100947 · Cited by 35
Key ethical challenges in the European medical information framework
Floridi, L., Luetge, C., Pagallo, U., Schafer, B., Valcke, P., Vayena, E., Addison, J., Hughes, N., Lea, N., Sage, C., et al. (2019) · Minds and Machines · doi:10.1007/s11023-018-9467-4 · Cited by 33
Rajotte, J.-F., Mukherjee, S., Robinson, C., Ortiz, A., West, C., Ferres, J. M. L., & Ng, R. T. (2021) · Proceedings of the Conference on Information Technology for Social Good · doi:10.1145/3462203.3475875 · Cited by 34
A critique of the regulation of data science in healthcare research in the European Union
Rumbold, J. M. M., & Pierscionek, B. K. (2017) · BMC Medical Ethics · doi:10.1186/s12910-017-0184-y · Cited by 33
Practical Attribute Reconstruction Attack Against Federated Learning
Chen, C., Lyu, L., Yu, H., & Chen, G. (2024) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2022.3159236 · Cited by 30
Learning Privately over Distributed Features: An ADMM Sharing Approach
Hu, Y., Liu, P., Kong, L., & Niu, D. (2019) · arXiv · doi:10.48550/arxiv.1907.07735 · Cited by 30
The Upworthy Research Archive, a time series of 32,487 experiments in U.S. media
Matias, J. N., Munger, K., Le Quere, M. A., & Ebersole, C. (2021) · Scientific Data · doi:10.1038/s41597-021-00934-7 · Cited by 29
Global and Local Differential Privacy for Collaborative Bandits
Wang, H., Zhao, Q., Wu, Q., Chopra, S., Khaitan, A., & Wang, H. (2020) · Fourteenth ACM Conference on Recommender Systems · doi:10.1145/3383313.3412254 · Cited by 28
Secure Federated Submodel Learning
Niu, C., Wu, F., Tang, S., Hua, L., Jia, R., Lv, C., Wu, Z., & Chen, G. (2019) · arXiv · doi:10.48550/arxiv.1911.02254 · Cited by 28
Ibitoye, O., Shafiq, M. O., & Matrawy, A. (2022) · Computers & Security · doi:10.1016/j.cose.2022.102631 · Cited by 27
On the Power of Multiple Anonymous Messages
Ghazi, B., Golowich, N., Kumar, R., Pagh, R., & Velingker, A. (2019) · arXiv · doi:10.48550/arxiv.1908.11358 · Cited by 26
Machine Unlearning via Algorithmic Stability
Ullah, E., Mai, T., Rao, A., Rossi, R., & Arora, R. (2021) · arXiv · doi:10.48550/arxiv.2102.13179 · Cited by 26
Integrating Technical and Legal Concepts of Privacy
Sokolovska, A., & Kocarev, L. (2018) · IEEE Access · doi:10.1109/access.2018.2836184 · Cited by 24
An adaptive robust defending algorithm against backdoor attacks in federated learning
Wang, Y., Zhai, D.-H., He, Y., & Xia, Y. (2023) · Future Generation Computer Systems · doi:10.1016/j.future.2023.01.026 · Cited by 25
“Privacy-preserving quantum machine learning using differential privacy,”
Senekane, M., Mafu, M., & Taele, B. M. (2017) · 2017 IEEE AFRICON · doi:10.1109/afrcon.2017.8095692 · Cited by 25
Differentially-Private "Draw and Discard" Machine Learning
Pihur, V., Korolova, A., Liu, F., Sankuratripati, S., Yung, M., Huang, D., & Zeng, R. (2018) · arXiv · doi:10.48550/arxiv.1807.04369 · Cited by 25
Generalized genomic data sharing for differentially private federated learning
Aziz, M. M. A., Anjum, M. M., Mohammed, N., & Jiang, X. (2022) · Journal of Biomedical Informatics · doi:10.1016/j.jbi.2022.104113 · Cited by 24
Differential Privacy Defenses and Sampling Attacks for Membership Inference
Rahimian, S., Orekondy, T., & Fritz, M. (2021) · Proceedings of the 14th ACM Workshop on Artificial Intelligence and Security · doi:10.1145/3474369.3486876 · Cited by 24
A comprehensive survey and taxonomy on privacy-preserving deep learning
Tran, A.-T., Luong, T.-D., & Huynh, V.-N. (2024) · Neurocomputing · doi:10.1016/j.neucom.2024.127345 · Cited by 21
Differentially Private Federated Learningfor Anomaly Detection in eHealth Networks
Cholakoska, A., Pfitzner, B., Gjoreski, H., Rakovic, V., Arnrich, B., & Kalendar, M. (2021) · Adjunct Proceedings of the 2021 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2021 ACM International Symposium on Wearable Computers · doi:10.1145/3460418.3479365 · Cited by 20
On the Detection of Shilling Attacks in Federated Collaborative Filtering
Jiang, Y., Zhou, Y., Wu, D., Li, C., & Wang, Y. (2020) · 2020 International Symposium on Reliable Distributed Systems (SRDS) · doi:10.1109/srds51746.2020.00026 · Cited by 22
Privacy Preserving Time-Series Forecasting of User Health Data Streams
Imtiaz, S., Horchidan, S.-F., Abbas, Z., Arsalan, M., Chaudhry, H. N., & Vlassov, V. (2020) · 2020 IEEE International Conference on Big Data (Big Data) · doi:10.1109/bigdata50022.2020.9378186 · Cited by 15
You, F., Yuan, X., Ni, W., & Jamalipour, A. (2025) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2024.3499342 · Cited by 15
Differentially Private Knowledge Distillation for Mobile Analytics
Lyu, L., & Chen, C.-H. (2020) · Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval · doi:10.1145/3397271.3401259 · Cited by 14
Yang, J., Fu, C., & Lu, H. (2021) · Information Sciences · doi:10.1016/j.ins.2021.02.028 · Cited by 14
Data Poisoning Attacks against Differentially Private Recommender Systems
Wadhwa, S., Agrawal, S., Chaudhari, H., Sharma, D., & Achan, K. (2020) · Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval · doi:10.1145/3397271.3401301 · Cited by 11
Towards Quantifying the Carbon Emissions of Differentially Private Machine Learning
Naidu, R., Diddee, H., Mulay, A., Vardhan, A., Ramesh, K., & Zamzam, A. (2021) · arXiv · doi:10.48550/arxiv.2107.06946 · Cited by 10
A Privacy-Preserving Querying Mechanism with High Utility for Electric Vehicles
Atmaca, U. I., Biswas, S., Maple, C., & Palamidessi, C. (2024) · IEEE Open Journal of Vehicular Technology · doi:10.1109/ojvt.2024.3360302 · Cited by 9
DeepObliviate: A Powerful Charm for Erasing Data Residual Memory in Deep Neural Networks
He, Y., Meng, G., Chen, K., He, J., & Hu, X. (2021) · arXiv · doi:10.48550/arxiv.2105.06209 · Cited by 9
Angelopoulos, A. N., Bates, S., Zrnic, T., & Jordan, M. I. (2022) · Harvard Data Science Review · doi:10.1162/99608f92.16c71dad · Cited by 8
Li, X., Wang, Y., Song, J., Liu, Y., Zhang, X., Zhou, K., & Li, C. (2020) · World Wide Web · doi:10.1007/s11280-019-00769-8 · Cited by 7
Interpretable and Differentially Private Predictions
Harder, F., Bauer, M., & Park, M. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i04.5827 · Cited by 6
Fairness-aware Differentially Private Collaborative Filtering
Yang, Z., Ge, Y., Su, C., Wang, D., Zhao, X., & Ying, Y. (2023) · Companion Proceedings of the ACM Web Conference 2023 · doi:10.1145/3543873.3587577 · Cited by 6
FedVPS: Federated Learning for Privacy and Security of Internet of Vehicles on Non-IID Data
Hangdong, K., Bo, M., Darong, H., & Zhaoyang, D. (2023) · 2023 IEEE 12th Data Driven Control and Learning Systems Conference (DDCLS) · doi:10.1109/ddcls58216.2023.10166791 · Cited by 6
Sequential Trajectory Data Publishing With Adaptive Grid-Based Weighted Differential Privacy
Xie, G., Xu, H., Xu, J., Zhao, S., Li, Y., Wang, C.-D., Hu, X., & Tian, Y. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3449433 · Cited by 6
Graves, L., Nagisetty, V., & Ganesh, V. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i13.17371 · Cited by 5
Automatic Discovery of Privacy–Utility Pareto Fronts
Avent, B., González, J., Diethe, T., Paleyes, A., & Balle, B. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2020-0060 · Cited by 3
Why do classifier accuracies show linear trends under distribution shift?
Mania, H., & Sra, S. (2020) · arXiv · doi:10.48550/arxiv.2012.15483 · Cited by 3
Segar, N., & Vijayan, V. (2026) · Frontiers in Artificial Intelligence · doi:10.3389/frai.2026.1804943 · Cited by 5
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.