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].”
BackgroundLocal Privacy and Statistical Minimax Rates
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · 2013 IEEE 54th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.53 · Cited by 954
Alon, N., & Spencer, J. H. (2000) · Wiley eBooks · doi:10.1002/0471722154 · Cited by 949
Practical privacy: the SuLQ framework
Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005) · Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1065167.1065184 · Cited by 797 · cited 2×
“, 2005; 2013) and they provide a primitive for constructing more complex queries (Blum et al., 2005).”
BackgroundBoosting and Differential Privacy
Dwork, C., Rothblum, G. N., & Vadhan, S. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.12 · Cited by 784 · cited 3×
“A routine argument shows that the composition of k queries, each of which is (ε, δ)differentially private, is at least (k , kδ)-differentially private (Dwork et al., 2006b;a; Dwork & Lei, 2009; Dwork et al., 2010).”
BackgroundMethodInfluentialInformation theoretic inequalities
Dembo, A., Cover, T. M., & Thomas, J. A. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.104312 · Cited by 742 · cited 1×
“As an aside, we mention that there is a strong tradition of such derivations in the information theory literature: the Fisher information inequality (Blachman, 1965; Zamir, 1998), the entropy power inequality (Stam, 1959; Blachman, 1965; Verdú & Guo, 2006), an extremal inequality involving mutual informations (Liu & V…”
BackgroundSome inequalities satisfied by the quantities of information of Fisher and Shannon
Stam, A. J. (1959) · Information and Control · doi:10.1016/s0019-9958(59)90348-1 · Cited by 706 · cited 1×
“Comparing to (4), the privacy guarantee is significantly improved from ˜ ε ˜ δ = O kε 2 + kε 2 log(1 / ˜ δ ) to ˜ ε ˜ δ = O kε 2 + min kε 2 log(1 / ˜ δ ) , ε log( ε/ ˜ δ ) (cid:9)(cid:17) , especially when composing a large number k of interactive queries.”
Differential privacy and robust statistics
Dwork, C., & Lei, J. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536466 · Cited by 611 · cited 8×
“A routine argument shows that the composition of k queries, each of which is (ε, δ)differentially private, is at least (k , kδ)-differentially private (Dwork et al., 2006b;a; Dwork & Lei, 2009; Dwork et al., 2010). A tighter bound of (ε̃δ̃, kδ + δ̃)-differential privacy under k-fold adaptive composition is provided, u…”
BackgroundMethodInfluentialA Statistical Framework for Differential Privacy
Wasserman, L., & Zhou, S. (2010) · Journal of the American Statistical Association · doi:10.1198/jasa.2009.tm08651 · Cited by 397 · cited 2×
“Together with Corollary 4, Theorem 5 recovers a well known result: differential privacy is preserved by postprocessing the output [10], [15], [33].”
BackgroundResultPrivacy-Preserving Datamining on Vertically Partitioned Databases
Dwork, C., & Nissim, K. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28628-8_32 · Cited by 348
The convolution inequality for entropy powers
Blachman, N. (1965) · IEEE Transactions on Information Theory · doi:10.1109/tit.1965.1053768 · Cited by 331 · cited 1×
“Comparing to (4), the privacy guarantee is significantly improved from ˜ ε ˜ δ = O kε 2 + kε 2 log(1 / ˜ δ ) to ˜ ε ˜ δ = O kε 2 + min kε 2 log(1 / ˜ δ ) , ε log( ε/ ˜ δ ) (cid:9)(cid:17) , especially when composing a large number k of interactive queries.”
A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis
Hardt, M., & Rothblum, G. N. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.85 · Cited by 319
On the geometry of differential privacy
Hardt, M., & Talwar, K. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806786 · Cited by 314
A simple and practical algorithm for differentially private data release
Hardt, M., Ligett, K., & McSherry, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.4763 · Cited by 283
Universally Utility-maximizing Privacy Mechanisms
Ghosh, A., Roughgarden, T., & Sundararajan, M. (2012) · SIAM Journal on Computing · doi:10.1137/09076828x · Cited by 253
A learning theory approach to noninteractive database privacy
Blum, A., Ligett, K., & Roth, A. (2013) · Journal of the ACM · doi:10.1145/2450142.2450148 · Cited by 242 · cited 1×
“Count queries are well studied in differential privacy [3], [6], [13], [14] and they provide a primitive for constructing more complex queries [3].”
BackgroundAn Extremal Inequality Motivated by Multiterminal Information-Theoretic Problems
Liu, T., & Viswanath, P. (2007) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.894680 · Cited by 215 · cited 1×
“Further, the δ -approximate differential privacy degradation of (1 ) is also strictly smaller than the previous ( kδ + ˜ δ ).”
BackgroundSelf-citationA proof of the Fisher information inequality via a data processing argument
Zamir, R. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.669301 · Cited by 171
Iterative Constructions and Private Data Release
Gupta, A., Roth, A., & Ullman, J. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-28914-9_19 · Cited by 164
Distributed Private Data Analysis: Simultaneously Solving How and What
Beimel, A., Kobbi Nissim, B., & Omri, E. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85174-5_25 · Cited by 163
A simple proof of the entropy-power inequality
Verdú, S., & Guo, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.872978 · Cited by 139 · cited 1×
“Comparing to (4), the privacy guarantee is significantly improved from ˜ ε ˜ δ = O kε 2 + kε 2 log(1 / ˜ δ ) to ˜ ε ˜ δ = O kε 2 + min kε 2 log(1 / ˜ δ ) , ε log( ε/ ˜ δ ) (cid:9)(cid:17) , especially when composing a large number k of interactive queries.”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
Blocki, J., Blum, A., Datta, A., & Sheffet, O. (2012) · 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.67 · Cited by 136
The primes contain arbitrarily long polynomial progressions
Tao, T., & Ziegler, T. (2008) · Acta Mathematica · doi:10.1007/s11511-008-0032-5 · Cited by 128
The Limits of Two-Party Differential Privacy
McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., & Vadhan, S. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.14 · Cited by 119
The optimal mechanism in differential privacy
Geng, Q., & Viswanath, P. (2014) · 2014 IEEE International Symposium on Information Theory · doi:10.1109/isit.2014.6875258 · Cited by 97
Self-citationOptimal Noise Adding Mechanisms for Approximate Differential Privacy
Geng, Q., & Viswanath, P. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2504972 · Cited by 91 · cited 4×
“In terms of variance-privacy trade-off for real-valued queries, the optimal noise-adding mechanism known as the staircase mechanism was introduced in [20].”
BackgroundInfluentialSelf-citationBeyond worst-case analysis in private singular vector computation
Hardt, M., & Roth, A. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488650 · Cited by 90
Determinant Inequalities via Information Theory
Cover, T. M., & Thomas, A. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609033 · Cited by 80
Optimal private halfspace counting via discrepancy
Muthukrishnan, S., & Nikolov, A. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2214090 · Cited by 53
Accuracy-Privacy Tradeoffs for Two-Party Differentially Private Protocols
Goyal, V., Mironov, I., Pandey, O., & Sahai, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40041-4_17 · Cited by 20
The Optimal Mechanism in Differential PrivacyPreprint
Geng, Q., & Viswanath, P. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1212.1186 · Cited by 14
Self-citationOptimal Private Halfspace Counting via DiscrepancyPreprint
Muthukrishnan, S., & Nikolov, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1203.5453 · Cited by 11
Optimal Noise Adding Mechanisms for Approximate Differential PrivacyPreprint
Geng, Q., & Viswanath, P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.1330 · Cited by 9
Self-citation
Research works printed but not linked: 2
- cover, 2012, Elements of Information Theory
- kairouz, 2015, The composition theorem for differential privacy, Proc Int Conf Mach Learn
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
Self-citationMironov, I. (2017) · 2017 IEEE 30th Computer Security Foundations Symposium (CSF) · doi:10.1109/csf.2017.11 · Cited by 1,255
“[7] for an optimal bound on composition of homogeneous mechanisms and Murtagh and Vadhan [8] for hardness results and an approximation scheme for composition of mechanisms with heterogeneous privacy guarantees.”
BackgroundMethodA Hybrid Approach to Privacy-Preserving Federated Learning
Truex, S., Baracaldo, N., Anwar, A., Steinke, T., Ludwig, H., Zhang, R., & Zhou, Y. (2019) · Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security · doi:10.1145/3338501.3357370 · Cited by 1,029
Yin, X., Zhu, Y., & Hu, J. (2022) · ACM Computing Surveys · doi:10.1145/3460427 · Cited by 638
“To limit the privacy leakage from the updates or the final model, a user-level differential privacy can be applied during the FL training process [6, 44, 83].”
MethodDifferential Privacy for Deep and Federated Learning: A Survey
Ouadrhiri, A. E., & Abdelhadi, A. (2022) · IEEE Access · doi:10.1109/access.2022.3151670 · Cited by 445
“[62] define a procedure that allows achieving the optimal bound of the privacy budget after k queries.”
BackgroundInfluential
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.