The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
The Algorithmic Foundations of Differential Privacy
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The text we found for this paper looks like another document, so the self-check wasn’t run.
Citations
Cites
Federated Optimization:Distributed Optimization Beyond the Datacenter
Konečný, J., McMahan, B., & Ramage, D. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.03575 · Cited by 544
Federated Learning: Collaborative Machine Learning without Centralized Training Data
A, A. V., Binny, S., R, J. T., Raj, N., & Thomas, V. (2022) · international journal of engineering technology and management sciences · doi:10.46647/ijetms.2022.v06i05.052 · Cited by 489
Privacy-Preserving Machine Learning: Methods, Challenges and DirectionsPreprint
Xu, R., Baracaldo, N., & Joshi, J. B. D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.04417 · Cited by 297
Learning to Protect Communications with Adversarial Neural Cryptography
Abadi, M., & Andersen, D. G. (2016) · arXiv · doi:10.48550/arxiv.1610.06918 · Cited by 182
Chiffrement totalement homomorphe pour l'apprentissage automatique
Minelli, M. (2018) · HAL (Le Centre pour la Communication Scientifique Directe) · Cited by 14
- Data Anonymization Techniques
Frank, M. J. (2013) · Auerbach Publications eBooks · doi:10.1201/b13097-20 · Cited by 2
Research works printed but not linked: 83
- Arora, 2012, The multiplicative weights update method: A meta-algorithm and applications, Theory of Computing, 8, 121, 10.4086/toc.2012.v008a006 · doi:10.4086/toc.2012.v008a006
- Balcan, 2005, Mechanism design via machine learning, Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, 605
- Beimel, 2010, Bounds on the sample complexity for private learning and private data release, Theory of Cryptography, 437
- Beimel, 2013, Characterizing the sample complexity of private learners, Proceedings of the Conference on Innovations in Theoretical Computer Science, 97
- Bhaskara, 2012, 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, 1269
- Blum, 2005, Practical privacy: the SuLQ framework, Principles of Database Systems, 128
- Blum, Practical privacy: the sulq framework, Principles of Database Systems
- Blum, 2008, A learning theory approach to noninteractive database privacy, Symposium on Theory of Computing, 609, 10.1145/1374376.1374464 · DOI · Paper page
- Blum, 2007, Learning, regret minimization, and equilibria
- Casti, Five Golden Rules: Great Theories of 20th-Century Mathematics and Why They Matter
- Hubert, 2010, Private and continual release of statistics, Automata, Languages and Programming, 405, 10.1007/978-3-642-14162-1_34 · DOI
- Chaudhuri, Sample complexity bounds for differentially private learning, Proceedings of the Annual Conference on Learning Theory (COLT 2011)
- Chaudhuri, Differentially private empirical risk minimization, Journal of machine learning research: JMLR
- Chaudhuri, 2012, Near-optimal differentially private principal components, Advances in Neural Information Processing Systems 25, 998
- Chen, 2013, Truthful mechanisms for agents that value privacy, Association for Computing Machinery Conference on Electronic Commerce
- Dandekar, 2012, Privacy auctions for recommender systems, Internet and Network Economics, 309, 10.1007/978-3-642-35311-6_23 · DOI
- De, 2012, Lower bounds in differential privacy, Theory of Cryptography Conference, 321
- Dinur, 2003, Revealing information while preserving privacy, Proceedings of the Association for Computing Machinery SIGACT- SIGMOD-SIGART Symposium on Principles of Database Systems, 202
- Duchi, 2013, Local privacy and statistical minimax rates, arXiv preprint arXiv:1302.3203 · arXiv
- Dwork, 2006, Differential privacy, Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP)(2), 1
- Dwork, 2006, Our data, ourselves: Privacy via distributed noise generation, EUROCRYPT, 486
- Dwork, Differential privacy and robust statistics, Proceedings of the 2009 International Association for Computing Machinery Symposium on Theory of Computing (STOC)
- Dwork, 2006, Calibrating noise to sensitivity in private data analysis, Theory of Cryptography Conference ’06, 265
- Dwork, 2007, The price of privacy and the limits of lp decoding, Proceedings of the Association for Computing Machinery Symposium on Theory of Computing, 85
- Dwork, 2010, On the difficulties of disclosure prevention in statistical databases or the case for differential privacy, Journal of Privacy and Confidentiality, 10.29012/jpc.v2i1.585 · DOI
- Dwork, 2010, Differential privacy under continual observation, Proceedings of the Association for Computing Machinery Symposium on Theory of Computing, 715
- Dwork, Pan-private streaming algorithms, Proceedings of International Conference on Super Computing
- Dwork, 2009, On the complexity of differentially private data release: Efficient algorithms and hardness results, Symposium on Theory of Computing ’09, 381, 10.1145/1536414.1536467 · DOI · Paper page
- Dwork, The privacy of the analyst and the power of the state, Foundations of Computer Science
- Dwork, Efficient algorithms for privately releasing marginals via convex relaxations, Proceedings of the Annual Symposium on Computational Geometry (SoCG)
- Dwork, 2004, Privacy-preserving datamining on vertically partitioned databases, Proceedings of Cryptology 2004, 3152, 528, 10.1007/978-3-540-28628-8_32 · DOI · Paper page
- Dwork, 2010, Boosting and differential privacy, Foundations of Computer Science, 51
- Dwork, Analyze gauss: Optimal bounds for privacy-preserving pca, Symposium on Theory of Computing
- Fleischer, 2012, Approximately optimal auctions for selling privacy when costs are correlated with data, Association for Computing Machinery Conference on Electronic Commerce, 568
- Ghosh, 2013, Privacy and coordination: Computing on databases with endogenous participation, Proceedings of the fourteenth ACM conference on Electronic commerce (EC), 543, 10.1145/2482540.2482585 · DOI
- Ghosh, Selling privacy at auction, Association for Computing Machinery Conference on Electronic Commerce
- Groce, Limits of computational differential privacy in the client/server setting, Proceedings of the Theory of Cryptography Conference
- Gupta, 2011, Privately releasing conjunctions and the statistical query barrier, Symposium on Theory of Computing ’11, 803
- Gupta, 2012, Iterative constructions and private data release, Theory of Cryptography Conference, 339
- Hastad, A pseudorandom generator from any one-way function, SIAM Journal of Computing
- Hardt, 2012, A simple and practical algorithm for differentially private data release, Advances in Neural Information Processing Systems 25, 2348
- Hardt, 2012, Beating randomized response on incoherent matrices, Proceedings of the Symposium on Theory of Computing, 1255, 10.1145/2213977.2214088 · DOI
- Hardt, Beyond worst-case analysis in private singular vector computation, Proceedings of the Symposium on Theory of Computing
- Hardt, 2010, A multiplicative weights mechanism for privacy-preserving data analysis, Foundations of Computer Science, 61
- Hardt, 2010, On the geometry of differential privacy, Proceedings of the Association for Computing Machinery Symposium on Theory of Computing, 705
- Homer, Resolving individuals contributing trace amounts of dna to highly complex mixtures using high- density snp genotyping microarrays, PLoS Genet
- Hsu, 2013, arXiv, 1311
- Hsu, 2013, Differential privacy for the analyst via private equilibrium computation, Proceedings of the Association for Computing Machinery Symposium on Theory of Computing (STOC), 341
- Huang, 2012, The exponential mechanism for so cial welfare: Private, truthful, and nearly optimal, IEEE Annual Symposium on the Foundations of Computer Science (FOCS), 140
- Jain, Differentially private online learning, Journal of Machine Learning Research — Proceedings Track
- Kapralov, On differentially private low rank approximation, 10.1137/1.9781611973105.101 · DOI
- Kearns, 1998, Efficient noise-tolerant learning from statistical queries, Journal of the Association for Computing Machinery (JAssociation for Computing Machinery), 45, 983, 10.1145/293347.293351 · DOI · Paper page
- Kearns, 2014, Mechanism design in large games: Incentives and privacy, Proceedings of the 5th conference on Innovations in theoretical computer science (ITCS)
- Kifer, Private convex empirical risk minimization and high-dimensional regression, Journal of Machine Learning Research
- Ligett, 2012, Take it or leave it: Running a survey when privacy comes at a cost, Internet and Network Economics, 378, 10.1007/978-3-642-35311-6_28 · DOI
- Littlestone, 1989, The weighted majority algorithm, Annual Symposium on Foundations of Computer Science, 1989, 256
- McGregor, 2010, The limits of two-party differential privacy, Foundations of Computer Science, 81
- McSherry, 2007, Mechanism design via differential privacy, Foundations of Computer Science, 94
- McSherry, 2007, Mechanism design via differential privacy, Foundations of Computer Science, 94
- Mir, 2011, Pan-private algorithms via statistics on sketches, Proceedings of the Association for Computing Machinery SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 37, 10.1145/1989284.1989290 · DOI
- Mironov, On significance of the least significant bits for differential privacy, 10.1145/2382196.2382264 · DOI · Paper page
- Mironov, 2009, Computational differential privacy, Proceedings of CRYPTOLOGY, 126
- Narayanan, Robust de-anonymization of large sparse datasets (how to break anonymity of the netflix prize dataset), Proceedings of IEEE Symposium on Security and Privacy
- Nikolov, 2013, The geometry of differential privacy: the sparse and approximate cases, Symposium on Theory of Computing
- Nissim, 2012, Privacy-aware mechanism design, Association for Computing Machinery Conference on Electronic Commerce, 774
- Nissim, 2007, Smooth sensitivity and sampling in private data analysis, Proceedings of the Association for Computing Machinery Symposium on Theory of Computing, 75
- Nissim, 2012, Approximately optimal mechanism design via differential privacy, Innovations in Theoretical Computer Science, 203, 10.1145/2090236.2090254 · DOI
- Pai, 2013, Privacy and mechanism design, SIGecom Exchanges, 10.1145/2509013.2509016 · DOI
- Rogers, 2013, arXiv, 1311
- Roth, 2010, Differential privacy and the fat-shattering dimension of linear queries, Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 683, 10.1007/978-3-642-15369-3_51 · DOI
- Roth, 2012, Buying private data at auction: the sensitive surveyor’s problem, Association for Computing Machinery SIGecom Exchanges, 11, 1, 10.1145/2325713.2325714 · DOI
- Roth, 2010, Interactive privacy via the median mechanism, Symposium on Theory of Computing ’10, 765
- Roth, Conducting truthful surveys, cheaply, Proceedings of the ACM Conference on Electronic Commerce
- Rubinstein, 2009, arXiv, 0911
- Schapire, 2003, The boosting approach to machine learning: An overview, 10.1007/978-0-387-21579-2_9 · DOI · Paper page
- Schapire, 1999, Improved boosting algorithms using confidence-rated predictions, Machine Learning, 39, 297, 10.1023/A:1007614523901 · DOI · Paper page
- Schapire, Boosting: Foundations and Algorithms
- Smith, Differentially private feature selection via stability arguments, and the robustness of the lasso, Proceedings of Conference on Learning Theory
- Sweeney, 1997, Weaving technology and policy together to maintain confidentiality, Journal of Law, Medicines Ethics, 25, 98, 10.1111/j.1748-720X.1997.tb01885.x · DOI · Paper page
- Ullman, 2013, Answering n{2+o(1)} counting queries with differential privacy is hard, Symposium on Theory of Computing, 361
- Valiant, 1984, A theory of the learnable, Communications of the Association for Computing Machinery, 27, 1134, 10.1145/1968.1972 · DOI · Paper page
- Warner, 1965, Randomized response: A survey technique for eliminating evasive answer bias, Journal of the American Statistical Association, 60, 63, 10.1080/01621459.1965.10480775 · DOI · Paper page
- Xiao, 2013, Is privacy compatible with truthfulness, Proceedings of the Conference on Innovations in Theoretical Computer Science, 67
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
Communication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215
“While federated learning offers many practical privacy benefits, providing stronger guarantees via differential privacy [14, 13, 1], secure multi-party computation [18], or their combination is an interesting direction for future work.”
BackgroundTraumatic 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
Federated Learning With Differential Privacy: Algorithms and Performance Analysis
Wei, K., Li, J., Ding, M., Ma, C., Yang, H. H., Farokhi, F., Jin, S., Quek, T. Q. S., & Vincent Poor, H. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2020.2988575 · Cited by 2,400
Metadata
- Authors
- Dwork, C., & Roth, A.
- Affiliations
- Microsoft (United States) (US)
- University of Pennsylvania (US)
- Venue
- Foundations and Trends® in Theoretical Computer Science
- Publisher
- Emerald
- Published
- 2014-08-11
- Volume
- 9
- Issue
- 3-4
- Pages
- 211-487
- ISSN
- 1551-305X (ISSN-L)
- 1551-3068
- OpenAlex
- W4205228770
- Cited by
- 5,557
- References
- 6
- Citations by year
- 2026: 887 · 2025: 822 · 2024: 755 · 2023: 706 · 2022: 602 · 2021: 562 · 2020: 473 · 2019: 297 · 2018: 194 · 2017: 150 · 2016: 73 · 2015: 28 · 2014: 6
- FWCI
- 85.31
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Foundations and Trends® in Theoretical Computer Science (publishedVersion)
- ELARTU (Ternopil National Technical University) (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, privacy definitions, 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.