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 301–400 of 404
Privacy-Preserving Federated Learning in Oil Palm Industry for Fresh Fruit Bunch Ripeness Grading
Laddawong, P., Pianroj, Y., Chotikawanid, P., Punvichai, T., Jumrat, S., & Muangprathub, J. (2025) · Journal of Advances in Information Technology · doi:10.12720/jait.16.3.434-446 · Cited by 1
“[23] conducted a survey on FL, focusing on aspects such as efficiency, effectiveness, privacy, robustness, and fairness considerations.”
Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms Under Composition
Lebeda, C. J., Regehr, M., Kamath, G., & Steinke, T. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00060 · Cited by 15
“A common approach is to find the privacy parameters for each part of a mechanism and apply a composition theorem [13], [15] to find the privacy parameters of the full mechanism.”
Auditing Differential Privacy Guarantees Using Density Estimation
Koskela, A., & Mohammadi, J. A. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00061 · Cited by 4
“By training multiple models, once with and once without the differing sample, and by measuring the false positive rates (FPRs) and false negative rates (FNRs) of the membership inferences, empirical ε -estimates can be derived for a given value of δ [18].”
Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach
Jiang, B., Zhang, W., Lu, D., Du, J., Sharma, S., & Yan, Q. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00064 · Cited by 1
“The basic composition theorem [16] suggests that ϵ , δ both increase linearly with the number of queries, or sublinearly with advanced composition [17], [18], [19].”
A Utility-Aware Privacy-Preserving Method for Trajectory Publication
Wu, Z., Wang, X., Huang, Z., Zhang, T., Zhu, M., Huang, X., Xu, M., & Chen, W. (2025) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2025.3627644 · Cited by 1
“In path anonymization, the exponential mechanism applied in each path group provides OD -DP; by parallel composition, the overall path stage satisfies 2 = max( OD ) -DP. Finally,ourapproachsatisfies ( (cid:2) 1 + (cid:2) 2 , δ ) - DP by sequential composition [75].”
PLRV-O: Advancing Differentially Private Deep Learning via Privacy Loss Random Variable Optimization
Yang, Q., Stout, N., Mohammady, M., Wang, H., Samreen, A., Quinn, C. J., Yan, Y., Kundu, A., & Hong, Y. (2025) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3719027.3765151 · Cited by 4
Differentially Private Sliced Inverse Regression in the Federated Paradigm
He, S., Zhang, J., & Chen, X. (2026) · Journal of the American Statistical Association · doi:10.1080/01621459.2025.2604315 · Cited by 3
Multi-Task Semantic Communications With Bounded Privacy Leakage Constraint
Zamani, A., & Skoglund, M. (2026) · IEEE Transactions on Information Theory · doi:10.1109/tit.2026.3654430 · Cited by 1
Composition Theorems for Multiple Differential Privacy Constraints
Cadir, C., Najib, S., & Shkel, Y. Y. (2026) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit62367.2026.11653633
“The details are in Appendix C. Unlike [11], which, for a given δ i , returns the corresponding ε i , Algorithm 1 yields a closed form of the heterogeneous composition region, giving all the ( ε i , δ i ) defining it.”
InfluentialDai, J., & Hou, P. (2026) · Mathematics · doi:10.3390/math14091564 · Cited by 1
Protecting Link Privacy for Large Correlated Social Networks
Yang, L., Fei, Y., & Zhang, X. (2016) · doi:10.1109/ccbd.2016.048 · Cited by 1
Counterterrorism: Privately Clustering a Radical Social Network Data
Boujmil, J., Tagmouti, N., & Raissouni, N. (2017) · Transactions on Machine Learning and Artificial Intelligence · doi:10.14738/tmlai.54.3204
Aggregation Scheme for Behavior Pattern Analysis in Social Networking Sites
Ghonge, M. M., Kotwal, P. R., & Potgantwar, A. D. (2018) · 2018 International Conference On Advances in Communication and Computing Technology (ICACCT) · doi:10.1109/icacct.2018.8529652 · Cited by 1
“Viswanath [16], in which Laplacian mechanism or the staircase mechanism is used to add noise in the data so that it cannot be spread across the unauthorized access.”
MethodPrivacyBuDe: Privacy Buckets Demo Tight Differential Privacy Guarantees made Simple
Sommer, D., Meiser, S., & Mohammadi, E. (2018) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3243734.3278485 · Cited by 1
“The generic composition theorem of Kairouz, Oh, and Visvanath [5], e.”
Privacy-Preserving Inference on the Ratio of Two Gaussians Using Sums
Miao, J., & Li, Y. P. (2022) · Journal of Data Science · doi:10.6339/22-jds1050 · Cited by 1
A Quantifying Approach for Evaluating Differential Privacy in Deep Learning
Yin, L., Lv, Y., Sun, Z., Tao, F., & Li, R. (2022) · IEEE Smart World Congress (SWC) · doi:10.1109/smartworld-uic-atc-scalcom-digitaltwin-pricomp-metaverse56740.2022.00323 · Cited by 1
“If a differentially private algorithm is designed for deep learning according to the original definition of differential privacy, due to the mathematical nature of the privacy budget, the privacy budget will continue to increase with the iteration of data in the process of model training [8].”
BackgroundMethodDivergences on monads for relational program logics
Sato, T., & Katsumata, S.-Y. (2023) · Mathematical Structures in Computer Science · doi:10.1017/s0960129523000245 · Cited by 2
“2 Generation of Divergences It has been shown that DP can be interpreted as hypothesis testing ([54, 30]).”
BackgroundNatural differential privacy—a perspective on protection guarantees
Altman, M., & Cohen, A. (2023) · PeerJ Computer Science · doi:10.7717/peerj-cs.1576 · Cited by 1
“…for protection at the (bit) event-level, To calculate epsilon for other units of protection, it is straightforward to calculate the effective epsilon by using the standard dp composition formula across the maximum number of shared events in the computation ( Kairouz, Oh & Viswanath, 2015 ).”
MethodRobust Constrained Consensus with Guaranteed Differential Privacy and Accurate Convergence
Wang, Y. (2024) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc62350.2024.10587768 · Cited by 1
“It is worth noting that the considered notion of (cid:2) -DP is more stringent than other relaxed (approximate) DP notions such as ( (cid:2), δ ) -DP [28], zero-concentrated DP [29], or R´enyi DP [30].”
BackgroundMinimax rates of convergence for sliced inverse regression with differential privacy
Zhao, W., Zhu, X., & Zhu, L. (2024) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2024.108041 · Cited by 1
Chernoff Information as a Privacy Constraint for Adversarial Classification
Ünsal, A., & Önen, M. (2024) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton63246.2024.10735286 · Cited by 2
“Namely, sequential composition [37], [38], provides an upper bound on the privacy budget of releasing a series of query outputs of several DP mechanisms applied on the same data and is reminded to the reader by the following theorem.”
Hybrid Laplace-Gaussian Differential Privacy to Secure Data Aggregation in Edge-IoT Systems
Yadav, P. K., Pandey, S., Singh, P., & Pandey, P. (2024) · IEEE International Conference on Advances in Signal Processing, Power, Communication, and Computing (ASPCC) · doi:10.1109/aspcc62191.2024.10880970 · Cited by 3
Analyzing and Enhancing LDP Perturbation Mechanisms in Federated Learning
Duan, J., Ye, Q., Hu, H., & Sun, X. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3580796 · Cited by 2
“Since Dwork et al. [21] first introduced the definition of differential privacy (DP) and the first DP mechanism, i.e., Laplace mechanism, extensive DP-related works [13], [22], [23], [24], [25], [26] have been proposed.”
Information Density Bounds for Privacy
Saeidian, S., Grosse, L., Sadeghi, P., Skoglund, M., & Oechtering, T. J. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3637364 · Cited by 5
“Index Terms —Privacy, information density, pointwise maximal leakage, pointwise maximal cost, local di ff erential privacy, information privacy, gain function, cost function.”
Differential privacy for publishing enterprise-scale WLAN traces
Li, D., Dong, X., & Li, M. (2018) · Soft Computing · doi:10.1007/s00500-018-3223-9 · Cited by 1
“Wealsocomparetheproposedapproach with the methods of PCP (Wang et al. 2017) and the composition theorem Kairouz et al. (2017).”
MethodDifferential Privacy at Risk: Bridging Randomness and Privacy Budget
Dandekar, A., Basu, D., & Bressan, S. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2021-0005 · Cited by 12
Defining Privacy-Preserving Data Analysis
Ny, J. L. (2020) · Springer briefs in electrical and computer engineering · doi:10.1007/978-3-030-41039-1_1 · Cited by 1
Differential Privacy Online Learning Based on the Composition Theorem
Jiang, P., & Liao, S. (2020) · IEEE International Conference on Electronics Information and Emergency Communication · doi:10.1109/iceiec49280.2020.9152303 · Cited by 1
“Before discussing how to achieve differential privacy in online learning, we introduce the composition theorem [16].”
MethodCascading Bandit Under Differential Privacy
Wang, K., Dong, J., Wang, B., & Li, S. (2022) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp43922.2022.9746966 · Cited by 1
p-Power Exponential Mechanisms for Differentially Private Machine Learning
Li, Y., Ren, X., Zhao, F., & Yang, S. (2021) · IEEE Access · doi:10.1109/access.2021.3129130 · Cited by 1
“For ( ε, δ ) -DP, although many researchers have studied the theoretical bound of the optimal mechanism [41], [42], [43], [44], they mainly focus on the non-adaptive linear queries but seldom propose practical mechanism.”
BackgroundA Survey on Privacy-Preserving Deep Learning with Differential Privacy
Zhang, Y., Cai, Y., Zhang, M., Li, X., & Fan, Y. (2022) · Communications in computer and information science · doi:10.1007/978-981-19-0852-1_2 · Cited by 1
DiPPS: Differentially Private Propensity Scores for Bias Correction
Chen, L., Hartmann, V., & West, R. (2023) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v17i1.22131 · Cited by 1
“This requires further rounds of communication with the individuals that hold the data and, more importantly, each additional function computation decreases the level of privacy (Kairouz, Oh, and Viswanath 2015; Rogers et al. 2016).”
Background*-Liftings for Differential Privacy
Barthe, G., Espitau, T., Hsu, J., Sato, T., & Strub, P.-Y. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2017.102 · Cited by 6
On The Differential Privacy of Thompson Sampling With Gaussian PriorPreprint
Tossou, A. C. Y., & Christos Dimitrakakis, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.09192 · Cited by 1
“Solving the inequality and taking the minimum ǫ k i that satisfies it leads to To get the privacy loss over T times we apply the advanced composition theorem of (Kairouz et al., 2017) (Theorem 3.5).”
InfluentialThe Cost of a Reductions Approach to Private Fair OptimizationPreprint
Alabi, D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.09613 · Cited by 4
DP-CGAN: Differentially Private Synthetic Data and Label GenerationPreprint
Torkzadehmahani, R., Kairouz, P., & Paten, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.09700 · Cited by 38
“al [1], which provides strong estimates of privacy loss compared to various versions of composition theorem [10, 12, 28, 15, 16] including strong composition theorem [16].”
BackgroundSelf-citationLearning Numeric Optimal Differentially Private Truncated Additive MechanismsPreprint
Sommer, D., Abfalterer, L., Zingg, S., & Mohammadi, E. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.12957 · Cited by 2
“, a pair of mechanism output distributionsM(D0) andM(D1) such that no pair of inputs induces more privacy leakage, is common to simplify the privacy analysis [12, 24, 32, 1, 31, 4].”
BackgroundInfluentialPrivacy-Preserving Probabilistic Voltage Forecasting in Local Energy CommunitiesPreprint
Toubeau, J., Teng, F., Wang, Y., Krannichfeldt, L. V., & Morstyn, T. (2022) · doi:10.36227/techrxiv.18535274 · Cited by 1
Enforcing Group Fairness in Privacy-Preserving Federated LearningPreprint
Chen, C., Zhou, Z., Tang, P., Su, S., & He, L. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4601101 · Cited by 1
Privacy-Preserving Federated Learning Compatible with Robust AggregatorsPreprint
Alebouyeh, Z., & Bidgoly, A. J. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4793556 · Cited by 2
Efficiently Verifiable Computations on User Data for Behavior Analysis with Privacy Preservation
Kotwal, M. P. R., Ghonge, M. M., & Potgantwar, A. D. (2018) · International Journal of Engineering & Technology · doi:10.14419/ijet.v7i3.8.15227
“Viswanath [15] introduces Composition theorem for differential privacy in which Laplacian mechanism or the staircase mechanism is used to add noise in the data so that it can't be spread over the unapproved access get to.”
New Program Abstractions for Privacy
Hunt, S., & Sands, D. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-41103-9_10
“a new abstract domain) in a way which will provide greater precision and versatility; it is based on the idea of a geometric interpretation of differential privacy, a privacy region introduced by Kairouz, Oh, and Viswanath [18].”
InfluentialDifferential Privacy Technology Resistant to the Model Inversion Attack in AI Environments
Park, C., & Hong, D. (2019) · Information Security and Cryptology · doi:10.13089/jkiisc.2019.29.3.589
Multi-Dimensional Randomized Response
Domingo‐Ferrer, J., & Soria-Comas, J. (2022) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde53745.2022.00135
Vinterbo, S. A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.10523
“On the positive side, a non-zero δ allows, among others, for better composition properties than ( , 0)-differential privacy [6].”
BackgroundOn the Differentially Private Nature of Perturbed Gradient DescentPreprint
Tholeti, T., & Kalyani, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.06847 · Cited by 1
“This is characterized by the strong composition theorem [19].”
BackgroundQuantifying identifiability to choose and audit $ε$ in differentially private deep learningPreprint
Bernau, D., Eibl, G., Grassal, P. W., Keller, H., & Kerschbaum, F. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.02913
“The application of differential privacy (DP) for machine learning has received considerable attention by the privacy research community, leading to key contributions such as the tight estimation of privacy loss under composition [22, 23, 32] and differentially private stochastic gradient descent [1, 3, 41, 43] (DPSGD)…”
BackgroundLearning Towards Better Accuracy and Privacy
Xiang, L. (2018) · TSpace (University of Toronto)
Jorge Mateu’s Contribution to the Discussion of ‘Gaussian Differential Privacy’ by Dong et al.
Mateu, J. (2021) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1111/rssb.12461
Making the Most of Parallel Composition in Differential Privacy
Smith, J., Asghar, H. J., Gioiosa, G., Mrabet, S., Gaspers, S., & Tyler, P. (2021) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2022-0013 · Cited by 18
Pejó, B., & Desfontaines, D. (2022) · SpringerBriefs in computer science · doi:10.1007/978-3-030-96398-9_7
Private quantiles estimation in the presence of atoms
Lalanne, C., Gastaud, C., Grislain, N., Garivier, A., & Gribonval, R. (2023) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaad030 · Cited by 8
Hero, A. O. (2018) · Journal of the American Statistical Association · doi:10.1080/01621459.2018.1442606
“Recent work on k -fold composition theory for differential privacy developed by Kairouz, Oh, and Viswanath (2017) could be relevant here.”
BackgroundPrivacy accounting εconomics: Improving differential privacy composition via a posteriori bounds
Hartmann, V., Bindschaedler, V., Bentkamp, A., & West, R. (2022) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2022-0070 · Cited by 2
“[25] and Murtagh and Vadhan [31], we derive an expression for OptDel({ki}i=1, {(εk, δk)} kn k=1, E) by showing that it suffices to analyze a class of randomized response mechanisms and to then compute the optimal ODP bound for these randomized response mechansisms.”
BackgroundMethodBatching of Tasks by Users of Pseudonymous Forums: Anonymity Compromise and Protection
Goldberg, A., Fanti, G. C., & Shah, N. B. (2023) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3579335 · Cited by 1
“Similar to prior work on differential privacy [42], [21], we show that an adversary conducting a hypothesis test to determine if batching occurred will face a poor trade-off between power and type I error given an output of a mechanism that is OSDP with gap g:”
ResultTotal Variation with Differential Privacy: Tighter Composition and Asymptotic Bounds
Ghazi, E., & Issa, I. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206716 · Cited by 3
“Given this fact, one can follow exactly the converse proof in [6] to show that the output of the k -fold composition of any ε -DP and η -TV mechanisms can also be simulated using the (non-adaptive) k -fold composition of M ε, 0 ,η , hence the corresponding tradeoff function will be greater than the…”
BackgroundMethodResultInfluentialDifferential privacy in machine learning for traffic forecasting
Vinay, S., & Redburg, R. (2022) · Journal of Emerging Investigators · doi:10.59720/22-130
Joint Distribution Analysis of Multi-Dimensional Randomized Response
Wang, W., Zhang, Y., Yan, J., Zhou, Y., & Lu, L. (2023) · International Conference on Networking and Network Applications (NaNA) · doi:10.1109/nana60121.2023.00076
Amplification by Shuffling without Shuffling
Balle, B., Bell, J., & Gascón, A. (2023) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3576915.3623215
“Applying the advanced composition theorem [36] to the privacy loss incurred by √ n columns then yields a total privacy loss of the order n−1/4 · n−1/2 · n = n−1/2 as claimed in the theorem.”
MethodMinimizing Noise in Location Privacy Protection Through Equipment Error Consideration
Isawa, R., Sei, Y., Tahara, Y., & Ohsuga, A. (2024) · International journal of electrical and computer engineering systems · doi:10.32985/ijeces.15.3.7
“Kairouz et al. [24] focused on privacy guarantees under k-fold composition.”
InfluentialRyffel, T., Créquit, P., Baillet, M., Paumier, J., Marfoq, Y., Sy, R., Girardot, O., Chanet, T., Bayssat, L., Mazières, J., et al. (2024) · doi:10.2196/preprints.59685
A federated learning algorithm based on hierarchical importance adaptive differential privacy
Zhang, P., Guo, H., Chen, F., & Lu, B. (2023) · International Conference on Artificial Intelligence and Computer Engineering (ICAICE) · doi:10.1145/3652628.3652669
“The procedural steps are delineated in conjunction with Figure 1 and precisely defined as per Theorem 1 and Theorem 2: Theorem 1: Sequential Composition [7] Suppose there exist algorithms 𝐴 1 ,𝐴 2 , ...,𝐴 𝐾 , which satisfy 1 − differential privacy, 𝜀 2 − differential privacy, and 𝜀 3 − differential privacy, and any tw…”
MethodPrivacy-Preserving Frank-Wolfe on Shuffle Model
Zhang, L., Wu, S., & Zhang, H. F. (2024) · Acta Mathematicae Applicatae Sinica English Series · doi:10.1007/s10255-024-1095-6
Privacy-Preserving Federated Learning Compatible with Robust AggregatorsPreprint
Alebouyeh, Z., & Bidgoly, A. J. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4882102 · Cited by 1
Efficiently Calculating Stronger Lower Bound for Differentially Private SGD in Black-Box Setting
Shibahara, T., Miura, T., Kii, M., & Ichikawa, A. (2024) · IEEE Annual International Computer Software and Applications Conference (COMPSAC) · doi:10.1109/compsac61105.2024.00133
“If a mechanism is ( (cid:2), δ ) -differentially private, the false positive rate (FPR) and false negative rate (FNR) of the games are bounded [15] by: Given δ , the maximum (cid:2) satisfying the above inequalities is the empirical (cid:2) .”
BackgroundAllmann, J., von Voigt, S. N., & Tschorsch, F. (2024) · IEEE European Symposium on Security and Privacy Workshops (EuroS&PW) · doi:10.1109/eurospw61312.2024.00013
“One elegant feature of differential privacy is the composition theorem, which states, that generally the ε -values of repeated queries add up [8].”
BackgroundPrivacy-preserving visualization of brain functional connectivity
Tao, Y., Sarwate, A. D., Panta, S. R., Turner, J., Plis, S., Beason‐Held, L. L., Bilgel, M., Resnick, S. M., Abrol, A., & Calhoun, V. D. (2026) · NeuroImage · doi:10.1016/j.neuroimage.2026.122175
Adaptive Privacy for Differentially Private Causal Graph Discovery
Bhattacharjee, P., & Tandon, R. (2024) · Machine learning for signal processing ... · doi:10.1109/mlsp58920.2024.10734773
“As Composition is a critical tool in DP-CGD, the total leakage can be calculated by Basic Composition [4, 5, 14, 15], Advanced Composition [15, 6], Optimal Composition [16], Adaptive Composition [17], Moments Accountant [18].”
MethodCURATE: Scaling-Up Differentially Private Causal Graph Discovery
Bhattacharjee, P., & Tandon, R. (2024) · Entropy · doi:10.3390/e26110946 · Cited by 1
“Therefore the total leakage can be calculated by Basic Composition [8], [10], [9], [12], Advanced Composition [12], [11], Optimal Composition [14], Adaptive Composition [26], Moments Accountant [1].”
Differential Privacy: 6 Key Equations Explained
Tiwari, A. (2024) · doi:10.59350/ntarj-tg210
He, F., & Tao, D. (2025) · Machine learning · doi:10.1007/978-981-16-8233-9_11
Differentially private multivariate statistics with an application to contingency table analysis
Kim, M., Lee, J., Kwak, S. W., & Jung, S. (2025) · Electronic Journal of Statistics · doi:10.1214/25-ejs2368 · Cited by 4
Zhang, X., Ma, X., Yang, X., Zhang, X., Xiao, Y., & Bai, X. (2025) · International Conference on Computer Supported Cooperative Work in Design (CSCWD) · doi:10.1109/cscwd64889.2025.11033391 · Cited by 1
“Given n random algorithms { M 1 , M 2 , . . . , M n } , where Theorem 2 (The Parallel Composition of DP [13]) .”
A Novel Approach to Differential Privacy with Alpha Divergence
Liu, Y., & Wang, Z. (2025) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf64896.2025.00009
“Figures 6, 7, and 8 illustrate that although zCDP initially exhibits a higher growth rate of privacy consumption, its logarithmic growth becomes favourable over a wide range of iterative scenarios.”
Node Similarity-Based Synthetic Graphs Releasing With Differential Privacy Guarantees
Cai, B., Li, Y., Hu, C., Sheng, W., Chen, J., & Yu, J. (2025) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2025.3597347
“Crucially, DP offers composition properties [27], [28], allowing the privacy guarantees of multiple mechanisms to be combined, and post-processing immunity [29], ensuring further computations on a DP output do not degrade its privacy.”
Differentially-Private Collaborative Online Personalized Mean Estimation
Yakimenka, Y., Weng, C.-W., Lin, H.-Y., Rosnes, E., & Kliewer, J. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2025.3612276
MCMC for Bayesian Estimation of Differential Privacy from Membership Inference Attacks
Yildirim, C., Kaya, K., Yıldırım, S., & Savaş, E. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-06096-9_23 · Cited by 1
“Theoretical lower bounds for ( ϵ, δ ) have been extensively analyzed for a variety of mechanisms, such as noise-adding mechanisms (Laplace, Gaussian, etc.) (Dwork et al., 2006; Dwork and Roth, 2014), subsampling (Balle et al., 2018), and their composition (Kairouz et al., 2015).”
Auditing Privacy of Additive Noise Mechanisms Using Linear Predictive Models
Welfert, M., Stromberg, N., Díaz, M., Melbourne, J., & Sankar, L. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195545
“Motivated by obfuscating sensitive features, our work also connects to broader notions of privacy risk quantification, including differential privacy [15], maximal α -leakage [16], [17], and probability of correct guessing [18].”
Coarse-Grained Dynamic Differential Privacy Federated Learning based on D3QN
Yu, J., Wu, T., Shu, N., Wang, H., Yan, K., Qi, L., Jiang, R., & Chang, C. (2025) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn64981.2025.11228649
“(Sequential Composition [18]): Given m mechanisms M ( · ) satisfying ( ε, δ ) -DP, the m -fold adaptive composition satisfies ( mε, mδ ) -DP. Lemma 1 demonstrates that the combination of multiple ( ε, δ ) -DP mechanisms also satisfies DP.”
Differential Privacy: 6 Key Equations Explained
Tiwari, A. (2024) · doi:10.59350/76egt-nwz87
The Asymptotic Behavior of Information Leakage Metrics
Taylor, S., Vippathalla, P. K., & Coon, J. P. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3646586
“Index Terms —Information theoretic leakage metrics, privacy, composition theorems, pointwise leakage, global leakage, method of types.”
Differential Privacy and Homomorphic Encryption in Healthcare Artificial Intelligence
Shafik, W., Tufail, A., Silva, L. C. D., & Apong, R. A. A. H. M. (2026) · Studies in computational intelligence · doi:10.1007/978-3-032-03985-9_8
Adapting to Noise Tails in Private Linear Regression
Chang, J., Yang, L., Zha, M., & Zhou, W.-X. (2026) · Journal of the American Statistical Association · doi:10.1080/01621459.2026.2644613
The Devil Within, The Cure Without: Securing Locally Private Graph Learning under Poisoning
He, L., Tang, P., Sun, L., & Su, S. (2026) · International World Wide Web Conference (WWW) · doi:10.1145/3774904.3792102
Heterogeneous Privacy-Preserving Federated Learning for Edge Intelligence
Zhang, Z., WU, L., Cui, H., Wang, Z., Huo, L., Wang, J., & Hu, S. (2026) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2026.3685129 · Cited by 1
DIARY: Differentially Private Recovery with Adaptive Privacy Budgets in Federated Unlearning
Wang, H., Dai, L., Zhang, X., Chen, H., Hu, J. M., & Yang, K. (2026) · International World Wide Web Conference (WWW) · doi:10.1145/3774904.3792423
A Fast Differentially Private Distributed Algorithm Over Unbalanced Directed Networks
Ran, M., Wang, Z. X., Lei, Y., & Li, H. (2026) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2026.3691978
“…a sensitivity perspective, the Laplace mechanism is typically calibrated to the (cid:4) 1 -sensitivity, whereas the Gaussian mechanism is calibrated to the (cid:4) 2 -sensitivity [14], making it more compatible with vector-valued updates and Euclidean-norm-based analysis in iterative algorithms.”
Prism: Private Relational Data Synthesis with Language Models
Guan, G., & Ge, C. (2026) · Proceedings of the ACM on Management of Data · doi:10.1145/3802102 · Cited by 1
Yuan, M., & Yu, R. (2026) · Mathematics · doi:10.3390/math14101731
PC-FT: A Lightweight and Utility-Preserving Private Fine-Tuning Framework for Edge-Based Agentic AI
Zhang, P., Zhang, R., Lv, Z., Fan, Q., Yuan, S., & Guan, Z. (2026) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2026.3694751
“In other words, the resulting relevance signals are inevitably noisy [34], [35].”
Exploring Hardware-Driven Privacy Techniques for Trustworthy Machine Learning
Haider, M. H., Zhang, H., & Ko, S. (2026) · Springer eBooks · doi:10.1007/978-3-032-17948-7_11
Privacy-Conscious Algorithm Design Via PAC Privacy
Sridhar, M., Zhu, X., & Devadas, S. (2026) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp63933.2026.00147
“In particular, ϵ - DP can be converted into a posterior success rate guarantee via the following equation [14], [24]: Thus, a PAC Privacy budget MI = 2 − 8 corresponds to a posterior success rate of 54% under a prior of 0 .”
RandModShift: Model and Data Privacy in Federated Inference
Kherani, N. A., Mitra, U., Sarwate, A. D., & Bloch, M. R. (2026) · IEEE International Conference on Communications workshops · doi:10.1109/iccworkshops63917.2026.11586691
“…( ε, δ ) - differentially private ( ( ε, δ ) -DP) if for all datasets D , D ′ , differing in one element, and for any measurable set S , This privacy definition has a hypothesis testing interpretation [25], [26]: an adversary observing the output of M wishes to test whether the input was D or D ′ .”
Adaptive Composition Theorems: Degeneracy Conditions and Leakage Growth
Issa, I., Shkel, Y. Y., & Cung, R. D. H. (2026) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit62367.2026.11653869
“This is reminiscent of composition results for differential privacy [6] and maximal leakage with binary inputs [16], where worst-case leakage under adaptive composition is also achieved by non-adaptive schemes.”
LAP 2 : Revisiting Laplace DP-SGD for High Dimensions via Majorization Theory
Mohammady, M., Yang, Q., Stout, N., Samreen, A., Wang, H., Quinn, C. J., & Hong, Y. (2026) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf68417.2026.00013
“Stronger composition theorems, such as the advanced composition theorem [28], provide tighter bounds.”
Zhang, X., Gao, T., & Jiang, Y. (2026) · Electronics · doi:10.3390/electronics15184091
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.