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 201–300 of 404
Secure Aggregation Is Not Private Against Membership Inference Attacks
Ngo, K., Östman, J., Durisi, G., & Amat, A. G. I. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-70365-2_11 · Cited by 17
Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme
Nikolakakis, K. E., Kalogerias, D. S., Sheffet, O., & Sarwate, A. D. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3081525 · Cited by 11
“8We could have used the notion of approximate ( , δ)-DP to reduce our total privacy loss by a factor of √ K by relaying on the advanced composition theorem [71], [72].”
MethodDesensitization method of meteorological data based on differential privacy protection
Zhang, F., Zhang, Y., & Zhang, Y. (2023) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2023.136117 · Cited by 8
Privacy-Preserving Federated Singular Value Decomposition
Liu, B., Pejó, B., & Tang, Q. (2023) · Applied Sciences · doi:10.3390/app13137373 · Cited by 8
“Besides this basic loose composition, one can obtain 244 better results by utilizing more involved composition theorems such as in [31].”
MethodDifferentially private multi-party computation
Kairouz, P., Oh, S., & Viswanath, P. (2016) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2016.7460489 · Cited by 10
“The dominance of this randomized response follows from a more general result proved in [34] which introduces a new operational interpretation of differential privacy mechanisms that provides strong analytical tools to compare privacy mechanisms.”
BackgroundMethodInfluentialSelf-citationQuantifying identifiability to choose and audit ϵ in differentially private deep learning
Bernau, D., Eibl, G., Grassal, P. W., Keller, H., & Kerschbaum, F. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3484224.3484231 · Cited by 16
“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)…”
BackgroundRethinking Information Sharing for Actionable Threat IntelligencePreprint
Mohaisen, A., Alibrahim, O., Kamhoua, C., Kwiat, K. A., & Njilla, L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.00548 · Cited by 8
“[17] have proposed a composition theorem for differential privacy that characterize the level of overall privacy degradation as a function of the number of queries based on hypothesis testing.”
BackgroundOptimal Differential Privacy Composition for Exponential Mechanisms and the Cost of AdaptivityPreprint
Dong, J., Durfee, D., & Rogers, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.13830 · Cited by 10
“4 in [14], which is a rephrasing of the original optimal composition formulation in [11], where we replace ε with ε/2.”
BackgroundMethodResultInfluentialDifferential privacy in the shuffle model
Cheu, A. (2021) · Digital Repository Service (Northeastern University) · doi:10.17760/d20409473 · Cited by 13
Energy-Efficient Privacy-Preserving Time-Series Forecasting on User Health Data Streams
Arsalan, M., Matteo, D. D., Imtiaz, S., Abbas, Z., Vlassov, V., & Іссаков, В. (2022) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom56396.2022.00080 · Cited by 8
“When an algorithm requires multiple additive noise mechanisms, the privacy guarantees follow from the basic DP composition theorem [17], [18] or advanced composition theorems [19]–[21].”
MethodSu, W. (2024) · Annual Review of Statistics and Its Application · doi:10.1146/annurev-statistics-112723-034158 · Cited by 10
Variable-Length Coding with Zero and Non-Zero Privacy Leakage
Zamani, A., & Skoglund, M. (2025) · Entropy · doi:10.3390/e27020124 · Cited by 7
“Further privacy leakage measures, such as the differential privacy introduced in [28], ( ϵ , δ ) -differential privacy [29], local differential privacy [30–33], maximal leakage [12], and lift [27], have been used in the literature.”
Cost-Efficient and Secure Federated Learning for Edge Computing
Zhang, Z., Wu, L., Wang, Z., Hu, J., Ma, C., & Liu, Q. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3590799 · Cited by 11
“Theorem 1 (Sequential Composition [36]): [36]): To protect the privacy of FL, we adopt DP based on the Analytic Gaussian Mechanism.”
Ma, F., Zhu, R., & Wang, P. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3364496 · Cited by 7
“Therefore, more effort has been done in order to make improvement on mechanisms of such type in the last years [28].”
BackgroundHistory-Aware Privacy Budget Allocation for Model Training on Evolving Data-Sharing Platforms
Xiao, L., Zhang, X., Wu, D., Hu, M., Zhou, Y., & Yu, S. (2024) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2024.3451187 · Cited by 7
Position: Membership Inference Attacks Cannot Prove That a Model was Trained on Your Data
Zhang, J., Das, D., Kamath, G., & Tramèr, F. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00025 · Cited by 77
“In a similar vein, MI attacks can be used to audit implementations of differentially private machine learning [20, 29, 37], by drawing on a hypothesis testing interpretation of differential privacy [40, 21].”
Privacy-Aware Controllable Compressed Data Publishing Against Sparse Estimation Attack in IoT
Wang, M., Xiao, D., Xiang, Y., & Wang, H. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2916109 · Cited by 7
“Differential privacy [23]–[27]”
Pankova, A., & Laud, P. (2022) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf54842.2022.9919656 · Cited by 7
“Theorem 3 (Sequential composition [14]).”
Cohere: Managing Differential Privacy in Large Scale Systems
Küchler, N., Opel, E., Lycklama, H., Viand, A., & Hithnawi, A. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00122 · Cited by 12
“Specifically, generic (approximate DP) composition [43], [58] generally introduces a significant gap between the actual privacy cost and the bounds they provide.”
BackgroundPrivacy: A few definitional aspects and consequences for minimax mean-squared error
Barber, R. F., & Duchi, J. C. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039572 · Cited by 7
Oblivious Mechanisms in Differential Privacy: Experiments, Conjectures, and Open Questions
Chen, C., Pal, R., & Golubchik, L. (2016) · IEEE Security and Privacy Workshops (SPW) · doi:10.1109/spw.2016.27 · Cited by 7
“However, this bound is known to be loose [10].”
BackgroundCactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime
Alghamdi, W., Asoodeh, S., Calmon, F. P., Kosut, O., Sankar, L., & Wei, F. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834438 · Cited by 9
A Central Limit Theorem for Differentially Private Query AnsweringPreprint
Dong, J., Su, W., & Zhang, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.08721 · Cited by 8
Differentially Private Multi-party Computation: Optimality of Non-Interactive Randomized ResponsePreprint
Kairouz, P., Oh, S., & Viswanath, P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.1546 · Cited by 10
“The dominance of this randomized response follows from a more general result proved in [34] which introduces a new operational interpretation of differential privacy mechanisms that provides strong analytical tools to compare privacy mechanisms.”
BackgroundMethodInfluentialSelf-citationFlow-Based Distributionally Robust Optimization
Xu, C., Lee, J., Cheng, X., & Xie, Y. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3370699 · Cited by 24
“DP can be understood as a hypothesis-testing problem [4], [16], [30], [52].”
BackgroundInfluentialYhdego, T. O., Wang, H., Chi, H., & Yu, Z. (2024) · Journal of Computing and Information Science in Engineering · doi:10.1115/1.4067086 · Cited by 9
Heterogeneous differential privacy for vertically partitioned databases
Xia, Y., Zhu, T., Ding, X., Jin, H., & Zou, D. (2019) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.5607 · Cited by 6
Understanding Privacy-Utility Tradeoffs in Differentially Private Online Active Learning
Bittner, D. M., Brito, A. E., Ghassemi, M., Rane, S. D., Sarwate, A. D., & Wright, R. N. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.720 · Cited by 6
“Standard composition theorems [31, 36] allows us to find the overall differential privacy guarantee under each scenario under either Bernoulli or exponential sampling.”
BackgroundInformation-Theoretic Stability and Generalization
Raginsky, M., Rakhlin, A., & Xu, A. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108616799.011 · Cited by 14
Privacy-preserving Q-Learning with Functional Noise in Continuous State SpacesPreprint
Wang, B., & Hegde, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.10634 · Cited by 13
“With arguments similar to those in (Kairouz et al., 2013), we choose = T∆ 2 2σ2B + √ 2T∆2w σ2B so that the first term is e−w and the second term is 1”
BackgroundMethodInfluentialTighter Generalization Bounds for Iterative Differentially Private Learning AlgorithmsPreprint
He, F., Wang, B., & Tao, D. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.09371 · Cited by 8
“The approximation of factor δ in our composition theorems is tighter than the tightest existing result [31] by δ eε − 1 eε + 1 (”
BackgroundInfluentialGeneralization Techniques Empirically Outperform Differential Privacy against Membership InferencePreprint
Liu, J., Oya, S., & Kerschbaum, F. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.05524 · Cited by 12
Synthetic Tabular Data: Methods, Attacks and Defenses
Cormode, G., Maddock, S., Ullah, E., & Gade, S. (2025) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3711896.3736562 · Cited by 16
Canonical noise distributions and private hypothesis tests
Awan, J., & Vadhan, S. (2023) · The Annals of Statistics · doi:10.1214/23-aos2259 · Cited by 9
An Adaptive Composition Theorem for Maximal Leakage for Binary Inputs
Issa, I., & Wagner, A. B. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834392 · Cited by 5
CovidTrak: A Vision on Social Intelligence-Empowered COVID-19 Contact Tracing
Rashid, M. T., & Wang, D. (2022) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2022.3195103 · Cited by 8
“Anotheremerging area of data sparsity-aware privacy preservation schemes is differential privacy, where noise is deliberately injected into the user data to conceal the sensitive information of users [103], [137].”
BackgroundAdaptive Differential Privacy Budget Allocation Algorithm Based on Random Forest
Wang, C.-Y., Chen, S., & Li, X. (2022) · Communications in computer and information science · doi:10.1007/978-981-19-1256-6_15 · Cited by 5
Tchouka, Y., Couchot, J.-F., Laiymani, D., Selles, P., & Rahmani, A. (2024) · Intelligent Systems with Applications · doi:10.1016/j.iswa.2024.200416 · Cited by 8
Local Differential Privacy for Belief Functions
Li, Q., Zhou, C., Qin, B., & Xu, Z. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i9.21241 · Cited by 9
Strong Asymptotic Composition Theorems for Mutual Information Measures
Wu, B., Wagner, A. B., Issa, I., & Suh, G. E. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3228519 · Cited by 7
“In practice, attacks are often sequential in nature, whether the application is side channels in computer security [1], [2], [3] or database privacy [4], [5], [6].”
BackgroundExactly Optimal and Communication-Efficient Private Estimation via Block Designs
Park, H.-Y., Nam, S.-H., & Lee, S.-H. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3381195 · Cited by 8
“…notions of privacy constraints [9], [10], [11], [12], local differential privacy (LDP) is widely adopted and applied both in academia and industry due to its powerful privacy guarantee, operational meaning, and useful properties such as composability and robustness to post-processing [10], [13].”
Bridging Quantum Computing and Differential Privacy: Insights into Quantum Computing Privacy
Zhao, Y., Zhong, H., Zhang, X., Li, Y., Zhang, C., & Pan, M. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00012 · Cited by 17
“One of the most important properties of DP is composability, which dictates how to combine multiple privacy mechanisms [31], [65].”
A Blockchain-Based Approach for Saving and Tracking Differential-Privacy CostPreprint
Zhao, Y., Zhao, J., Kang, J., Zhang, Z., Niyato, D. T., & Shi, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.09259 · Cited by 5
“Although [26] gives the state-of-the-art results for the composition of differentially private algorithms, the results do not assume the underlying mechanisms to achieve DP.”
BackgroundCan Stochastic Gradient Langevin Dynamics Provide Differential Privacy for Deep Learning?
Heller, G., & Fetaya, E. (2023) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml54575.2023.00015 · Cited by 5
“Available: https://proceedings.mlr.press/v37/kairouz15.html [41] C. J. Clopper and E. S. Pearson, “The use of confidence or fiducial limits illustrated in the case of the binomial,” Biometrika, vol. 26, pp. 404–413, 1934.”
MethodAn Intelligent Edge Dual-Structure Ensemble Method for Data Stream Detection and Releasing
Zhang, J., Gong, B., Wang, Q., Wu, Y., & Zheng, G. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3286185 · Cited by 6
“The data releasing process is described using a Gaussian combination mechanism [35]. b) Adjustable Gaussian mechanism: Here, D represents the data sample set containing private information; V 1 and V 2 represent noise distributions that follow Gaussian distribution.”
MethodBlock Design-Based Local Differential Privacy Mechanisms
Park, H., Nam, S.-H., & Lee, S.-H. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206918 · Cited by 3
Differentially Private Synthetic Data Generation via Lipschitz-Regularised Variational Autoencoders
Groß, B., & Wunder, G. (2023) · IEEE Smart World Congress (SWC) · doi:10.1109/swc57546.2023.10449297 · Cited by 6
“In [13], a characterization of DP as a hypothesis test problem is provided.”
BackgroundInfluentialRényi Differential Privacy in the Shuffle Model: Enhanced Amplification Bounds
Chen, E., Cao, Y., & Ge, Y. (2024) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp48485.2024.10446115 · Cited by 3
SoK: A Review of Differentially Private Linear Models For High-Dimensional Data
Khanna, A., Raff, E., & Inkawhich, N. (2024) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml59370.2024.00012 · Cited by 6
“Similarly, for adaptive composition of ( (cid:2), δ ) DP algorithms, the advanced composition theorem shows a k -fold composition is ( (cid:2) (cid:2) , kδ + δ (cid:2) ) DP [13].”
Differentially Private Stream Processing at Scale
Zhang, B., Doroshenko, V., Kairouz, P., Steinke, T., Thakurta, A., Ma, Z., Cohen, E., Apte, H., & Spacek, J. (2024) · Proceedings of the VLDB Endowment · doi:10.14778/3685800.3685833 · Cited by 17
Self-citationDifferential Privacy in Geotechnical Engineering
Murakami, T., Wu, S., Zhang, J., Zhang, D., Asano, K., Otake, Y., & Phoon, K. (2024) · Geodata and AI. · doi:10.1016/j.geoai.2025.100004 · Cited by 6
Membership inference attack on differentially private block coordinate descent
Riaz, S., Ali, S., Wang, G., Latif, M. A., & Iqbal, M. Z. (2023) · PeerJ Computer Science · doi:10.7717/peerj-cs.1616 · Cited by 6
“Each of these mechanisms has its privacy guarantee incurring a privacy cost following the basic composition theorem ( Dwork et al., 2006a ; Dwork & Lei, 2009 ) and subsequently its advanced, re fi ned versions ( Dwork & Rothblum, 2016 ; Kairouz, Oh & Viswanath, 2015 ).”
BackgroundDifferentially Private Deep Q-Learning for Pattern Privacy Preservation in MEC Offloading
Gan, S., Siew, M., Xu, C., & Quek, T. Q. S. (2023) · International Conference on Communications · doi:10.1109/icc45041.2023.10278840 · Cited by 4
“Finally, according to the composition theorem in [20], multiple iterations in our proposed algorithm provide a privacy guarantee.”
MethodProtect Your Score: Contact-Tracing with Differential Privacy Guarantees
Romijnders, R., Louizos, C., Asano, Y. M., & Welling, M. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i13.29402 · Cited by 8
Differentially Private Big Data Publication via Structural Inference and Community Detection
Dong, K., Liu, Z., Xu, Y., & Li, Z. (2017) · International Symposium on Pervasive Systems, Algorithms and Networks (ISPAN) · doi:10.1109/ispan-fcst-iscc.2017.40 · Cited by 4
“Since E = E1 ∪ E2, according to the parallel composition property [13] of differential privacy, DCHRG satisfies differential privacy with privacy budget max( , 2) = .”
BackgroundOnline Algorithm for Differentially Private Genome-wide Association Studies
Aziz, M. M. A., Kamali, S., Mohammed, N., & Jiang, X. (2021) · ACM Transactions on Computing for Healthcare · doi:10.1145/3431504 · Cited by 9
“Formally, Lemma 2 (Seqential Composition [38]).”
BackgroundInfluentialMinimax Rates of Estimating Approximate Differential Privacy
Liu, X., & Oh, S. (2019) · arXiv · doi:10.48550/arxiv.1905.10335 · Cited by 4
Self-citationKim, M., Günlü, O., & Schaefer, R. F. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.04737 · Cited by 4
Dubey, M., Tembhurne, J. V., & Makhijani, R. (2025) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2025.3575420 · Cited by 7
“Theorem: Let D and D’ be two neighboring datasets that differ with one element [64].”
Budget Recycling Differential Privacy
Jiang, B., Du, J., Sharma, S., & Yan, Q. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00212 · Cited by 3
“:3) and δ both increase linearly with the number of queries [2] (or sublinearly with advanced composition [26]).”
BackgroundThe 2020 US Decennial Census is more private than you (might) think
Su, B., Su, W., & Wang, C. (2025) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2500337122 · Cited by 10
“‖ From a technical standpoint, accurately accounting for privacy loss under composition using ( ϵ, δ )-DP alone is difficult (36).”
Composition properties of Bayesian differential privacy
Zhao, J. (2017) · IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) · doi:10.1109/pimrc.2017.8292647 · Cited by 3
“[22] investigate the overall privacy cost for the composition of differential private algorithms.”
BackgroundPrivacy Accounting and Quality Control in the Sage Differentially Private ML Platform
Lécuyer, M., Spahn, R., Vodrahalli, K., Geambasu, R., & Hsu, D. (2019) · ACM SIGOPS Operating Systems Review · doi:10.1145/3352020.3352032 · Cited by 5
“basic composition [17], strong composition [21], and variations thereof [28]) analyze Alg.”
The Evolving Path of “the Right to Be Left Alone” - When Privacy Meets Technology
Iezzi, M. (2021) · IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA) · doi:10.1109/tpsisa52974.2021.00025 · Cited by 3
Dynamic Global Sensitivity for Differentially Private Contextual Bandits
Wang, H., Zhao, D., & Wang, H. (2022) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/3523227.3546781 · Cited by 4
“Based on composition theorem of differential privacy [17, 20], the final output, the sum of (ε ′, δ ′)-differentially private partial sums, is (ε, δ)-differentially private.”
BackgroundLossy Compression of Noisy Data for Private and Data-Efficient Learning
Isik, B., & Weissman, T. (2022) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2023.3260720 · Cited by 3
“Under this scenario, by the composition theorem for differential privacy [34], ( , δ)-differential privacy is satis-”
Differentially-Private Collaborative Online Personalized Mean Estimation
Yakimenka, Y., Weng, C.-W., Lin, H.-Y., Rosnes, E., & Kliewer, J. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206796 · Cited by 3
Schrödinger Mechanisms: Optimal Differential Privacy Mechanisms for Small Sensitivity
Alghamdi, W., Asoodeh, S., Calmon, F. P., Gomez, J. F., Kosut, O., & Sankar, L. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206616 · Cited by 7
Mixup Training for Generative Models to Defend Membership Inference Attacks
Ji, Z., Hu, Q., Xiang, L., & Zhou, C. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10229036 · Cited by 3
“According to [20] (see the proof of Remark.”
BackgroundTackling Privacy Heterogeneity in Federated Learning
Xu, R., Zhang, Y. A., & Huang, J. (2023) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt58741.2023.10349854 · Cited by 5
“If the data is subsampled by a ratio r without replacement, the mechanism under subsampling satisfies ( ϵ, δ ) -DP. Lemma 2 (Gaussian mechanism with strong composition theorem [12]) .”
MethodPrivacy-Preserving Visualization of Brain Functional Network Connectivity
Tao, Y., Sarwate, A. D., Panta, S. R., Plis, S., & Calhoun, V. D. (2024) · IEEE International Symposium on Biomedical Imaging (ISBI) · doi:10.1109/isbi56570.2024.10635222 · Cited by 4
“We explore (adaptive) composition techniques [14, 15, 16, 17] to quantify the risk of multiple releases.”
BackgroundMethodPrivacy Preserving Semi-Decentralized Mean Estimation Over Intermittently-Connected Networks
Saha, R., Seif, M., Yemini, M., Goldsmith, A. J., & Poor, H. V. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3473939 · Cited by 9
“Since the PS receives multiple copies of the data of any specific client i (upto scaling and additive noise) from multiple node relays, the privacy guarantee at the PS can be obtained using composition theorem [43].”
MethodImproving the Privacy Loss Under User-Level DP Composition for Fixed Estimation Error
Rameshwar, V. A., Tandon, A., & Sharma, A. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195471 · Cited by 3
“3.5], [13], [14].”
InfluentialStrong Asymptotic Composition Theorems for Sibson Mutual Information
Wu, B., Wagner, A. B., Suh, G. E., & Issa, I. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174456 · Cited by 3
“In practice, attacks are often sequential in nature, whether the application is side channels in computer security [1]–[3] or database privacy [4]–[6].”
BackgroundPrivacy-aware data publishing against sparse estimation attack
Wu, X., Yang, P., Tang, S., Zheng, X., & Wang, X. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.02.016 · Cited by 3
Information and Estimation Theoretic Approaches to Data Privacy
Asoodeh, S. (2017) · QSpace (Queen's University Library) · Cited by 3
Local Differential Privacy in Decentralized OptimizationPreprint
Xiao, H., Ye, Y., & Devadas, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.06101 · Cited by 5
Differential privacy for survival analysis and user data collection
Nguyen, T. T. (2019) · doi:10.32657/10220/48212 · Cited by 3
“Recently, Kairouz [64] investigated the problem of privacy degradation and improved the above result to e′ = O ( ke2 + e √ k log(e + (e √ k/δ′)) ) .”
BackgroundPrivacy-preserving biomedical database queries with optimal privacy-utility trade-offsPreprint
Cho, H., Simmons, S., Kim, R., & Berger, B. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.01.16.909010 · Cited by 3
Oneshot Differentially Private Top-k SelectionPreprint
Qiao, G., Su, W., & Zhang, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.08233 · Cited by 5
“The difficulty of this approach is in untangling the complex distribution dependence of the k selected items, as opposed to the conditional dependence in other existing mechanisms, which allows us to use the advanced composition theorem (Dwork et al. (2010), see also Kairouz et al. (2017)).”
MethodPrivacy-preserving data analytics
Zhao, Y. (2022) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/160032 · Cited by 3
Precise and Privacy-Preserving Tampering Detection Model for Document Images
Xing, B., Le, J., Zhu, F., Li, D., Zhou, Y., Wang, W., Wang, Y., Liu, Y., & Liao, X. (2025) · IEEE Transactions on Consumer Electronics · doi:10.1109/tce.2025.3621056 · Cited by 2
“Formally, if mechanisms are then the sequence of these mechanisms provides ( ki = 1 ε i )-DP. 4) Parallel Composition Theorem [44]: The Parallel Composition Theorem addresses the scenario where multiple differentially private analyses are performed on disjoint subsets of the data.”
Federated Learning on Riemannian Manifolds with Differential Privacy
Huang, Z., Huang, W., Jawanpuria, P., & Mishra, B. (2026) · Machine Learning · doi:10.1007/s10994-026-07018-w · Cited by 13
Deep Learning Algorithms Design and Implementation Based on Differential Privacy
Xu, X., Yao, Y., & Cheng, L. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-62223-7_27 · Cited by 2
Iwahana, K., Yanai, N., Cruz, J. P., & Fujiwara, T. (2022) · Journal of Information Processing · doi:10.2197/ipsjjip.30.209 · Cited by 4
Differential Privacy and Its Challenges: A Literature Review
Nisha, N., Singhal, A., & Muttoo, S. K. (2023) · Lecture notes in networks and systems · doi:10.1007/978-981-19-9304-6_64 · Cited by 3
Privacy-Preserving SGD on Shuffle Model
Zhang, L., & Zhang, H. F. (2023) · Journal of Mathematics · doi:10.1155/2023/4055950 · Cited by 2
D2-PSD: Dynamic Differentially-Private Spatial Decomposition in Collaboration With Edge Server
Sasada, T., Taenaka, Y., & Kadobayashi, Y. (2024) · IEEE Access · doi:10.1109/access.2024.3485610 · Cited by 2
“Building upon the parallel composition theorem [31], [32] in the context of CDP and LDP, and PSD, this study defines the direct sum decomposition of the privacy parameter as decomposition.”
MethodNavigating Differential Privacy Constraints in Machine Learning
Ha, T., & Dang, T. K. (2024) · Communications in computer and information science · doi:10.1007/978-981-96-0437-1_2 · Cited by 2
Ryffel, T., Créquit, P., Baillet, M., Paumier, J., Marfoq, Y., Girardot, O., Chanet, T., Sy, R., Bayssat, L., Mazières, J., et al. (2025) · JMIR Medical Informatics · doi:10.2196/59685 · Cited by 3
Differentially Private Online Federated Learning with Correlated Noise
Zhang, J., Zhu, L., & Johansson, M. (2024) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc56724.2024.10886177 · Cited by 2
“However, the injection of iid noise into the learning process also reduces the utility [12], [13].”
Differentially Private Distribution Estimation Using Functional Approximation
Tao, Y., & Sarwate, A. D. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10890461 · Cited by 4
“The composition property [23], [31]–[35] allows for a modular design of mechanisms: if each component of a mechanism is differentially private, then their composition also preserves differential privacy.”
Hyperparameters in Score-Based Membership Inference Attacks
Pradhan, G., Jälkö, J., Tobaben, M., & Honkela, A. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00027 · Cited by 4
“We compute the upper bound using the method of [35] described in Theorem 2.1.”
InfluentialDifferentially Private Parameter Estimation: Optimal Noise Insertion and Data Owner Selection
Cao, X., & Başar, T. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9304375 · Cited by 2
“A composition theorem was developed for computing differential privacy under sequential queries in [5].”
MethodData Privacy for a ρ-Recoverable Function
Nageswaran, A., & Narayan, P. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437327 · Cited by 2
Kaissis, G. A., Knolle, M. A., Jungmann, F., Ziller, A., Usynin, D., & Rueckert, D. (2022) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.807 · Cited by 7
Iwahana, K., Yanai, N., Cruz, J. P., & Fujiwara, T. (2022) · Lecture notes in computer science · doi:10.1007/978-3-030-93944-1_6 · Cited by 2
Geo-Graph-Indistinguishability: Location Privacy on Road Networks Based on Differential PrivacyPreprint
Takagi, S., Cao, Y., Asano, Y., & Yoshikawa, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.13449 · Cited by 2
“The first is to develop a mechanism for multiple perturbations that satisfies existing notions, such as differential privacy and Geo-I [12], [14].”
BackgroundAdaptive Differentially Private Empirical Risk MinimizationPreprint
Wu, X., Wang, L., Cristali, I., Gu, Q., & Willett, R. M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.07435 · Cited by 7
Experimental Evaluation for Risk Assessment of Privacy Preserving Synthetic Data
Chida, K., Kakuta, S., Itakura, H., Ishihara, I., Yoshioka, K., & Takeuchi, H. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68208-7_19 · Cited by 1
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.