Composition Theorems for Interactive Differential Privacy
Open accessAbstract
An interactive mechanism is an algorithm that stores a data set and answers adaptively chosen queries to it. The mechanism is called differentially private, if any adversary cannot distinguish whether a specific individual is in the data set by interacting with the mechanism. We study composition properties of differential privacy in concurrent compositions. In this setting, an adversary interacts with k interactive mechanisms in parallel and can interleave its queries to the mechanisms arbitrarily. Previously, Vadhan and Wang [2021] proved an optimal concurrent composition theorem for pure-differential privacy. We significantly generalize and extend their results. Namely, we prove optimal parallel composition properties for several major notions of differential privacy in the literature, including approximate DP, Rényi DP, and zero-concentrated DP. Our results demonstrate that the adversary gains no advantage by interleaving its queries to independently running mechanisms. Hence, interactivity is a feature that differential privacy grants us for free. Concurrently and independently of our work, Vadhan and Zhang [2022] proved an optimal concurrent composition theorem for f-DP [Dong et al., 2022], which implies our result for the approximate DP case.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
Loss of differential privacy due to composition (multiple AI systems, each with its own differential privacy guarantee, operating jointly) is well-studied.
“Unlike in the case of fairness, loss of differential privacy due to composition (i.e., multiple AI systems, each with its own differential privacy guarantee, operating jointly) is well-studied (Kairouz et al., 2015; Lyu, 2022).”
From Multi-Agent Risks from Advanced AI (2025) · cites this paper as Lyu, 2022
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 12
- Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 , pages 74-86. ACM, 2018. doi: 10.1145/3188745. 3188946. URL https://doi.org/10.1145/3188745.3188946 . · DOI
- Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , 84, 2022.
- Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR , abs/1603.01887, 2016. URL http://arxiv.org/abs/1603.01887 . · arXiv
- Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a rényi filter. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual , pages 28080-28091, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/ec7f346604f518906d35ef0492709f78-Abstract.html .
- Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015 , volume 37 of JMLR Workshop and Conference Proceedings , pages 1376-1385. JMLR.org, 2015. URL http://proceedings.mlr.press/v37/kairouz15.html .
- Mathias Lécuyer. Practical privacy filters and odometers with rényi differential privacy and applications to differentially private deep learning. CoRR , abs/2103.01379, 2021. URL https://arxiv.org/abs/2103.01379 . · arXiv
- Jack Murtagh and Salil P. Vadhan. The complexity of computing the optimal composition of differential privacy. Theory Comput. , 14(1):1-35, 2018. doi: 10.4086/toc.2018.v014a008. URL https://doi.org/10.4086/toc.2018.v014a008 . · DOI
- Ryan M. Rogers, Salil P. Vadhan, Aaron Roth, and Jonathan R. Ullman. Privacy odometers and filters: Pay-as-you-go composition. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain , pages 1921-1929, 2016. URL https://proceedings.neurips.cc/paper/2016/hash/58c54802a9fb9526cd0923353a34a7ae-Abstract.html .
- Salil Vadhan and Wanrong Zhang. Concurrent composition theorems for differential privacy. 2022. doi: 10.48550/ARXIV.2207.08335. URL https://arxiv.org/abs/2207.08335 . · DOI
- Salil P. Vadhan and Tianhao Wang. Concurrent composition of differential privacy. In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part II , volume 13043 of Lecture Notes in Computer Science , pages 582-604. Springer, 2021. doi: 10.1007/978-3-030-90453-1\_20. URL https://doi.org/10.1007/978-3-030-90453-1\_20 . · DOI
- Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Zhiwei Steven Wu. Fully adaptive composition in differential privacy. CoRR , abs/2203.05481, 2022. doi: 10.48550/arXiv.2203.05481. URL https://doi.org/10.48550/arXiv.2203.05481 . · DOI
- Yuqing Zhu and Yu-Xiang Wang. Improving sparse vector technique with renyi differential privacy. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual , 2020. URL https://proceedings.neurips.cc/paper/2020/hash/e9bf14a419d77534105016f5ec122d62-Abstract.html .
Cited by
Sorted by citations
Bounded 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 74 · see citing works
Rahdari, A., Keshavarz, E., Nowroozi, E., Taheri, R., Hajizadeh, M., Mohammadi, M., Sinaei, S., & Bauschert, T. (2025) · IEEE Open Journal of the Communications Society · doi:10.1109/ojcoms.2025.3560034 · Cited by 48 · see citing works
Multi-Agent Risks from Advanced AI
Hammond, L., Chan, A., Clifton, J., Hoelscher-Obermaier, J., Khan, A., McLean, E., Smith, C., Barfuss, W., Foerster, J., Gavenčiak, T., et al. (2025) · arXiv · doi:10.48550/arxiv.2502.14143 · Cited by 10 · see citing works
A quantization-based technique for privacy preserving distributed learning
Colombo, M., Asal, R., Damiani, E., Qassem, L. M. M. S. A., Almemari, A. A., & Al-Hammadi, Y. (2025) · Future Generation Computer Systems · doi:10.1016/j.future.2025.107741 · Cited by 7 · see citing works
Yhdego, T. O., Wang, H., Chi, H., & Yu, Z. (2024) · Journal of Computing and Information Science in Engineering · doi:10.1115/1.4067086 · Cited by 6 · see citing works
Concentrated Differential Privacy for Bandits
Azize, A., & Basu, D. (2024) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml59370.2024.00013 · Cited by 4 · see citing works
Zhang, J., Wang, J., Long, S., Liu, G., Wang, L., & Yang, D. (2025) · Neurocomputing · doi:10.1016/j.neucom.2025.131415 · Cited by 3 · see citing works
Turbo: Effective Caching in Differentially-Private Databases
Kostopoulou, K., Tholoniat, P., Cidon, A., Geambasu, R., & Lécuyer, M. (2023) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3600006.3613174 · Cited by 3 · see citing works
A Critical Study of Composition Algorithms in Differential PrivacyPreprint
Yogi, M. K., & DrASNChakravarthy (2023) · doi:10.22541/au.169286062.22123310/v1
Session Types for the Concurrent Composition of Interactive Differential Privacy
Sannier, V., Baillot, P., & Gaboardi, M. (2025) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf64896.2025.00020
Concurrent Composition for Differentially Private Continual Mechanisms
Henzinger, M. R., Safavi, R., & Vadhan, S. (2026) · Proceedings of the ACM on Management of Data · doi:10.1145/3801895
PC-FT: A Lightweight and Utility-Preserving Private Fine-Tuning Framework for Edge-Based Agentic AI
Zhang, P., Zhang, R., Lv, Z., Fan, Q., Yuan, S., & Guan, Z. (2026) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2026.3694751
Private Learning of Littlestone Classes, Revisited
Lyu, X. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800924
Self-citationLiu, F., Yang, Q., Li, D., Shangguan, Z., Feng, L., Guo, Y., & Yang, B. (2026) · IEEE Internet of Things Journal · doi:10.1109/jiot.2026.3717620
- Authors
- Lyu, X.
- Corresponding author
- Lyu, Xin
- Venue
- Advances in Neural Information Processing Systems 35
- Published
- 2022
- Pages
- 9700-9712
- ISSN
- 1049-5258 (ISSN-L)
- OpenAlex
- W7133240612
- Cited by
- 13
- References
- 0
- Citations by year
- 2026: 4 · 2025: 4 · 2024: 3 · 2023: 2
- FWCI
- 1.24
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- neural information processing systems (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Funders
- Office of Naval Research (N00014-17-1, N00014, N00014-17)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Keywords
- composition theorem, differential privacy, privacy amplification
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
