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 101–200 of 404
DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy
Zhang, Q., Lee, H., Ma, J., Lou, J., Yang, C., & Xiong, L. (2024) · International World Wide Web Conference (WWW) · doi:10.1145/3589334.3645531 · Cited by 49
Saeidian, S., Cervia, G., Oechtering, T. J., & Skoglund, M. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3304378 · Cited by 55
“For example, Wasserman and Zhou [22] and Kairouz et al. [23] have shown that differential privacy imposes a tradeoff between Type I and Type II error probabilities of a hypothesis testing adversary who wishes to determine whether or not a data point is included in a database.”
BackgroundA Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergences
Asoodeh, S., Liao, J., Calmon, F. P., Kosut, O., & Sankar, L. (2020) · 2020 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174015 · Cited by 28
“[3] as a method to bypass advanced composition theorems [11, 12].”
BackgroundMethodLinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at ScalePreprint
Rogers, R., Subramaniam, S., Peng, S. X., Durfee, D., Lee, S., Kancha, S. K., Sahay, S., & Ahammad, P. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.05839 · Cited by 29
“We now state the result from [2] and [18] that tightens the composition bound from Durfee and Rogers [12] which itself improved on the more general optimal DP composition bounds [19, 20].”
BackgroundOn Binary Decomposition Based Privacy-Preserving Aggregation Schemes in Real-Time Monitoring Systems
Yang, X., Ren, X., Lin, J., & Yu, W. (2016) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2016.2516983 · Cited by 28
“Although Kairouz [53] gave amuch tighter bound on the privacy bugdet, their work still showed the overall degradation is inevitable with the increase of query number.”
Model selection and error estimation without the agonizing pain
Oneto, L. (2018) · Wiley Interdisciplinary Reviews Data Mining and Knowledge Discovery · doi:10.1002/widm.1252 · Cited by 27
“…Dwork, Rothblum, & Vadhan, 2010; Jain & Thakurta, 2014; Kairouz, Oh, & Viswanath, 2015; Kusner, Gardner, Garnett, & Weinberger, 2015; Lei, 2011; Oh & Viswanath, 2015; Rogers, Vadhan, Lim, & Gaboardi, 2016; Song, Chaudhuri, & Sarwate, 2013; Steinke & Ullman, 2015; Williams & McSherry, 2010) and…”
Locally Differentially Private Sparse Vector Aggregation
Zhou, M., Wang, T., Chan, T.-H. H., Fanti, G. C., & Shi, E. (2022) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46214.2022.9833635 · Cited by 41
DP-Norm: Differential Privacy Primal-Dual Algorithm for Decentralized Federated Learning
Fukami, T., Murata, T., Niwa, K., & Tyou, I. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3390993 · Cited by 34
“Then, to find the smallest possible DP noise size σ i satisfying (6), we adopt the tight analysis of the advanced composition theorem given in [24].”
MethodInfluentialDifferentially Private Speaker Anonymization
Shamsabadi, A. S., Srivastava, B. M. L., Bellet, A., Vauquier, N., Vincent, E., Maouche, M., Tommasi, M., & Papernot, N. (2023) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2023-0007 · Cited by 58
Tight on Budget? Tight Bounds for r-Fold Approximate Differential Privacy
Meiser, S., & Mohammadi, E. (2018) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3243734.3243765 · Cited by 67
“Our approach is sufficiently general to subsume the generic adaptive r -fold ADP bounds of prior work [14, 21].”
BackgroundMethodInfluentialInvestigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing
Liu, C., He, X., Chanyaswad, T., Wang, S., & Mittal, P. (2019) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2019-0045 · Cited by 31
Privacy Preserving Distributed Deep Learning and Its Application in Credit Card Fraud Detection
Wang, Y., Adams, S., Beling, P. A., Greenspan, S. L., Rajagopalan, S., Velez-Rojas, M., Mankovski, S., Boker, S. M., & Brown, D. E. (2018) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom/bigdatase.2018.00150 · Cited by 38
“When the private data set is queried by a composition of algorithms, the consumed privacy budget will sum up following the composition theorems for differential privacy [23].”
MethodNetwork Traffic Shaping for Enhancing Privacy in IoT Systems
Xiong, S., Sarwate, A. D., & Mandayam, N. B. (2022) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3140174 · Cited by 38
Investigating Membership Inference Attacks under Data Dependencies
Humphries, T., Oya, S., Tulloch, L., Rafuse, M., Goldberg, I., Hengartner, U., & Kerschbaum, F. (2023) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf57540.2023.00013 · Cited by 81
“[31] show that, for an adversary that wants to distinguish between two neighbouring inputs of a DP mechanism, the following bounds on the adversary’s TPR and FPR hold:”
BackgroundDifferentially-Private "Draw and Discard" Machine Learning
Pihur, V., Korolova, A., Liu, F., Sankuratripati, S., Yung, M., Huang, D., & Zeng, R. (2018) · arXiv · doi:10.48550/arxiv.1807.04369 · Cited by 25
“le privacy parameter, but allow multiple collections from the same user over time. Formally, this corresponds to the privacy loss growing as the number of items submitted, as per composition theorems [14, 24]. 6.3.1 Feature-level Privacy. We offer feature-level local differential privacy and, therefore, in a situation…”
BackgroundInfluentialIntegrating Technical and Legal Concepts of Privacy
Sokolovska, A., & Kocarev, L. (2018) · IEEE Access · doi:10.1109/access.2018.2836184 · Cited by 24
“The differential privacy literature provides many tools for addressing this problem, ranging from simple [51] to sophisticated [92], [93], each with its own strengths and weaknesses [59].”
BackgroundPrivacy-Preserving Biomedical Database Queries with Optimal Privacy-Utility Trade-Offs
Cho, H., Simmons, S., Kim, R., & Berger, B. (2020) · Cell Systems · doi:10.1016/j.cels.2020.03.006 · Cited by 33
Comparing Local and Central Differential Privacy Using Membership Inference Attacks
Bernau, D., Robl, J., Grassal, P. W., Schneider, S., & Kerschbaum, F. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-81242-3_2 · Cited by 33
Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning PossiblePreprint
Zheng, K., Mou, W., & Wang, L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.03316 · Cited by 40
“[20] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.”
BackgroundMethodFederated $f$-Differential PrivacyPreprint
Zheng, Q., Chen, S., Long, Q., & Su, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.11158 · Cited by 37
Differentially Private Regression Diagnostics
Chen, Y., Machanavajjhala, A., Reiter, J. P., & Barrientos, A. F. (2016) · Proceedings · doi:10.1109/icdm.2016.0019 · Cited by 23
“provided inequalities governing the trade-off between false-alarm and missed-detection in [10].”
BackgroundThe influence of differential privacy on short term electric load forecasting
Eibl, G., Bao, K., Grassal, P.-W., Bernau, D., & Schmeck, H. (2018) · Energy Informatics · doi:10.1186/s42162-018-0025-3 · Cited by 23
Distribution-invariant differential privacy
Bi, X., & Shen, X. (2022) · Journal of Econometrics · doi:10.1016/j.jeconom.2022.05.004 · Cited by 35
Edge-Protected Triangle Count Estimation Under Relationship Local Differential Privacy
Liu, Y., Wang, T., Liu, Y., Chen, H., & Li, C. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3381832 · Cited by 34
“The key idea is that even if independent noise is injected into each query result to enforce ( ε, δ ) -DP, the overall privacy degrades eventually due to the continuous observation [14], [15], [16], [17].”
BackgroundModel-Protected Multi-Task Learning
Liang, J., Liu, Z., Zhou, J., Jiang, X., Zhang, C., & Wang, F. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3015859 · Cited by 25
Variational Bayes In Private Settings (VIPS)
Park, M., Foulds, J. R., Chaudhuri, K., & Welling, M. (2020) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.11763 · Cited by 40
Differentially Private Consensus and Distributed Optimization in Multi-Agent Systems: A Review
Wang, Y., Lin, H. S., Lam, J., & Kwok, K. (2023) · Neurocomputing · doi:10.1016/j.neucom.2024.127986 · Cited by 28
A Compression Perspective on Secrecy Measures
Shkel, Y. Y., & Poor, H. V. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3055692 · Cited by 24
Learning to Generate Image Embeddings with User-Level Differential Privacy
Xu, Z., Collins, M. D., Wang, Y., Panait, L., Oh, S., Augenstein, S., Liu, T., Schroff, F., & McMahan, H. B. (2023) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52729.2023.00770 · Cited by 48
“A DP guarantee with respect to the change of a single arbitrary training example is known as examplelevel DP, which provides plausible deniability (in the binary hypothesis testing sense of [38]) that any single example (e.”
BackgroundSelf-citationBiGRU-DP: Improved differential privacy protection method for trajectory data publishing
Shen, Z., Zhang, Y., Wang, H., Liu, P., Liu, K., & Shen, Y. (2024) · Expert Systems with Applications · doi:10.1016/j.eswa.2024.124264 · Cited by 20
Operational definitions for some common information leakage metrics
Issa, I., & Wagner, A. B. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006632 · Cited by 20
“[19] give an operational definition of differential privacy in the framework of hypothesis testing.”
BackgroundDecision Support for Sharing Data using Differential Privacy
John, M. F. S., Denker, G., Laud, P., Martiny, K., Pankova, A., & Pavlović, D. (2021) · IEEE Symposium on Visualization for Cyber Security (VIZSEC) · doi:10.1109/vizsec53666.2021.00008 · Cited by 19
Privacy-Constrained Parallel Distributed Neyman-Pearson Test
Li, Z., & Oechtering, T. J. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2623092 · Cited by 19
“In [15], the degradation of differential privacy level under adaptive interactions was characterized.”
BackgroundAn Effective Data Privacy Protection Algorithm Based on Differential Privacy in Edge Computing
Qiao, Y., Liu, Z., Lv, H., Li, M., Huang, Z., Li, Z., & Liu, W. (2019) · IEEE Access · doi:10.1109/access.2019.2939015 · Cited by 21
“This property indicates a combined algorithm consisting of a sequence of differential privacy protection models whose privacy protection level is the sum of all budgets[14].”
BackgroundReviewing and Improving the Gaussian Mechanism for Differential PrivacyPreprint
Zhao, J., Wang, T., Bai, T., Lam, K., Xu, Z., Shi, S., Ren, X., Yang, X., Liu, Y., & Yu, H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.12060 · Cited by 46
“Differential privacy [3] has received considerable interest [1], [4]–[11] since it provides a rigorous framework to quantify data privacy.”
BackgroundLearning discrete distributions: user vs item-level privacyPreprint
Liu, Y., Suresh, A. T., Yu, F., Kumar, S., & Riley, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.13660 · Cited by 58
Evaluation and utilisation of privacy enhancing technologies—A data spaces perspective
Auñón, J. M., Ramírez, D. H., Díaz, L. P., Peña, B. I., Rahmian, S., Al-Khazraji, Y., Soler-Garrido, J., & Kotsev, A. (2024) · Data in Brief · doi:10.1016/j.dib.2024.110560 · Cited by 34
“This scenario is addressed by the Composition Theorem (see [ 48 ] which establishes that the composition of k queries, each ( ε , δ )-differentially private, is bounded to ( k ε ,k δ ) or in other words, privacy is degraded with the number of analysis, but at the same time, it helps to define the…”
BackgroundMulti-Dimensional Randomized Response
Domingo‐Ferrer, J., & Soria-Comas, J. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3045759 · Cited by 22
“on of the dependences between attributes and the risk that results from applying RR to the resulting clusters of attributes. In differential privacy terms, the sequential composition property applies [18]: if the computation of the dependences between attributes is 1-differentially private and the RR data release is 2…”
BackgroundNoLeaks: Differentially Private Causal Discovery Under Functional Causal Model
Ma, P., Ji, Z., Pang, Q., & Wang, S. (2022) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2022.3184263 · Cited by 25
Measuring Linkability of Protected Biometric Templates Using Maximal Leakage
Shahreza, H. O., Shkel, Y. Y., & Marcel, S. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3266170 · Cited by 23
“A hypothesis testing perspective on differential privacy has been introduced in [24] and extended in [25].”
BackgroundAccuracy, Interpretability, and Differential Privacy via Explainable BoostingPreprint
Nori, H., Caruana, R., Bu, Z., Shen, J. H., & Kulkarni, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.09680 · Cited by 62
“We present two results for DP-EBMs: “EBM-Classic”, where we apply strong composition from (Kairouz et al., 2017), and “EBMGDP”, where composition is more tightly tracked via Gaussian Differential Privacy (Dong et al.”
MethodUniversal Neural-Cracking-Machines: Self-Configurable Password Models from Auxiliary Data
Pasquini, D., Ateniese, G., & Troncoso, C. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00032 · Cited by 25
“With H , we denote a secure cryptographic hash function, where H ( X )= { H ( x ) | x ∈ X } .”
BackgroundPrivacy Amplification of Iterative Algorithms via Contraction Coefficients
Asoodeh, S., Díaz, M., & Calmon, F. P. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174133 · Cited by 28
“One reason for its success is its operational significance, which can be best described in terms of binary hypothesis testing (see, e.g., [3, 4]).”
BackgroundResearch on an Ensemble Classification Algorithm Based on Differential Privacy
Jia, J., & Qiu, W. (2020) · IEEE Access · doi:10.1109/access.2020.2995058 · Cited by 20
“Definition 4 ( Exponential Mechanism [12], [16], [19]): Given a utility function q : ( D × O ) → r ( r ∈ Range ) , if the Function F ( D , q ) satisfies the following equation, then F ( D , q ) satisfies ε - differential privacy. where D is the input data set, the output is an entity object r , and…”
BackgroundDifferentially private stochastic gradient descent via compression and memorization
Phong, L. T., & Phuong, T. T. (2022) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2022.102819 · Cited by 19
Privacy-preserving federated learning compatible with robust aggregators
Alebouyeh, Z., & Bidgoly, A. J. (2025) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2025.110078 · Cited by 22
Data Privacy for a $\rho$ -Recoverable Function
Nageswaran, A., & Narayan, P. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2894147 · Cited by 17
UAV-Assisted Privacy-Preserving Online Computation Offloading for Internet of Things
Wei, D., Xi, N., Ma, J., & He, L. (2021) · Remote Sensing · doi:10.3390/rs13234853 · Cited by 17
“Finally, the accumulated policy gradient ψ is computed based on a chain rule in Reference [33] as shown below (Line 16): where ∇ ζ Π ( s i , a i ) is the gradient of the online policy for vector ( s n , a n ) .”
BackgroundInfluentialPrivacy Preserving Time-Series Forecasting of User Health Data Streams
Imtiaz, S., Horchidan, S.-F., Abbas, Z., Arsalan, M., Chaudhry, H. N., & Vlassov, V. (2020) · 2020 IEEE International Conference on Big Data (Big Data) · doi:10.1109/bigdata50022.2020.9378186 · Cited by 15
“When an algorithm requires multiple additive noise mechanisms, the privacy guarantee follows from the basic composition theorem [16], [17] or from advanced composition theorems and their extensions [18]–[20].”
MethodYou, F., Yuan, X., Ni, W., & Jamalipour, A. (2025) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2024.3499342 · Cited by 15
“With reference to the composition theorem [34], when the iteration amounts to T / B iterations, the proposed algorithm achieves ( (cid:9), δ + J exp( − (2 k − 8 .”
Federated Learning with Secure Aggregation for Privacy-Preserving Deep Learning in IoT Environments
Kasula, V. K., Yenugula, M., Konda, B., Yadulla, A. R., Tumma, C., & Rakki, S. B. (2025) · IEEE Conference on Computer Applications (ICCA) · doi:10.1109/icca65395.2025.11011120 · Cited by 30
Offset-Symmetric Gaussians for Differential Privacy
Sadeghi, P., & Korki, M. (2022) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2022.3185770 · Cited by 15
“For the Laplace mechanism, we start the composition formula in [20] with 1 = 1/b = √2/2500 and δ1 = 0 for p = 1.”
BackgroundMethodLiu, Y., Zhao, S., Xiong, L., Liu, Y., & Chen, H. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i10.26400 · Cited by 26
Personalized Graph Federated Learning With Differential Privacy
Gauthier, F., Gogineni, V. C., Werner, S., Huang, Y.-F., & Kuh, A. (2023) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2023.3325963 · Cited by 22
“In other words, DP limits the ability of attackers to infer information from individual data samples by adding controlled noise to the data before sharing it with the server [30], [31], [32], [33], [34].”
BackgroundComposition properties of inferential privacy for time-series data
Song, S., & Chaudhuri, K. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262823 · Cited by 17
“Optimal composition guarantees for both pure and approximate differential privacy are established by [6].”
BackgroundPrivacy Budgeting for Growing Machine Learning Datasets
Li, W., Xiang, L., Zhou, Z., & Peng, F. (2021) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom42981.2021.9488920 · Cited by 15
“Different from the offline case, the privacy parameters (cid:15) j s are assumed to be adaptively chosen rather than fixed in advance, so that Thm. 3.5 in [18] does not apply anymore.”
BackgroundInfluentialAccuracy Degrading: Toward Participation-Fair Federated Learning
You, X., Liu, X., Lin, X., Cai, J., & Chen, S. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3238038 · Cited by 19
“In that case, one important thing is that we should figure out how each part of FedACC consumes the DP budget [28], [35].”
BackgroundDifferentially Private Online Active Learning with Applications to Anomaly Detection
Ghassemi, M., Sarwate, A. D., & Wright, R. N. (2016) · ACM Workshop on Artificial Intelligence and Security (AISec) · doi:10.1145/2996758.2996766 · Cited by 15
“Standard composition theorems [31, 33] allows us to find the overall differential privacy guarantee under each scenario under either Bernoulli or exponential sampling.”
BackgroundPreliminary of Differential Privacy
Zhu, T., Li, G., Zhou, W., & Yu, P. S. (2017) · Advances in information security · doi:10.1007/978-3-319-62004-6_2 · Cited by 15
Differentially Private Inference for Binomial Data
Awan, J., & Slavković, A. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.725 · Cited by 30
Differentially Private Assouad, Fano, and Le CamPreprint
Acharya, J., Sun, Z., & Zhang, H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.06830 · Cited by 21
Differentially Private Real-Time Release of Sequential Data
Zhang, X., Khalili, M. M., & Liu, M. (2022) · ACM Transactions on Privacy and Security · doi:10.1145/3544837 · Cited by 25
“The data of each individual here spans over T time steps, the total privacy loss is the accumulation of privacy loss from T time steps: If x t is released under ( ϵ t , δ t ) -differential privacy at time t , then the total privacy loss can be calculated using the advanced composition theorem below: Theorem A.6 (Advan…”
BackgroundMethodResultInfluentialGenerating Synthetic Graphs for Large Sensitive and Correlated Social Networks
Ju, X., Zhang, X., & Cheung, W. K. (2019) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew.2019.00007 · Cited by 18
Using Noisy Binary Search for Differentially Private Anomaly Detection
Bittner, D. M., Sarwate, A., & Wright, R. N. (2018) · International Conference on Cyber Security Cryptography and Machine Learning · doi:10.1007/978-3-319-94147-9_3 · Cited by 13
“For approximate ( , δ)-differential privacy there are stronger composition results in which the total privacy risk for sequential composition grows sublinearly with the number of terms [6,19,26], including the so-called “moments accountant” [1].”
BackgroundDifferential Privacy for Tensor-Valued Queries
Yang, J., Xiang, L., Chen, R., Li, W., & Li, B. (2021) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2021.3089884 · Cited by 14
“For any pair of adjacent datasets X and X , the Rényi divergence between query results on the two datasets is The TVG mechanism could also take advantage of advanced composition approaches such as the moments accountant technique [10] and optimal composition [11].”
MethodRecommendations in Smart Devices Using Federated Tensor Learning
Yang, J., Fu, C., Liu, X.-Y., & Walid, A. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3116505 · Cited by 15
Assessing differentially private deep learning with Membership InferencePreprint
Bernau, D., Grassal, P.-W., Robl, J., & Kerschbaum, F. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.11328 · Cited by 33
“We chose this accumulation method over other advanced composition schemes (e.g., Advanced Composition or Moments Accountant [18, 1]) since it provides tighter bounds for heterogeneous mechanism invocations.”
MethodOneto, L., Donini, M., Pontil, M., & Shawe-Taylor, J. S. (2020) · Neurocomputing · doi:10.1016/j.neucom.2019.12.137 · Cited by 19
Privacy Amplification for Federated Learning via User Sampling and Wireless Aggregation
Seif, M., Chang, W.-T., & Tandon, R. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9518031 · Cited by 14
Protecting Your Shopping Preference With Differential Privacy
Lin, J., Niu, J., Liu, X., & Guizani, M. (2020) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2020.2972001 · Cited by 16
“Existing differential privacy approaches have not considered setting boundaries on data with added noise [18], [19].”
BackgroundDifferentially Private Learning Does Not Bound Membership Inference.Preprint
Humphries, T., Rafuse, M., Tulloch, L., Oya, S., Goldberg, I., & Kerschbaum, F. (2020) · arXiv (Cornell University) · Cited by 20
Distributed empirical risk minimization with differential privacy
Liu, C., Johansson, K. H., & Shi, Y. (2024) · Automatica · doi:10.1016/j.automatica.2024.111514 · Cited by 23
“We start by introducing some useful properties of DP [8,9, 15].”
MethodNetwork Shuffling: Privacy Amplification via Random Walks
Liew, S. P., Takahashi, T., Takagi, S., Kato, F., Cao, Y., & Yoshikawa, M. (2022) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3514221.3526162 · Cited by 23
“Finally, the heterogeneous composition theorem [32] is used to compose all εi ’s to obtain the overall ε.”
MethodDiscrimination of Quantum States Under Locality Constraints in the Many-Copy Setting
Cheng, H., Winter, A., & Yu, N. (2023) · Communications in Mathematical Physics · doi:10.1007/s00220-023-04836-0 · Cited by 19
“It has substantial applications in numerous fields, such as information sciences [2, 3, 4, 5, 6, 7, 8], computational learning theory [9, 10, 11, 12], property and distribution testing [13, 14, 15, 16], and differential privacy [17, 18, 19, 20, 21].”
BackgroundA Novel Privacy-Preserving Incentive Mechanism for Multi-Access Edge Computing
You, F., Yuan, X., Ni, W., & Jamalipour, A. (2024) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2024.3391303 · Cited by 11
“As a result, we have According to Composition Theorem [36], the proposed mechanism M = ( M 1 , . . . (cid:2) , M Λ ) satisfies (cid:4) -DP, and (cid:4) = Λ λ =1 (cid:4) λ .”
Total Variation Meets Differential Privacy
Ghazi, E., & Issa, I. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3384083 · Cited by 16
“Note that the refined composition bound involves lines with slopes of the form − e ± j ε for j ∈ { 0 , 1 , . . . , k } , while the bound introduced in [7] only involves values of j such that 0 ≤ j ≤ k and j and k have the same parity.”
BackgroundMethodResultInfluentialThe Role of Campus Data in Representing Depression Among College Students: Exploratory Research
Mei, G., Xu, W., Li, L., Zhao, Z., Li, H., Liu, W., & Jiao, Y. (2020) · JMIR Mental Health · doi:10.2196/12503 · Cited by 14
“For example, provide researchers with differential privacy [59] processed data.”
BackgroundDistributed differentially-private learning with communication efficiency
Phuong, T. T., & Phong, L. T. (2022) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2022.102555 · Cited by 13
LLDP: A Layer-wise Local Differential Privacy in Federated Learning
Chen, Q., Wang, H., Wang, Z., Chen, J., Yan, H., & Lin, X. (2022) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom56396.2022.00091 · Cited by 12
“We first recall the Sequential Composition as follows: Lemma 1 (Sequential Composition [25], [26]): Given m mechanisms M ( · ) s satisfying ( ε, δ ) -LDP, the m -fold adaptive composition satisfies ( mε, mδ ) -LDP.”
MethodPrivyNAS: Privacy-Aware Neural Architecture Search for Split Computing in Edge–Cloud Systems
Odema, M., & Faruque, M. A. A. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3311761 · Cited by 11
“Added to its quantifiability, DP is characterized by the two essential properties of postprocessing immunity and composition [17], [22].”
BackgroundMethodUnifying Privacy Measures via Maximal (α, β)-Leakage (MαbeL)
Gilani, A., Kurri, G. R., Kosut, O., & Sankar, L. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3384922 · Cited by 18
“An operational interpretation of DP in the framework of hypothesis testing is given by Kairouz et al. [21], where they show that it determines the trade-off between probabilities of false alarm and missed detection.”
MethodWang, Y. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383541 · Cited by 13
“It is worth noting that the considered notion of (cid:15) -DP is more stringent than other relaxed (approximate) DP notions such as ( (cid:15), δ ) -DP [39], zero-concentrated DP [40], or R´enyi DP [41].”
BackgroundDifferentially Private Heavy Hitter Detection using Federated Analytics
Chadha, K. N., Chen, J., Duchi, J. C., Feldman, V., Hashemi, H., Javidbakht, O., McMillan, A., & Talwar, K. (2024) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml59370.2024.00032 · Cited by 16
Enhancing social network privacy with accumulated non-zero prior knowledge
Wang, Y., Yang, L., Chen, X., Zhang, X., & He, Z. (2018) · Information Sciences · doi:10.1016/j.ins.2018.02.031 · Cited by 10
Matrix Gaussian Mechanisms for Differentially-Private Learning
Yang, J., Xiang, L., Yu, J., Wang, X., Guo, B., Li, Z., & Li, B. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3093316 · Cited by 12
“For MVG, MGM, and MM in Type I experiment, we adopt the composition theorem (Theorem 3.4 from [40]) to ensure the overall ð (cid:1); d Þ -differential privacy.”
MethodInfluentialNoiseless Privacy: Definition, Guarantees, and Applications
Farokhi, F. (2021) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2021.3104021 · Cited by 15
“Composition of differentially-private mechanisms [2], [64], [65] is an important result showing that the privacy budgets”
BackgroundWei, D., Xi, N., Ma, J., & Li, J. (2021) · International Workshop on Quality of Service · doi:10.1109/iwqos52092.2021.9521307 · Cited by 10
Security and Privacy for Big Data
Li, S., & Gao, J. Z. (2016) · Springer eBooks · doi:10.1007/978-3-319-27763-9_8 · Cited by 11
The Trade-Off Between Privacy and Fidelity via Ehrhart Theory
Padakandla, A., Kumar, P. R., & Szpankowski, W. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2959976 · Cited by 9
“5], [6] and post-processing [5, Proposition 2.”
Geo-Graph-Indistinguishability: Location Privacy on Road Networks with Differential Privacy
Takagi, S., Cao, Y., Asano, Y., & Yoshikawa, M. (2023) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2022dap0011 · Cited by 19
Privacy Auditing in Differential Private Machine Learning: The Current Trends
Namatēvs, I., Sudars, K., Ņikuļins, A., & Ozols, K. (2025) · Applied Sciences · doi:10.3390/app15020647 · Cited by 21
Baligodugula, V. V., & Amsaad, F. (2025) · Electronics · doi:10.3390/electronics14061218 · Cited by 10
Private resource allocators and their applications
Angel, S., Kannan, S., & Ratliff, Z. B. (2020) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp40000.2020.00065 · Cited by 14
DPlanner: A Privacy Budgeting System for Utility
Li, W., Xiang, L., Guo, B., Li, Z., & Wang, X. (2022) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2022.3231786 · Cited by 9
“One should note Estimator evaluates D j ’s importance p to Q i ; that advanced composition [27] or optimal composition [28] do not fit our problem, as they are designed to compose privacy budgets known in prior.”
BackgroundFP-Fed: Privacy-Preserving Federated Detection of Browser Fingerprinting
Annamalai, M. S. M. S., Bilogrevic, I., & Cristofaro, E. D. (2024) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2024.24360 · Cited by 21
Reliable Customized Privacy-Preserving in Fog Computing
Wang, X., Gu, B., Qu, Y., Ren, Y., Xiang, Y., & Gao, L. (2020) · International Conference on Communications · doi:10.1109/icc40277.2020.9148989 · Cited by 9
“Peter et al [22] proposed a solution which set an upper bound on the overall privacy level and build a sequence of privatization mechanisms that implement this limitation.”
BackgroundComputing Tight Differential Privacy Guarantees Using FFTPreprint
Koskela, A., Jälkö, J., & Honkela, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.03049 · Cited by 13
Differentially-Private Deep Learning With Directional Noise
Xiang, L., Li, W., Yang, J., Wang, X., & Li, B. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3130060 · Cited by 10
“In contrast, we adopt the optimal composition theorem [13] and further amplify the privacy guarantee with”
BackgroundMethodBreast Cancer Prediction Based on Differential Privacy and Logistic Regression Optimization Model
Chen, H., Wang, N., Zhou, Y. M., Mei, K., Tang, M., & Cai, G. (2023) · Applied Sciences · doi:10.3390/app131910755 · Cited by 8
Online Context-Aware Streaming Data Release With Sequence Information Privacy
Jiang, B., Li, M., & Tandon, R. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3378008 · Cited by 8
“LDP is also sequentially decomposable by applying independent mechanisms [22], and can be adapted in the online release setting.”
Background
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.