Data privacy is a subfield of data management concerned with answering queries over sensitive datasets while protecting the privacy of the individuals they contain. One influential definition addressing this challenge is differential privacy [3][6]. Differential privacy is a mathematical notion guaranteeing that the distribution of a randomized algorithm’s output changes only slightly with or without the participation of a single individual in the dataset, making it robust to auxiliary information and post-processing.
Differential privacy also formalizes an inherent limitation of data analysis. The Fundamental Law of Information Recovery states that releasing overly accurate answers to too many queries unavoidably destroys privacy [1]. By introducing a quantitative privacy parameter $\varepsilon$ that bounds privacy loss, differential privacy provides a principled framework for managing this trade-off [3]. Therefore, the central goal is to delay the consequences of the Fundamental Law as long as possible while maintaining utility.
Since its introduction, several refinements of differential privacy (DP) have been proposed to obtain tighter privacy–utility trade-offs and sharper composition analyses. These include zero-concentrated differential privacy (zCDP) [5], Rényi differential privacy (RDP) [11], and Gaussian differential privacy (GDP) [2].
In this work, we focus on the original definition of $\varepsilon$-DP [3], also known as pure DP, and its relaxation $(\varepsilon,\delta)$-DP [7], which we refer to as approximate DP (ADP).
ADP strikes a balance between theoretical robustness and practical utility, as it relaxes the strict requirements of pure DP while preserving meaningful worst-case privacy guarantees. Moreover, many widely used mechanisms and refined privacy notions, such as those mentioned above, are most naturally analyzed in alternative frameworks and then translated into $(\varepsilon,\delta)$-DP, making ADP a natural common reference point.
One of the key reasons for the success of DP is its well-behaved composition properties, which allow privacy guarantees to degrade gracefully under multiple analyses. Composition lies at the heart of any meaningful privacy definition, as multiple outputs may be jointly analyzed by an adversary. Failures to account for composition have led to severe privacy breaches in earlier frameworks, such as $k$-anonymity [8].
Two fundamental composition theorems are sequential composition and parallel composition. Sequential composition [4] states that privacy losses add when multiple analyses are applied to the same dataset, while parallel composition captures the case in which analyses operate on disjoint subsets of the data, yielding significantly stronger privacy guarantees. The focus of this paper lies on the latter. Parallel composition naturally arises in common tasks such as cross-silo federated learning with local DP as well as group-by aggregate queries, where each individual contributes to at most one computation [10].
The main contribution of this paper is a rigorous and self-contained proof of the parallel composition theorem for ADP. While McSherry [10] establishes parallel composition for $\varepsilon$-DP under a general definition of Dwork’s pure DP, extending this result to $(\varepsilon,\delta)$-DP is not entirely straightforward, as the failure probability $\delta$ introduces mathematical indirections and non-linear scaling behaviors that are not present in pure DP.
Often, parallel composition is taken as obvious or intuitive for ADP [12], but no mathematical proof is given.
By working directly with the original definition of approximate differential privacy, our proof clarifies precisely how privacy losses compose in the presence of a nonzero $\delta$. This is particularly relevant since many modern privacy notions—such as RDP, zCDP, and GDP—are ultimately interpreted and compared via their induced $(\varepsilon,\delta)$-DP guarantees. Establishing parallel composition at this foundational level, therefore, strengthens the theoretical underpinnings of these conversions and ensures that commonly used privacy accounting techniques rest on solid mathematical ground.
Definitions of Differential Privacy
Differential privacy protects sensitive data by introducing randomness into data analysis algorithms. Such randomized algorithms are commonly referred to as mechanisms.
We are treating the input datasets as a collection of records over a domain $\mathbb{D}$. A domain is the Cartesian product of $m \geq 1$ attributes, which are finite sets:
\[\mathbb{D} := A_1 \times \dots \times A_m.\]An element of a domain, also called a row, is a vector $(a_1, \dots, a_m)$ with $a_i \in A_i$ for $i \in {1, \dots, m}$. We represent a dataset $D \in \mathbb{N}^{\lvert \mathbb{D} \rvert}$ in histogram notation. We denote $\mathbb{N}$ as the set of all non-negative integers, including zero. For each possible row $i \in \mathbb{D}$, the dataset specifies a non-negative integer count $d_i$. Throughout this work, we assume that each record corresponds to a single individual, so that modifying one row corresponds to modifying one person’s data, consistent with the modeling assumptions in [3].
Differential privacy is defined with respect to pairs of adjacent datasets, which differ in the data of a single individual. There are two commonly used notions of adjacency, referred to as unbounded and bounded differential privacy [9].
In the unbounded model, two datasets are adjacent if one can be obtained from the other by adding or removing a single record. Consequently, in this model, adjacent datasets may have different sizes. In the bounded model, two datasets are adjacent if they differ in the value of exactly one record, so that all datasets have a fixed size. The choice between these models determines the unit of privacy being protected and whether the dataset size itself is considered sensitive.
The original definition of differential privacy, also known as pure differential privacy, is taken from Dwork et al. [3].
Definition 1
(Unbounded $\varepsilon$-Differential Privacy [3])
Let $\varepsilon > 0$. A mechanism $\mathcal{M} : \mathbb{N}^{\lvert \mathbb{D} \rvert} \to R$ guarantees $\varepsilon$-differential privacy if for any two adjacent datasets $D, D’ \in \mathbb{N}^{\lvert \mathbb{D} \rvert}$ and for any measurable set $S \subseteq R$,
\[\mathbb{P}[\mathcal{M}(D) \in S] \leq e^{\varepsilon} \, \mathbb{P}[\mathcal{M}(D') \in S].\]Definition 1 is stated with respect to adjacent datasets under the unbounded model. If bounded adjacency is used instead, replacing one record can be viewed as removing one record and adding another, resulting in a privacy loss scaled by a constant factor. Mechanisms satisfying unbounded differential privacy can therefore be converted to bounded differential privacy with an appropriate adjustment of the privacy parameter.
McSherry [10] presents a formulation of differential privacy that removes the explicit restriction to adjacent datasets by scaling the privacy loss with the distance between datasets. Let
\[\|D\|_1 = \sum_{i=1}^{|\mathbb{D}|} |d_i|\]denote the $\ell_1$ norm of a dataset $D \in \mathbb{N}^{\lvert \mathbb{D} \rvert}$. Then $\lVert D - D’ \rVert_1$ counts how many rows differ, with replacement counted as two operations. McSherry uses the symmetric difference of datasets. Since we are using histogram notation and not considering datasets as sets, care must be taken with the interpretation. The $\ell_1$ distance can be seen as the multiset symmetric difference size of datasets $D, D’ \in \mathbb{N}^{\lvert \mathbb{D} \rvert}$.
Definition 2
(Group Privacy Formulation of Differential Privacy [10])
A randomized computation $\mathcal{M} : \mathbb{N}^{\lvert \mathbb{D} \rvert} \to R$ provides $\varepsilon$-differential privacy if for any two datasets $D, D’ \in \mathbb{N}^{\lvert \mathbb{D} \rvert}$ and any set of possible outputs $S \subseteq R$,
\[\mathbb{P}[\mathcal{M}(D) \in S] \leq e^{\varepsilon \lVert D - D' \rVert_1} , \mathbb{P}[\mathcal{M}(D') \in S].\]When $D$ and $D’$ differ by the addition or removal of a single record, $\lVert D - D’ \rVert_1 = 1$, and Definition 2 reduces to Definition 1. Under bounded adjacency, replacing one record yields $\lVert D - D’ \rVert_1 = 2$, resulting in a corresponding scaling of the privacy parameter.
This formulation makes the group privacy property of pure differential privacy explicit: if two datasets differ in the data of $k$ individuals, then the privacy loss scales linearly with $k$ under the exponential bound. In the following, we consider unbounded adjacency unless stated otherwise.
Pure differential privacy can be overly restrictive in some settings, motivating a relaxation that allows a small probability of failure. This leads to approximate differential privacy, introduced by Dwork et al. [7].
Definition 3
(Approximate Differential Privacy [7])
Let $\varepsilon \geq 0$ and $\delta \in [0,1]$. A mechanism $\mathcal{M}$ is $(\varepsilon,\delta)$-differential privacy if for any two adjacent datasets $D$ and $D’$ and any set
$ S \subseteq \mathcal{R} $,
\[\mathbb{P}[\mathcal{M}(D) \in S] \leq e^{\varepsilon} , \mathbb{P}[\mathcal{M}(D') \in S] + \delta.\]Approximate differential privacy is almost exclusively defined with respect to adjacent datasets in the literature, and we are not aware of a standard formulation that extends $(\varepsilon,\delta)$-differential privacy to arbitrary dataset pairs via a single distance-based inequality analogous to McSherry’s formulation for pure DP. The presence of the $\delta$ term complicates symmetric-difference scaling, as converting a single-step guarantee into bounds for larger dataset differences leads to nontrivial accumulation effects in both $\varepsilon$ and $\delta$, for which simple linear scaling in $\lVert D - D’ \rVert_1$ is generally not tight [4]. Consequently, group privacy and composition guarantees for approximate differential privacy are typically derived through specialized theorems rather than a unified distance-based definition.
Fundamental Properties of Differential Privacy
Differential privacy has several fundamental properties that make it particularly well-suited for practical data analysis. First, it treats all information as potentially identifying, thereby avoiding the need to enumerate or classify sensitive attributes explicitly. Second, it is robust to arbitrary auxiliary information, preventing linkage attacks that are possible under weaker privacy notions. Third, and most importantly for this work, differential privacy is compositional: privacy guarantees degrade in a controlled and analyzable manner when multiple analyses are performed [4].
A basic structural property of differential privacy is invariance under post-processing: once a mechanism satisfies differential privacy, any further computation on its output cannot weaken the privacy guarantee.
Proposition 1
(Post-Processing)
Let $\mathcal{M}: \mathbb{N}^{\lvert \mathbb{D} \rvert} \to R$ be a mechanism which is $(\varepsilon, \delta)$-differentially private and let $f: R \to R’$ be an arbitrary randomized mapping. Then $f \circ \mathcal{M}: \mathbb{N}^{\lvert \mathbb{D} \rvert} \to R’$ is $(\varepsilon, \delta)$-differentially private.
An immediate consequence of Proposition 1 and Definition 3 is that composing two $(\varepsilon,0)$-differentially private mechanisms on the same dataset yields a $(2\varepsilon,0)$-differentially private mechanism. This observation already illustrates how privacy loss accumulates under repeated analysis [4]. However, group privacy, which concerns the effect of changing multiple individuals’ data, and composition, which concerns multiple algorithmic releases, are conceptually distinct, even though both involve cumulative privacy loss.
The most general form of composition is sequential composition, which applies when multiple mechanisms are run on the same dataset.
Theorem 1
(Sequential Composition)
Let $\mathcal{M}_i: \mathbb{N}^{\lvert \mathbb{D} \rvert} \to R$ be $(\varepsilon_i, \delta_i)$-differentially private for $i \in {1, \dots, t}$. Then the composition $\mathcal{M}$ of the sequence $(\mathcal{M}_1, \dots, \mathcal{M}_t)$ is $(\varepsilon’, \delta’)$-differentially private, with
\[\varepsilon' = \sum_{i=1}^t \varepsilon_i \quad \text{and} \quad \delta' = \sum_{i=1}^t \delta_i.\]This result is proven in [4] and holds even under adaptive composition, meaning each mechanism may depend arbitrarily on the outputs of all preceding mechanisms.
A significantly stronger guarantee can be obtained when mechanisms operate on disjoint subsets of the data. This setting gives rise to parallel composition.
Theorem 2
(Parallel Composition)
Let $\mathbb{D}$ be a domain, let $D \in \mathbb{N}^{\lvert \mathbb{D} \rvert}$ be a dataset, and let $k$ be a positive integer. For $i \in [k]$, let $\mathbb{D}_i \subseteq \mathbb{D}$ and let $\mathcal{M}_i$ be a mechanism that takes $D \cap \mathbb{D}_i$ as input. Suppose that each $\mathcal{M}_i$ is $(\varepsilon_i, \delta_i)$-differentially private and that $\mathbb{D}_i \cap \mathbb{D}_j = \emptyset$ whenever $i \neq j$. Then the composition of the sequence $\mathcal{M}_1, \dots, \mathcal{M}_k$ is $(\varepsilon’, \delta’)$-differentially private, with
\[\varepsilon' = \max_i \varepsilon_i \quad \text{and} \quad \delta' = \max_i \delta_i.\]Whereas sequential composition is unavoidable in any functional privacy-preserving data analysis pipeline, parallel composition is essential for achieving good utility. Many realistic analyses involve computing aggregates over disjoint subpopulations. Treating such analyses as sequential composition would cause the privacy loss to scale with the number of subpopulations. In contrast, parallel composition allows these analyses to be performed with a fixed privacy cost, independent of the total number of queries, thereby enabling substantially more informative data releases at modest privacy cost.
Proof of Parallel Composition for Approximate Differential Privacy
This section is the core of this paper, dedicated to proving the parallel composition theorem for ADP.
We introduced McSherry’s [10] definition of $\varepsilon$-differential privacy, which was already used to prove parallel composition. Since Definition 2 is a generalization of Definition 1, his proof also holds for the latter.
However, a rigorous proof for the parallel composition theorem using ADP was not yet provided. This paper fills this gap. Since mechanisms that satisfy unbounded differential privacy also satisfy bounded differential privacy (via a conversion that decreases the privacy guarantee slightly), we only consider adjacent datasets obtained by adding or removing an entry.
The proof of Theorem 2 now follows.
Proof
Let $D$ and $D’$ be adjacent datasets differing in exactly one individual. For each $i \in [k]$, define
$D_i := D \cap \mathbb{D}_i$ and $D’_i := D’ \cap \mathbb{D}_i$.
Since the subsets $\mathbb{D}_i$ are pairwise disjoint, there exists a unique index $m \in [k]$ such that $D_m \neq D’_m$, while $D_i = D’_i$ for all $i \neq m$.
Let $\mathcal{M}$ denote the composition of mechanisms defined by
\[\mathcal{M}(D) := (\mathcal{M}_1(D_1), \dots, \mathcal{M}_k(D_k)),\]and let each $\mathcal{M}_i$ be $(\varepsilon_i, \delta_i)$-differentially private for $i \in [k]$.
For an arbitrary output vector $r = (r_1, \dots, r_k)$, define
\[\mathbb{P}\big[ \mathcal{M}i(D_i) = r_i \mid \mathcal{M}1(D_1) = r_1 \land \dots \land \mathcal{M}{i-1}(D{i-1}) = r_{i-1} \big].\]Then it follows that
\[\begin{aligned} \mathbb{P}[\mathcal{M}(D) = r] &= \prod_{i=1}^k \mathbb{P}[\mathcal{M}^r_i(D_i) = r_i] \\ &= \mathbb{P}[\mathcal{M}^r_m(D_m) = r_m] \cdot \prod_{\substack{i=1 \\ i \neq m}}^k \mathbb{P}[\mathcal{M}^r_i(D_i) = r_i] \\ &\leq \left( e^{\varepsilon_m} \mathbb{P}[\mathcal{M}^r_m(D'_m) = r_m] + \delta_m \right) \\ &\qquad\cdot \prod_{\substack{i=1 \\ i \neq m}}^k \mathbb{P}[\mathcal{M}^r_i(D_i) = r_i] \\ &= e^{\varepsilon_m} \prod_{i=1}^k \mathbb{P}[\mathcal{M}^r_i(D'_i) = r_i] \\ &\qquad+ \delta_m \prod_{\substack{i=1 \\ i \neq m}}^k \mathbb{P}[\mathcal{M}^r_i(D_i) = r_i] \\ &= e^{\varepsilon_m} \mathbb{P}[\mathcal{M}(D') = r] \\ &\qquad+ \delta_m \prod_{\substack{i=1 \\ i \neq m}}^k \mathbb{P}[\mathcal{M}^r_i(D_i) = r_i]. \end{aligned}\]Since all probabilities are at most $1$, the product term is bounded by $1$. Moreover, $\varepsilon_m \leq \max_i \varepsilon_i$ and $\delta_m \leq \max_i \delta_i$, yielding
\[\mathbb{P}[\mathcal{M}(D) = r] \leq e^{\max_i \varepsilon_i} \mathbb{P}[\mathcal{M}(D') = r] \max_i \delta_i.\]This inequality holds for all outputs $r$, and therefore the mechanism $\mathcal{M}$ satisfies $(\max_i \varepsilon_i, \max_i \delta_i)$-differential privacy according to Definition 3.
Discussion
This post provides a rigorous and self-contained proof of the parallel composition theorem for approximate differential privacy, derived directly from the original definition of $(\varepsilon,\delta)$-DP. Although parallel composition is widely used in practice, a formal proof at the level of approximate differential privacy has been largely missing from the literature. Our result closes this gap and gives a precise mathematical justification for a principle that underpins many deployed privacy-preserving systems. The proof clarifies how the disjointness of data subsets ensures that only one mechanism contributes to the privacy loss when considering unbounded differential privacy.
Parallel composition is essential for achieving useful privacy guarantees in realistic data analysis settings, including group-by queries and federated learning, where analyses naturally operate on disjoint subsets of individuals. By ensuring that privacy costs depend only on the worst-case mechanism rather than the number of parallel computations, parallel composition enables scalable and interpretable privacy accounting.
Finally, since many modern privacy notions are ultimately translated into $(\varepsilon,\delta)$-DP guarantees, this result strengthens the theoretical foundations of such conversions and supports their use in practice.
References
[1] Irit Dinur and Kobbi Nissim. “Revealing Information While Preserving Privacy.” In: Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM, 2003, pp. 202–210.
[2] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian Differential Privacy. May 30, 2019. arXiv: 1905.02383 [cs]. DOI · arXiv (visited on 11/25/2025).
[3] Cynthia Dwork. “Differential Privacy.” 2006.
[4] Cynthia Dwork and Aaron Roth. “The Algorithmic Foundations of Differential Privacy.” Foundations and Trends in Theoretical Computer Science 9.3 (2013), pp. 211–407. ISSN: 1551-305X, 1551-3068. DOI (visited on 10/10/2025).
[5] Cynthia Dwork and Guy N. Rothblum. Concentrated Differential Privacy. Mar. 16, 2016. arXiv: 1603.01887 [cs]. DOI · arXiv (visited on 10/10/2025).
[6] Cynthia Dwork et al. “Calibrating Noise to Sensitivity in Private Data Analysis.” In: Theory of Cryptography. Vol. 3876, 2006, pp. 265–284. ISBN: 978-3-540-32731-8. DOI.
[7] Cynthia Dwork et al. “Our Data, Ourselves: Privacy via Distributed Noise Generation.” In: Advances in Cryptology – EUROCRYPT 2006. Lecture Notes in Computer Science. St. Petersburg, Russia: Springer, 2006, pp. 486–503.
[8] Srivatsan R. Ganta, Shiva Prasad Kasiviswanathan, and Adam Smith. “Composition Attacks and Auxiliary Information in Data Privacy.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). ACM, 2008, pp. 265–273.
[9] Daniel Kifer and Ashwin Machanavajjhala. “No Free Lunch in Data Privacy.” In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. SIGMOD/PODS ’11. Athens, Greece: ACM, June 12, 2011, pp. 193–204. ISBN: 978-1-4503-0661-4. DOI (visited on 12/22/2025).
[10] Frank D. McSherry. “Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis.” In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. SIGMOD/PODS ’09. Providence, Rhode Island, USA: ACM, June 29, 2009, pp. 19–30. ISBN: 978-1-60558-551-2. DOI (visited on 12/12/2025).
[11] Ilya Mironov. “Rényi Differential Privacy.” In: 2017 IEEE 30th Computer Security Foundations Symposium (CSF). Aug. 2017, pp. 263–275. arXiv: 1702.07476 [cs]. DOI · arXiv (visited on 10/10/2025).
[12] Natalia Ponomareva et al. “How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy.” Journal of Artificial Intelligence Research 77 (July 23, 2023), pp. 1113–1201. ISSN: 1076-9757. arXiv: 2303.00654 [cs]. DOI · arXiv (visited on 10/10/2025).
Author: Clara E. Pichler