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
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Self-citationMironov, I. (2017) · 2017 IEEE 30th Computer Security Foundations Symposium (CSF) · doi:10.1109/csf.2017.11 · Cited by 1,255
“[7] for an optimal bound on composition of homogeneous mechanisms and Murtagh and Vadhan [8] for hardness results and an approximation scheme for composition of mechanisms with heterogeneous privacy guarantees.”
BackgroundMethodA Hybrid Approach to Privacy-Preserving Federated Learning
Truex, S., Baracaldo, N., Anwar, A., Steinke, T., Ludwig, H., Zhang, R., & Zhou, Y. (2019) · Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security · doi:10.1145/3338501.3357370 · Cited by 1,029
Yin, X., Zhu, Y., & Hu, J. (2022) · ACM Computing Surveys · doi:10.1145/3460427 · Cited by 638
“To limit the privacy leakage from the updates or the final model, a user-level differential privacy can be applied during the FL training process [6, 44, 83].”
MethodDifferential Privacy for Deep and Federated Learning: A Survey
Ouadrhiri, A. E., & Abdelhadi, A. (2022) · IEEE Access · doi:10.1109/access.2022.3151670 · Cited by 445
“[62] define a procedure that allows achieving the optimal bound of the privacy budget after k queries.”
BackgroundInfluentialDong, J., Roth, A., & Su, W. J. (2022) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/rssb.12454 · Cited by 374
Dong, J., Roth, A., & Su, W. J. (2019) · arXiv · doi:10.48550/arxiv.1905.02383 · Cited by 389
Extremal mechanisms for local differential privacy
KairouzPeter, OhSewoong, & ViswanathPramod (2016) · Journal of Machine Learning Research · doi:10.5555/2946645.2946662 · Cited by 92
Self-citationSubsampled Rényi Differential Privacy and Analytical Moments Accountant
Wang, Y.-X., Balle, B., & Kasiviswanathan, S. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.723 · Cited by 137
Subsampled Rényi Differential Privacy and Analytical Moments Accountant
Wang, Y.-X., Balle, B., & Kasiviswanathan, S. (2018) · arXiv · doi:10.48550/arxiv.1808.00087 · Cited by 224
“We consider two baselines: the naïve composition that simply adds up ( (cid:15), δ ) and the strong composition is through the result of (Kairouz et al., 2015) with an optimal choice of per-round δ parameter computed for every k .”
BackgroundInfluentialDifferential Privacy for Industrial Internet of Things: Opportunities, Applications, and Challenges
Jiang, B., Li, J., Yue, G., & Song, H. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3057419 · Cited by 201
“[54] discussed the optimal multidimensional setting mechanism in differential privacy, which improved the optimal mechanism while protecting privacy.”
BackgroundAn Operational Approach to Information Leakage
Issa, I., Wagner, A. B., & Kamath, S. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2962804 · Cited by 198
“This also raises interest in the behavior of mechanisms under composition [56].”
BackgroundDP-CGAN: Differentially Private Synthetic Data and Label Generation
Torkzadehmahani, R., Kairouz, P., & Paten, B. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw.2019.00018 · Cited by 193
“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-citationDifferential Privacy as a Mutual Information Constraint
Cuff, P., & Yu, L. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978308 · Cited by 184
“Finally, (ǫ, δ)-closeness is shown in [17] to be precisely a piecewise linear constraint on the error region in a binary hypothesis test.”
BackgroundDifferential Privacy and Machine Learning: a Survey and Review
Ji, Z., Lipton, Z. C., & Elkan, C. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.7584 · Cited by 181
Turner, J. A. (2013) · Frontiers in Neuroscience · doi:10.3389/fnins.2013.00137 · Cited by 178
Deep Learning with Gaussian Differential Privacy
Bu, Z., Dong, J., Long, Q., & Weijie, S. (2020) · Harvard Data Science Review · doi:10.1162/99608f92.cfc5dd25 · Cited by 164
The Optimal Noise-Adding Mechanism in Differential Privacy
Geng, Q., & Viswanath, P. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2504967 · Cited by 169
Self-citationHow to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z., Denison, C., McMahan, H. B., Vassilvitskii, S., Chien, S., & Thakurta, A. G. (2023) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.14649 · Cited by 166
“The ε′ in the latter bound can be improved at the expense of some degradation in δ′, using advanced composition bounds (Dwork & Roth, 2014; Kairouz et al., 2015).”
MethodRodríguez-Barroso, N., Stipcich, G., Jiménez-López, D., Ruiz-Millán, J. A., Martínez-Cámara, E., González-Seco, G., Luzón, M. V., Veganzones, M. A., & Herrera, F. (2020) · Information Fusion · doi:10.1016/j.inffus.2020.07.009 · Cited by 148
Efficient Privacy-Preserving Machine Learning for Blockchain Network
Kim, H., Kim, S.-H., Hwang, J. Y., & Seo, C. (2019) · IEEE Access · doi:10.1109/access.2019.2940052 · Cited by 144
“A simple composition shows that the composition of k queries, each of which guarantees ( , δ)–DP has at least (k , kδ)– differentially private [14], [29]–[32].”
BackgroundAdversary Instantiation: Lower Bounds for Differentially Private Machine Learning
Nasr, M., Songi, S., Thakurta, A., Papernot, N., & Carlin, N. (2021) · 2021 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40001.2021.00069 · Cited by 135
“al [29] showed if a mechanism M is ( , δ)-differentially private then the adversary’s false positive (FP) and false negative (FN) rate is bounded by:”
BackgroundcpSGD: Communication-efficient and differentially-private distributed SGD
Agarwal, N., Suresh, A. T., Yu, F., Kumar, S., & McMahan, H. B. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.10559 · Cited by 180
“5 [19]) or moments accounting [2] can be used to relate the privacy guarantee of SGD to that of gradient mean estimate at each instance t.”
BackgroundKim, M., Gunlu, O., & Schaefer, R. F. (2021) · ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp39728.2021.9413764 · Cited by 128
Age-Dependent Differential Privacy
Zhang, M., Wei, E., Berry, R., & Huang, J. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3340147 · Cited by 143
“Similarly, the accuracy loss incurred by the DP benchmark grows unbounded as the privacy risk approaches zero, while a finite accuracy loss is always achievable under our proposed scheme that combines both noise injection and aging.”
BackgroundMethodPacGAN: The Power of Two Samples in Generative Adversarial Networks
Lin, Z., Khetan, A., Fanti, G., & Oh, S. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.2983071 · Cited by 122
“This was used to prove strong composition theorems in differential privacy [34] and to identify the optimal differentially-private mechanisms under local privacy [32] and multi-party communications [33].”
BackgroundMethodResultInfluentialSelf-citationManipulation Attacks in Local Differential Privacy
Cheu, A., Smith, A., & Ullman, J. (2021) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp40001.2021.00001 · Cited by 161
Privacy-Preserving Artificial Intelligence Techniques in Biomedicine
Torkzadehmahani, R., Nasirigerdeh, R., Blumenthal, D. B., Kacprowski, T., List, M., Matschinske, J., Spaeth, J., Wenke, N. K., & Baumbach, J. (2022) · Methods of Information in Medicine · doi:10.1055/s-0041-1740630 · Cited by 111
“Two important properties of differential privacy are composability [87] and resilience to post-processing.”
BackgroundLF-GDPR: A Framework for Estimating Graph Metrics With Local Differential Privacy
Ye, Q., Hu, H., Au, M. H., Meng, X., & Xiao, X. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3047124 · Cited by 146
“Graph-specific tighter bounds for the composition of DP [60] and the correlation of graph data will also be studied.”
BackgroundFedDM: Iterative Distribution Matching for Communication-Efficient Federated Learning
Xiong, Y., Wang, R., Cheng, M., Yu, F., & Hsieh, C. (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.01566 · Cited by 176
“There are many scenarios in which DP guarantee is necessary [1, 2, 12, 13, 21,34,38].”
BackgroundDesfontaines, D., & Pejó, B. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2020-0028 · Cited by 211
Differentially Private SQL with Bounded User Contribution
Wilson, R. J., Zhang, C. Y., Lam, W. H. K., Desfontaines, D., Simmons-Marengo, D., & Gipson, B. R. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2020-0025 · Cited by 201
Privacy in Deep Learning: A Survey
Mireshghallah, F., Taram, M., Vepakomma, P., Singh, A., Raskar, R., & Esmaeilzadeh, H. (2020) · arXiv · doi:10.48550/arxiv.2004.12254 · Cited by 106
“It has been shown that tighter privacy bound for composition can be reached, so that the privacy budget decreases sub-linearly [56, 57].”
BackgroundAnonymization: The imperfect science of using data while preserving privacy
Gadotti, A., Rocher, L., Houssiau, F., Creţu, A.-M., & de Montjoye, Y.-A. (2024) · Science Advances · doi:10.1126/sciadv.adn7053 · Cited by 182
“These guarantees can be translated into a worst-case measure of robustness against attacks, for example, in terms of Bayesian inference ( 194 ) or hypothesis testing ( 195 ).”
BackgroundGenerative Models for Effective ML on Private, Decentralized Datasets
Augenstein, S., McMahan, H. B., Ramage, D., Ramaswamy, S., Kairouz, P., Chen, M., Mathews, R., & Arcas, B. A. Y. (2019) · arXiv · doi:10.48550/arxiv.1911.06679 · Cited by 103
“using the strong composition theorem for DP (Mironov, 2017; Kairouz et al., 2017).”
MethodSelf-citationTailoring Gradient Methods for Differentially Private Distributed Optimization
Wang, Y., & Nedić, A. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3272968 · Cited by 138
“Under relaxed (approximate) ǫ -DP frameworks, such as ( ǫ, δ ) -DP [46], zero-concentrated DP [47], or R´enyi DP [48], advanced composition theories in [46], [47], [48] can be exploited to characterize the cumulative privacy budget.”
BackgroundOptimal Noise Adding Mechanisms for Approximate Differential Privacy
Geng, Q., & Viswanath, P. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2504972 · Cited by 91
Self-citationQuantum Differential Privacy: An Information Theory Perspective
Hirche, C., Rouzé, C., & França, D. S. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3272904 · Cited by 164
Reconstructing Training Data with Informed Adversaries
Balle, B., Cherubin, G., & Hayes, J. (2022) · 2022 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp46214.2022.9833677 · Cited by 83
Secure and Utility-Aware Data Collection with Condensed Local Differential Privacy
Gursoy, M. E., Tamersoy, A., Truex, S., Wei, W., & Liu, L. (2019) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2019.2949041 · Cited by 87
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
Feldman, V., McMillan, A., & Talwar, K. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00096 · Cited by 204
The 2020 Census Disclosure Avoidance System TopDown Algorithm
Abowd, J. M., Ashmead, R., Cumings-Menon, R., Garfinkel, S., Heineck, M., Heiss, C., Johns, R., Kifer, D., Leclerc, P., Machanavajjhala, A., et al. (2022) · Harvard Data Science Review · doi:10.1162/99608f92.529e3cb9 · Cited by 200
Gradient Leakage Attack Resilient Deep Learning
Wei, W., & Liu, L. (2021) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2021.3139777 · Cited by 94
“There are four representative privacy accounting methods: moments accountant (MA) [24], zCDP [27], advanced composition (AdvC) [43] and optimal composition (OptC) [44].”
Revisiting Membership Inference Under Realistic Assumptions
Jayaraman, B., Wang, L., Knipmeyer, K., Gu, Q., & Evans, D. (2021) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2021-0031 · Cited by 185
The Complexity of Computing the Optimal Composition of Differential Privacy
Murtagh, J., & Vadhan, S. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49096-9_7 · Cited by 75
Efficient Deep Learning on Multi-Source Private Data
Hynes, N., Cheng, R., & Song, D. X. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.06689 · Cited by 73
“This result is known as strong composition [21].”
BackgroundBounded and Unbiased Composite Differential Privacy
Zhang, K., Zhang, Y., Sun, R., Tsai, P., Hassan, M. U., Yuan, X., Xue, M., & Chen, J. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00108 · Cited by 100
“We also note that our proposed composite DP mechanism differs from the composition theory [56], [57], [58], [59] in the realm of DP research.”
ResultDiscrete Gaussian for Differential Privacy
Canonne, C. L., Kamath, G., & Steinke, T. (2022) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.784 · Cited by 85
Information-theoretic analysis of stability and bias of learning algorithms
Raginsky, M., Rakhlin, A., Tsao, M., Wu, Y., & Xu, A. (2016) · 2016 IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2016.7606789 · Cited by 70
“Moreover, differential privacy behaves nicely under composition of algorithms [11], [12], which makes it particularly amenable to information-theoretic analysis.”
BackgroundDifferential Privacy for IoT-Enabled Critical Infrastructure: A Comprehensive Survey
Husnoo, M. A., Anwar, A., Chakrabortty, R. K., Doss, R., & Ryan, M. J. (2021) · IEEE Access · doi:10.1109/access.2021.3124309 · Cited by 92
A Hybrid Approach to Privacy-Preserving Federated Learning
Truex, S., Baracaldo, N., Anwar, A., Steinke, T., Ludwig, H., Zhang, R., & Zhou, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.03224 · Cited by 66
“When an algorithm requires multiple additive noise mechanisms, the evaluation of the privacy guarantee follows from the basic composition theorem [14, 15] or from advanced composition theorems and their extensions [7, 17, 18, 23].”
MethodDesign of Privacy-Preserving Dynamic Controllers
Kawano, Y., & Cao, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2994030 · Cited by 77
“However, there is still a considerable lack of in-depth understanding of the possible fundamental interplay between differential privacy and other critical properties of dynamical systems [29].”
BackgroundAdaCliP: Adaptive Clipping for Private SGD
Pichapati, V., Suresh, A. T., Yu, F. X., Reddi, S. J., & Kumar, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.07643 · Cited by 60
“For the Gaussian mechanism, [14] introduced moments accountant, which provides tighter privacy bounds compared to other composition theorems [33, 34, 35, 34, 36].”
BackgroundWang, Q., Chen, D., Zhang, N., Ding, Z., & Qin, Z. (2017) · IEEE Access · doi:10.1109/access.2017.2748956 · Cited by 61
“It adds the artificial noise to the data before output it so that the adversary cannot figure out the actual data through the statistical analysis [7], [8].”
BackgroundEW-Tune: A Framework for Privately Fine-Tuning Large Language Models with Differential Privacy
Behnia, R., Ebrahimi, M. R., Pacheco, J., & Padmanabhan, B. (2022) · 2022 IEEE International Conference on Data Mining Workshops (ICDMW) · doi:10.1109/icdmw58026.2022.00078 · Cited by 60
“The GDP framework offers a nice characterization of differential privacy using hypothesis testing interpretation [24].”
Blockchain-Enabled Reengineering of Cloud Datacenters
Gai, K., Choo, K.-K. R., & Zhu, L. (2018) · IEEE Cloud Computing · doi:10.1109/mcc.2018.064181116 · Cited by 60
Sarwate, A. D., Plis, S. M., Turner, J. A., Arbabshirani, M. R., & Calhoun, V. D. (2014) · Frontiers in Neuroinformatics · doi:10.3389/fninf.2014.00035 · Cited by 60
Quantization Enabled Privacy Protection in Decentralized Stochastic Optimization
Wang, Y., & Başar, T. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3198030 · Cited by 79
“The cumulative privacy loss (budget) increases roughly at a rate of √ T for T iterations, according to the composition theorem for differential privacy [58].”
BackgroundOptimal Differentially Private Mechanisms for Randomised Response
Holohan, N., Leith, D. J., & Mason, O. (2017) · Maynooth University ePrints and eTheses Archive (Maynooth University) · Cited by 59
Privacy-Preserving Federated Learning Model for Healthcare Data
Islam, T. U., Ghasemi, R., & Mohammed, N. (2022) · 2022 IEEE 12th Annual Computing and Communication Workshop and Conference (CCWC) · doi:10.1109/ccwc54503.2022.9720752 · Cited by 56
“Also, according to the composition theorem [16] of the DP mechanism as detailed in the Background section, If F 1 ( x ) satisfies " 1 -differential privacy and F 2 ( x ) satisfies " 2 -differential privacy, then the mechanism G ( x ) = ( F 1 ( x ) ; F 2 ( x )) which releases both results satisfies " 1…”
BackgroundDifferential Privacy for Data and Model Publishing of Medical Data
Sun, Z., Wang, Y., Shu, M., Liu, R., & Zhao, H. (2019) · IEEE Access · doi:10.1109/access.2019.2947295 · Cited by 56
Security and Privacy Issues in Deep Learning
Bae, H., Jang, J., Jung, D., Jang, H., Ha, H., Lee, H., & Yoon, S. (2018) · arXiv · doi:10.48550/arxiv.1807.11655 · Cited by 56
“Composition theorem [23, 52], advanced composition theorem [53, 24, 54] and moment accountant [21] have been proposed.”
BackgroundAdvanced Probabilistic Couplings for Differential Privacy
Barthe, G., Fong, N., Gaboardi, M., Grégoire, B., Hsu, J., & Strub, P.-Y. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978391 · Cited by 79
PADL: Privacy-Aware and Asynchronous Deep Learning for IoT Applications
Liu, X., Li, H., Xu, G., Liu, S., Liu, Z., & Lu, R. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.2981379 · Cited by 60
“The sequential composition and parallel composition of differential privacy are very useful in the design of multistep mechanisms [36], as defined in Theorems 1 and 2.”
BackgroundPrivacy With Estimation Guarantees
Wang, H., Vo, L., Calmon, F. P., Médard, M., Duffy, K. R., & Varia, M. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2934414 · Cited by 53
“Fundamental bounds on composition of differentially private mechanisms were given by Kairouz et al. [30].”
BackgroundRandomized requantization with local differential privacy
Xiong, S., Sarwate, A. D., & Mandayam, N. B. (2016) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2016.7472065 · Cited by 61
“Small ε means greater indistinguishability and hence less privacy risk; it characterizes the false-alarm/missed-detection tradeoff for the hypothesis test in guessing x from x̂ [11, 12].”
BackgroundKaraoke: distributed private messaging immune to passive traffic analysis
Lazar, D., Gilad, Y., & Zeldovich, N. (2018) · Operating Systems Design and Implementation · doi:10.5555/3291168.3291221 · Cited by 115
Probabilistic matrix factorization with personalized differential privacy
Zhang, S., Liu, L., Chen, Z., & Zhong, H. (2019) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.07.035 · Cited by 58
Shuffled Model of Federated Learning: Privacy, Accuracy and Communication Trade-Offs
Girgis, A. M., Data, D., Diggavi, S. N., Kairouz, P., & Suresh, A. T. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3056102 · Cited by 102
Self-citationA Fine-Grained Differentially Private Federated Learning Against Leakage From Gradients
Zhu, L., Liu, X., Li, Y., Yang, X. S., Xia, S., & Lu, R. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3131258 · Cited by 61
“:3) f , is shown as follows: The proposed scheme can be regarded as a multistep mechanism, where the sequential composition theorem and the parallel composition theorem of DP are widely used [15].”
BackgroundMethodA rate-disortion perspective on local differential privacy
Sarwate, A. D., & Sankar, L. (2014) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2014.7028550 · Cited by 60
Privacy Amplification for Federated Learning via User Sampling and Wireless Aggregation
Seif, M., Chang, W.-T., & Tandon, R. (2021) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3118408 · Cited by 60
“We can expect the same behavior to hold true for the timeinvariant case since the result in [34] is more general than the result in [35].”
MethodResultPrivacy Loss Classes: The Central Limit Theorem in Differential Privacy
Sommer, D., Meiser, S., & Mohammadi, E. (2019) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2019-0029 · Cited by 104
A Fair Mechanism for Private Data Publication in Online Social Networks
Zheng, X., Luo, G., & Cai, Z. (2018) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2018.2801798 · Cited by 49
“These solutions, such as differential privacy [10] and k-anonymity [11], obfuscate contents or statistical results before publication.”
BackgroundDifferentially-Private Deep Learning from an optimization Perspective
Xiang, L., Yang, J., & Li, B. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737494 · Cited by 56
“We adopt the advanced composition theorem for differential privacy [11] and privacy amplification by a sampling approach [13] in our mechanism.”
MethodPrivacy and Statistical Risk: Formalisms and Minimax BoundsPreprint
Barber, R. F., & Duchi, J. C. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.4451 · Cited by 101
Differentially Private Distributed Algorithms for Aggregative Games With Guaranteed Convergence
Wang, Y., & Nedić, A. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3351068 · Cited by 49
“Under relaxed (approximate) ǫ-differential privacy frameworks, such as (ǫ, δ)-differential privacy [33], zeroconcentrated differential privacy [34], or Rényi differential privacy [35], advanced composition theories in [33], [34], [35] can be exploited to characterize the cumulative privacy budget.”
BackgroundTalwar, K. (2022) · Leibniz international proceedings in informatics · doi:10.4230/lipics.forc.2022.7 · Cited by 104
Model Explanations with Differential Privacy
Patel, N., Shokri, R., & Zick, Y. (2022) · ACM Conference on Fairness, Accountability, and Transparency (FAccT) · doi:10.1145/3531146.3533235 · Cited by 72
“Following the DP composition theorem [19], k independent ( , δ)-private queries result in an (̃, kδ + δ̃)-differentially private output for any δ̃ ∈ (0, 1) and ̃ ∈ O ( × (ke + √ k log ( e + √ k/δ̃ )) .”
Differentially Private MIMO Filtering for Event Streams
Ny, J. L., & Mohammady, M. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2713643 · Cited by 49
“One can also show that it is impossible to design a statistical test with a small error to decide if d or d′ was used by a differentially private mechanism to produce its output [32], [33].”
Locally differentially private item-based collaborative filtering
Guo, T., Luo, J., Dong, K., & Yang, M. (2019) · Information Sciences · doi:10.1016/j.ins.2019.06.021 · Cited by 41
Secrecy by Design With Applications to Privacy and Compression
Shkel, Y. Y., Blum, R. S., & Poor, H. V. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3041224 · Cited by 49
DP-Sniper: Black-Box Discovery of Differential Privacy Violations using Classifiers
Bichsel, B., Steffen, S., Bogunovic, I., & Vechev, M. (2021) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp40001.2021.00081 · Cited by 73
“4], [46, Thm. 2.1].”
InfluentialPrivacy-Aware Distributed Bayesian Detection
Li, Z., & Oechtering, T. J. (2015) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2015.2429123 · Cited by 38
“In [25], the degradation of the differential privacy level under adaptive interactions was characterized.”
BackgroundDifferentially Private Testing of Identity and Closeness of Discrete DistributionsPreprint
Acharya, J., Sun, Z., & Zhang, H. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.05128 · Cited by 75
“We use differential privacy [30], a notion which rose from database and cryptography literature, and has emerged as one of the most popular privacy measures (See [30, 29, 62, 33, 15, 45, 44, 41], references therein, and the recent book [32]).”
MethodPrivacy-Aware Multiagent Deep Reinforcement Learning for Task Offloading in VANET
Wei, D., Zhang, J., Shojafar, M., Kumari, S., Xi, N., & Ma, J. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3202196 · Cited by 46
“68 √ θµ) 2 / 2 )- differential privacy, referring to the composition theorem [38].”
BackgroundOptimization of privacy-utility trade-offs under informational self-determination
Asikis, T., & Pournaras, E. (2018) · Future Generation Computer Systems · doi:10.1016/j.future.2018.07.018 · Cited by 48
Confidentiality and Differential Privacy in the Dissemination of Frequency Tables
Rinott, Y., O’Keefe, C. M., Shlomo, N., & Skinner, C. (2018) · Statistical Science · doi:10.1214/17-sts641 · Cited by 47
Privacy 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 Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3341301.3359639 · Cited by 53
“basic composition [17], strong composition [21], and variations thereof [28]) analyze Alg.”
BackgroundThree Variants of Differential Privacy: Lossless Conversion and Applications
Asoodeh, S., Liao, J., Calmon, F. P., Kosut, O., & Sankar, L. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3054692 · Cited by 70
“This can be done, for example, by invoking advanced composition theorems for DP, such as [13], [14].”
BackgroundMethodInfluentialPrivacy-Preserving Probabilistic Voltage Forecasting in Local Energy Communities
Toubeau, J., Teng, F., Morstyn, T., Krannichfeldt, L. V., & Wang, Y. (2022) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2022.3187557 · Cited by 45
“A solution is offered by advanced composition theorems [45], which give an upper bound of the accumulated privacy loss (by assuming that the worst-case scenario wherein the same amount of leakage occurs at each query to the data).”
BackgroundNumerical Composition of Differential Privacy
Gopi, S., Lee, Y. T., & Wutschitz, L. (2024) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.870 · Cited by 79
Privacy-Preserving Selective Aggregation of Online User Behavior Data
Qian, J., Qiu, F., Wu, F., Ruan, N., Chen, G., & Tang, S. (2016) · IEEE Transactions on Computers · doi:10.1109/tc.2016.2595562 · Cited by 33
Geo-Graph-Indistinguishability: Protecting Location Privacy for LBS over Road Networks
Takagi, S., Cao, Y., Asano, Y., & Yoshikawa, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-22479-0_8 · Cited by 33
A Blockchain-Based Approach for Saving and Tracking Differential-Privacy Cost
Zhao, Y., Zhao, J., Kang, J., Zhang, Z., Niyato, D. T., Shi, S., & Lam, K. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3058209 · Cited by 39
“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.”
BackgroundDifferential privacy and generalization: Sharper bounds with applications
Oneto, L., Ridella, S., & Anguita, D. (2017) · Pattern Recognition Letters · doi:10.1016/j.patrec.2017.02.006 · Cited by 40
An estimation-theoretic view of privacy
Wang, H., & Calmon, F. P. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262832 · Cited by 30
“Fundamental bounds on composition of differentially private mechanisms were given by Kairouz et al. [21].”
BackgroundIndividual Privacy Accounting via a Renyi FilterPreprint
Feldman, V., & Zrnic, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.11193 · Cited by 46
“[14, 22, 9, 26, 25, 3, 28, 5, 29]).”
Secure multi-party differential privacy
Kairouz, P., Oh, S., & Viswanath, P. (2015) · neural information processing systems · Cited by 57
Self-citationLinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale
Rogers, R., Subramaniam, S., Peng, S. X., Durfee, D., Lee, S., Kancha, S. K., Sahay, S., & Ahammad, P. (2021) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.782 · Cited by 92
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.