The Composition Theorem for Differential Privacy
Open accessThe DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Abstract
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 a data processing inequality along with its converse. Our result improves over the state of the art, and has immediate connections to several problems studied in the literature.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“As such, virtually all implementations of differential privacy satisfy only (variants of) computational differential privacy introduced by [347].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [347]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
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
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000042 · Cited by 5,557
Dwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Randomized 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 · cited 1×
“th high enough condence, no matter what auxiliary information or computational power she might. Consider the following simple protocol known as the randomized response, which is a term rst coined by [War65] and commonly used in many private communications including the multi-party setting [MMP+10]. We will show in Sec…”
MethodInfluentialLauritzen, S. L. (1996) · doi:10.1093/oso/9780198522195.001.0001 · Cited by 2,976
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
Equivalent Comparisons of Experiments
Blackwell, D. (1953) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729032 · Cited by 1,406 · cited 1×
“…and ˜ δ ∈ [0 , 1] , the class of ( ε (cid:96) , δ (cid:96) ) - differentially private mechanisms satisfy ˜ ε ˜ δ , 1 This tells us that the ε (cid:96) ’s sum up under composition : whenever we have kε or kε 2 in (7) we can replace it by the summation to get the general result for heterogeneous case.”
BackgroundMechanism Design via Differential Privacy
McSherry, F., & Talwar, K. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.66 · Cited by 1,371
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 · cited 2×
“When composing real-valued queries, the Gaussian mechanism is a popular choice [2], [3], [13], [14], [24].”
Background
Research works printed but not linked: 5
- [DKM + 06b] , Our data, ourselves: Privacy via distributed noise generation , Advances in Cryptology-EUROCRYPT 2006, Springer, 2006, pp. 486-503.
- [CT12] Thomas M Cover and Joy A Thomas, Elements of information theory , John Wiley & Sons, 2012.
- [KOV14a] P. Kairouz, S. Oh, and P. Viswanath, The composition theorem for differential privacy , International Conference on Machine Learning, 2014.
- [KOV14b] , Extremal mechanisms for local differential privacy , Advances in Neural Information Processing Systems 27, 2014, pp. 2879-2887.
- [KOV15] , Secure multi-party differential privacy , Advances in Neural Information Processing Systems, 2015.
Cited by
Items 401–404 of 404
SoK: The Hitchhiker’s Guide to Efficient, End-to-End, and Tight DP Auditing
Annamalai, M. S. M. S., Balle, B., Hayes, J., Kaissis, G. A., & Cristofaro, E. D. (2026) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml68715.2026.00031 · Cited by 3
“Functional DP ( f -DP). f -DP uses the hypothesis testing interpretation of DP [57] (reviewed in Section 2.4) to bound the type II error achievable by an adversary aiming to distinguish between the outputs of a DP mechanism on adjacent inputs at a significance level of α .”
InfluentialZhong-zheng, L., Liao, M., Wang, Y., Zhang, R., Sun, J., & Zheng, H. (2026) · PLoS ONE · doi:10.1371/journal.pone.0350884
Differentially-Private Quantum Federated Learning Against Gradient Inversion Attacks
Im, C., Park, S., & Kim, J. (2026) · IEEE Transactions on Networking · doi:10.1109/ton.2026.3738131
“In particular, repeated observations of differential-private data can accumulate enough information to infer about the true data before applying DP, posing threats to privacy preservation even when DP is utilized [11].”
Privacy-Preserving Sharing for Genomic Data
Zhang, Y., & Li, X. (2026) · Springer handbooks · doi:10.1007/978-3-031-92372-2_39
Metadata
- Authors
- Kairouz, P., Oh, S., & Viswanath, P.
- Affiliations
- Stanford University (US)
- University of Illinois Urbana-Champaign (US)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2017-06
- Volume
- 63
- Issue
- 6
- Pages
- 4037-4049
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W1880309113
- Cited by
- 408
- References
- 34
- Citations by year
- 2026: 26 · 2025: 33 · 2024: 55 · 2023: 44 · 2022: 49 · 2021: 48 · 2020: 47 · 2019: 35 · 2018: 27 · 2017: 18
- FWCI
- 20.72
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- International Conference on Machine Learning
- Funders
- NSF CISE (CCF-1422278, CCF-1553452)
- NSF SaTC (CNS-1527754)
- NSF CMMI (MES-1450848)
- NSF ENG (ECCS-1232257)
- Google Faculty Research Award
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Keywords
- differential privacy, composition theorem, upper bounds, hypothesis testing, data processing inequality, Converse
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.