---
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '22318'
abstract:
- lang: eng
text: "Many intended uses of differential privacy involve a continual mechanism
that is set up to run continuously\r\nover a long period of time, making more
statistical releases as either queries come in or the dataset is updated.\r\nIn
this paper, we give the first general treatment of privacy against adaptive adversaries
for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily
interleaved. It also models a very general notion\r\nof neighboring, that includes
both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems
for continual mechanisms, which ensure privacy even when an adversary can interleave
its queries\r\nand dataset updates to the different composed mechanisms. Previous
concurrent composition theorems for\r\ndifferential privacy were only for the
case when the dataset is static, with no adaptive updates. We also give\r\nthe
first interactive and continual generalizations of the “parallel composition theorem”
for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue
of the noninteractive parallel composition theorem\r\nholds if either there are
no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential
privacy, but it fails to hold for composing approximately differentially private
mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem
for this case. In addition, we prove concurrent\r\nfilter compositions theorems
for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend
these results to other measures of differential privacy, including Rényi DP and
\U0001D453 -DP.\r\nWe then formalize a set of general conditions on a continual
mechanism M that runs multiple continual submechanisms such that the privacy guarantees
of M follow directly using the above concurrent composition\r\ntheorems on the
sub-mechanisms, without further privacy loss. This enables us to give a simpler
and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger,
Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof
that shows that its privacy holds against adaptive adversaries.\r\nWe also provide
a framework that simplifies the analysis of local differential privacy when the
protocol\r\nincludes multi-round server-user interactions. Using this result,
we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala,
Henzinger, Li, Liu, Sricharan, and Zhu [5]."
acknowledgement: "1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from
the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting
Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported
by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi
were supported by the European Research Council (ERC)\r\nunder the European Union’s
Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564),
and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982,
and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic
copyright license to any author-accepted manuscript version arising from this submission.\r\nViews
and opinions expressed are however those of the author(s)\r\nonly and do not necessarily
reflect those of the European Union\r\nor the European Research Council Executive
Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible
for them."
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Salil
full_name: Vadhan, Salil
last_name: Vadhan
citation:
ama: Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially
private continual mechanisms. Proceedings of the ACM on Management of Data.
2026;4(2):1-26. doi:10.1145/3801895
apa: Henzinger, M., Safavi Hemami, R., & Vadhan, S. (2026). Concurrent composition
for differentially private continual mechanisms. Proceedings of the ACM on
Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801895
chicago: Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent
Composition for Differentially Private Continual Mechanisms.” Proceedings of
the ACM on Management of Data. Association for Computing Machinery, 2026.
https://doi.org/10.1145/3801895.
ieee: M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for
differentially private continual mechanisms,” Proceedings of the ACM on Management
of Data, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026.
ista: Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially
private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2),
1–26.
mla: Henzinger, Monika, et al. “Concurrent Composition for Differentially Private
Continual Mechanisms.” Proceedings of the ACM on Management of Data, vol.
4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:10.1145/3801895.
short: M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management
of Data 4 (2026) 1–26.
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-13T14:59:14Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-07-16T09:14:49Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3801895
ec_funded: 1
external_id:
arxiv:
- '2411.03299'
file:
- access_level: open_access
checksum: c6c5e256d02b90682c0690c3bee94040
content_type: application/pdf
creator: dernst
date_created: 2026-07-16T09:09:53Z
date_updated: 2026-07-16T09:09:53Z
file_id: '22345'
file_name: 2026_ACMMgmtData_Henzinger.pdf
file_size: 655405
relation: main_file
success: 1
file_date_updated: 2026-07-16T09:09:53Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '2'
keyword:
- differential privacy
- concurrent composition
- continual release
- continual observation
- data streaming
- continual mechanisms
- concurrent parallel composition
- concurrent filter composition
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1-26
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
publication: Proceedings of the ACM on Management of Data
publication_identifier:
issn:
- 2836-6573
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Concurrent composition for differentially private continual mechanisms
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2026'
...