mlsanityData to 7 Oct 2026

The Composition Theorem for Differential Privacy

arXiv 1311.0776 ↗First posted 4 Nov 2013cs.DS cs.CR cs.ITcited by 290

Not on the map. Why?

Cited by 33 in LLM safety and security, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Sequential querying of differentially private mechanisms degrades the overall privacy level. In this paper, we answer the fundamental question of characterizing the level of overall privacy degradation as a function of the number of queries and the privacy levels maintained by each privatization mechanism. Our solution is complete: we prove an upper bound on the overall privacy level and construct a sequence of privatization mechanisms that achieves this bound. The key innovation is the introduction of an operational interpretation of differential privacy (involving hypothesis testing) and the use of new data processing inequalities. Our result improves over the state-of-the-art, and has immediate applications in several problems studied in the literature including differentially private multi-party computation.

Key facts. Cited by 290 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Nov 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 38; 2022: 60; 2023: 49; 2024: 55; 2025: 46; 2026: 42.

290 papers.

Sort:

By area:

  1. 2021Membership Inference Attacks From First Principlescited by 839
  2. 2021Enhanced Membership Inference Attacks against Machine Learning Modelscited by 237
  3. 2021Adversary Instantiation: Lower Bounds for Differentially Private Machine Learningcited by 193
  4. 2021Numerical Composition of Differential Privacycited by 174
  5. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 150
  6. 2022Reconstructing Training Data with Informed Adversariescited by 143
  7. 2023Invisible Image Watermarks Are Provably Removable Using Generative AIcited by 124
  8. 2022Privacy for Free: How does Dataset Condensation Help Privacy?cited by 119
  9. 2023Privacy Auditing with One (1) Training Runcited by 119
  10. 2022Measuring Forgetting of Memorized Training Examplescited by 118
  11. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  12. 2021Differentially Private Federated Learning on Heterogeneous Datacited by 74
38 more
  1. 2022Differentially Private Language Models for Secure Data Sharingcited by 68
  2. 2021Robust and Differentially Private Mean Estimationcited by 66
  3. 2021The Skellam Mechanism for Differentially Private Federated Learningcited by 66
  4. 2022FedDM: Iterative Distribution Matching for Communication-Efficient Federated Learningcited by 65
  5. 2022TAPAS: a Toolbox for Adversarial Privacy Auditing of Synthetic Datacited by 56
  6. 2023FedFed: Feature Distillation against Data Heterogeneity in Federated Learningcited by 54
  7. 2022Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributionscited by 50
  8. 2024Membership Inference Attacks Cannot Prove that a Model Was Trained On Your Datacited by 49
  9. 2024Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearningcited by 48
  10. 2024Are we making progress in unlearning? Findings from the first NeurIPS unlearning competitioncited by 48
  11. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 42
  12. 2024Private Fine-tuning of Large Language Models with Zeroth-order Optimizationcited by 41
  13. 2022Debugging Differential Privacy: A Case Study for Privacy Auditingcited by 39
  14. 2022Privately Fine-Tuning Large Language Models with Differential Privacycited by 39
  15. 2021Federated Learning with Local Differential Privacy: Trade-offs between Privacy, Utility, and Communicationcited by 38
  16. 2024Privacy-Preserving Retrieval-Augmented Generation with Differential Privacycited by 38
  17. 2023Why Is Public Pretraining Necessary for Private Model Training?cited by 36
  18. 2023User Inference Attacks on Large Language Modelscited by 36
  19. 2022RelaxLoss: Defending Membership Inference Attacks without Losing Utilitycited by 35
  20. 2023One-shot Empirical Privacy Estimation for Federated Learningcited by 35
  21. 2024Evaluations of Machine Learning Privacy Defenses are Misleadingcited by 35
  22. 2024Privacy-Preserving Instructions for Aligning Large Language Modelscited by 34
  23. 2025Firewalls to Secure Dynamic LLM Agentic Networkscited by 34
  24. 2021Decision Making with Differential Privacy under a Fairness Lenscited by 32
  25. 2022Quantum Differential Privacy: An Information Theory Perspectivecited by 32
  26. 2022Bayesian Estimation of Differential Privacycited by 31
  27. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  28. 2021Federated f-Differential Privacycited by 29
  29. 2023Conformal Prediction for Federated Uncertainty Quantification Under Label Shiftcited by 29
  30. 2022On the Impossible Safety of Large AI Modelscited by 27
  31. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  32. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  33. 2021The Role of Adaptive Optimizers for Honest Private Hyperparameter Selectioncited by 25
  34. 2022A General Framework for Auditing Differentially Private Machine Learningcited by 25
  35. 2021Accuracy, Interpretability, and Differential Privacy via Explainable Boostingcited by 24
  36. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  37. 2022CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learningcited by 24
  38. 2022Learning to Generate Image Embeddings with User-level Differential Privacycited by 23

50 most cited of 290 All 290 (JSON)