Composition Theorems for Interactive Differential Privacy

Introduction

By now, differential privacy (Dwork et al., 2006b) has been widely accepted as a standard framework for protecting individual privacy when performing data analysis on data sets that may contain sensitive information of individuals (see, e.g., the surveys by Dwork and Roth (2014); Vadhan (2017)).

Let ${\mathcal{M}}$ be an algorithm that runs on a data set $x$ and calculates some information about it. Roughly speaking, ${\mathcal{M}}$ is called differentially private, if the output distribution of $\mathcal{A}$ remains nearly identical when we arbitrarily modify a single entry in $x$.

One essential feature of differential privacy is its composability. Composition captures the scenario where a data analyst runs $k$ differentially private algorithms sequentially, and releases the results afterward. Typically, a composition theorem has the following form: if each of the $k$ algorithms satisfies differential privacy, then the analyst’s output is still differentially private with moderately degraded privacy parameters.

Composition theorems are important for at least two reasons. First, we might want to perform computation tasks on the same data set multiple times and still have reasonable control over the privacy loss. In this case, composition theorems reveal how the privacy guarantee degrades over time. More importantly, composition theorems allow us to build more complex and powerful differentially-private algorithms from simple primitives, and argue the privacy guarantee of the combined algorithm in a straightforward way.

There is a rich literature concerning the composition property of differential privacy (see, e.g., Dwork et al. (2006a, 2010); Kairouz et al. (2015); Murtagh and Vadhan (2018); Bassily et al. (2021)). However, most existing composition theorems only consider the scenario where an analyst runs several private algorithms sequentially. That is, the analyst will only move on to the next algorithm after finishing their computation with the previous one. In contrast, many fundamental primitives in differential privacy are interactive in nature, such as the sparse vector technique (Dwork et al., 2009; Roth and Roughgarden, 2010) and private multiplicative weight updates (Hardt and Rothblum, 2010). Hence, the interactivity issue appears to be a significant limitation of current composition theorems. Namely, the data analyst may want to communicate with several interactive mechanisms concurrently, and interleave its queries to the mechanisms arbitrarily. A sequential composition theorem completely fails to capture this scenario. Also, in practice, deployments of DP algorithms often demand a better understanding of concurrent compositions of interactive mechanisms (Hay et al., 2020).

Recently, Vadhan and Wang (2021) initiated a study of concurrent compositions and proved an optimal concurrent composition theorem for pure differential privacy. In this work, we significantly advance this research direction by proving optimal concurrent composition theorems for several popular notions of differential privacy, including approximate DP, Rényi DP, zero-concentrated DP and truncated concentrated DP.

Before we continue, we set up necessary pieces of notation. We use ${\mathcal{X}}$ and ${\mathcal{Y}}$ to denote the domain of query messages and responses, respectively. We assume that both ${\mathcal{X}}$ and ${\mathcal{Y}}$ are finite sets. This assumption is for easing some mathematical manipulation and is not restrictive: all practical applications of differential privacy have finite input and output spaces anyway.

For a set $S$, denote by $\Delta(S)$ the set of all possible distributions supported over $S$. We define interactive systems below.

An interactive system is a (randomized) algorithm ${\mathcal{M}}\colon({\mathcal{X}}\times{\mathcal{Y}})^{*}\times{\mathcal{X}}\to\Delta({\mathcal{Y}})$. The input to ${\mathcal{M}}$ is an interaction history $(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{t},y_{t})\in({\mathcal{X}}\times{\mathcal{Y}})^{t}$ together with a query $x_{t+1}$. The output of ${\mathcal{M}}$ is denoted by $y_{t+1}\sim{\mathcal{M}}((x_{i},y_{i})_{i\in[t]},x_{t+1})$.

A technicality worth mentioning is that due to the internal memory and randomness of an interactive system ${\mathcal{M}}$, the response of ${\mathcal{M}}$ to the $(t+1)$-th query might be correlated with its responses to previous queries. Although the internal randomness of ${\mathcal{M}}$ is not explicitly stated as a parameter, Definition 1 captures this correlation by requiring that each query $x_{t+1}$ to ${\mathcal{M}}$ is attached with the interaction history $(x_{1},y_{1}),\dots,(x_{t},y_{t})$. This history is sufficient for determining the conditional distribution of the response ${\mathcal{M}}((x_{i},y_{i})_{i\in[t]},x_{t+1})$ without specifying the internal randomness and memory.

We make a distinction between mechanisms and systems. By “mechanism” we mean a differentially private algorithm ${\mathcal{M}}$ that holds a sensitive input $d$ and answers queries about it. When applied to a concrete input $d$, ${\mathcal{M}}$ induces an interactive system, denoted by ${\mathcal{M}}^{d}$. According to the definition of differential privacy, studying the privacy of a mechanism boils down to studying the pair of systems $({\mathcal{M}}^{d},{\mathcal{M}}^{d^{\prime}})$ induced by running ${\mathcal{M}}$ on every pair of neighboring inputs $(d,d^{\prime})$. For brevity, we usually assume W.L.O.G. that the input only consists of a single bit $b\in\{0,1\}$, and we compare the two systems ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ induced by ${\mathcal{M}}$.

In the special case $k=1$, there is only one system ${\mathcal{M}}$ and the adversary is interacting with it. We define approximate differential privacy for interactive mechanisms in this case.

Two interactive systems ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ are called $(\varepsilon,\delta)$-indistinguishable, if for every $b\in\{0,1\}$, every adversary $\mathcal{A}$ and every collection of transcripts $S\subseteq\{(x_{i},y_{i})_{i\in[T]}\}$, it holds that

Let ${\mathcal{M}}$ be an interactive mechanism. ${\mathcal{M}}$ is called $(\varepsilon,\delta)$-approximate differentially private (or $(\varepsilon,\delta)$-DP for short), if for every two neighboring data sets $d$ and $d^{\prime}$, the systems ${\mathcal{M}}^{d}$ and ${\mathcal{M}}^{d^{\prime}}$ are $(\varepsilon,\delta)$-indistinguishable.

2 Differential Privacy in Concurrent Compositions

Vadhan and Wang (2021) also considered the case $\delta>0$ (i.e., approximate DP). However, for this case, they only showed an upper bound on $\varepsilon^{\prime},\delta^{\prime}$ that is inferior to the basic composition in the sequential setting. It was asked as an open question in Vadhan and Wang (2021) whether the optimal composition theorem for approximate DP still holds in the concurrent composition.

Besides pure and approximate DP, there are also other notions of differential privacy that are extensively studied in the literature. A non-exhaustive list includes Rényi DP (Mironov, 2017), concentrated DP (Dwork and Rothblum, 2016; Bun and Steinke, 2016; Bun et al., 2018), Gaussian DP and $f$-DP (Dong et al., 2022) etc. Compared with the standard notion of $(\varepsilon,\delta)$-approximate DP, these variants of DP either allow for a simplified analysis of private algorithms or give sharper bounds of privacy guarantee. In the sequential composition, the composition property of these variants has been well understood. It is also interesting to extend these composition theorems to the concurrent composition, thereby expanding the potential applicability of these DP notions.

Our Results

In this work, we give an affirmative answer to the open question mentioned above. Moreover, our result confirms that several major differential privacy definitions in the literature enjoy the same composition guarantee in the concurrent composition, just as they do in the sequential composition.

Approximate differential privacy. $(\varepsilon,\delta)$-DP is arguably the most widely studied notion of differential privacy and is deemed the “standard” definition of DP. As our first main result, we show an optimal concurrent composition theorem for approximate DP.

In particular, when the privacy parameter for each mechanism is the same $(\varepsilon,\delta)$, their concurrent composition satisfies $O(\sqrt{k\log(1/\delta^{\prime})}\varepsilon,\delta^{\prime}+k\delta)$-DP for all $\delta^{\prime}\in(0,1)$.

Rényi differential privacy. Rényi differential privacy was first defined by Mironov (2017). We recall its definition.

Let $P,Q$ be two distributions supported over ${\mathcal{X}}$. For each $\alpha>1$, define the Rényi divergence of order $\alpha$ of $P$ from $Q$ as

Two interactive systems are called $(\alpha,\varepsilon)$-Rényi close, if for every adversary $\mathcal{A}$ and every $b\in\{0,1\}$, it holds that

Let ${\mathcal{M}}$ be a mechanism. ${\mathcal{M}}$ is called $(\alpha,\varepsilon)$-Rényi differentially private (or $(\alpha,\varepsilon)$-RDP for short), if for every two neighboring data sets $d$ and $d^{\prime}$, the systems ${\mathcal{M}}^{d}$ and ${\mathcal{M}}^{d^{\prime}}$ are $(\alpha,\varepsilon)$-Rényi close.

A main advantage of Rényi DP is that it has a natural and simple composition. In the sequential setting, it is known that if two mechanisms ${\mathcal{M}}_{1},{\mathcal{M}}_{2}$ are $(\alpha,\varepsilon_{1})$ and $(\alpha,\varepsilon_{2})$-RDP, respectively, then the composition of ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$ is $(\alpha,\varepsilon_{1}+\varepsilon_{2})$-RDP. Our next theorem generalizes this result to the concurrent composition setting.

One implication of Theorem 2 is that the zero-concentrated differential privacy by Bun and Steinke (2016) and the truncated concentrated differential privacy by Bun et al. (2018) also compose nicely under the concurrent composition. We state the corollary below, and prove it in Appendix A.3 for completeness.

Theorem 1, 2 and Corollary 1 provide compelling evidence that the adversary gains no advantage by interleaving its queries to independently running mechanisms. Consequently, interactivity can be viewed as a feature that differential privacy grants us for free.

Concurrent and independent work. Concurrently to our work, a recent work by Vadhan and Zhang (2022) proves an optimal concurrent composition theorem for $f$-DP (Dong et al., 2022). By the standard connection, their result implies the optimal concurrent composition theorem for approximate DP. However, our techniques are very different than theirs. Their result is stronger, as it is known that approxiamte-DP can be seen as a special case of $f$-DP (Dong et al., 2022). However, our proof for approximate DP is more elementary: we do not need to work through $f$-DP as their proof does. Furthermore, our proof comes with several interesting technical ingredients that might be of independent interests. This includes a structural result for interactive mechanisms (Theorem 3), as well as a dual perspective to reason about Rényi divergences (Lemma 4).

Implications of Our Results

In this section, we discuss implications of our results, and demonstrate how they offer more than the sequential composition theorems.

Designing new algorithms. The optimal concurrent composition theorem makes it possible to design new differentially private algorithm that involves running several building blocks concurrently. As one motivating example, consider the Sparse Vector Technique (SVT). The standard SVT (as in Dwork and Roth (2014)) and its variants have been studied extensively in the literature. In particular, it was observed by Lyu et al. (2017); Zhu and Wang (2020) that one can add noise to the threshold only once, and then use the noisy threshold to answer $c>1$ “meaningful” queries (namely, after reporting each meaningful query, the SVT algorithm does NOT refresh the noisy threshold). It was argued in (Lyu et al., 2017; Zhu and Wang, 2020) that this variant of SVT can offer a higher accuracy while consuming the same amount of privacy budget, both theoretically and empirically.

However, this variant of SVT has received relatively less attention in literature. One reason might be that it is unclear what happens if we compose this SVT with other mechanisms. In particular, the standard SVT refreshes its threshold after answering each “meaningful” query, which allows one to decompose the algorithm into $c$ pieces of smaller SVT algorithms, and then compose with other mechanisms via the sequential computation. In contrast, the variants by Lyu et al. (2017); Zhu and Wang (2020) work by answering each “meaningful query” using the same noisy threshold, which do not seem to admit such a decomposition. This makes this variant less appealing: in most applications, people want to use SVT as a supporting subroutine for other algorithms. Therefore, it is crucial to understand the (concurrent) composition behavior of SVT with other mechanisms.

Now, with the new concurrent composition theorem, we can plug this variant of SVT in any algorithm, and argue the privacy guarantee of the whole computation by black-box applying Theorems 1 and 2 (depending on whether we are working with $(\varepsilon,\delta)$-DP or RDP). To illustrate the idea, in Appendix B, we apply Theorem 1 to analyze a simple algorithm: private “Guess-and-Check” with the aforementioned variant of SVT as a subroutine. We hope our example can motivate people to design more powerful algorithms by concurrently composing simple building blocks.

Practical Implication. Besides the theoretical interests, our theorem has implications for practical deployments of interactive DP mechanisms. For one example, suppose there is a data center that holds the private information of individuals and offers data analysts access to the database (interactively and differentially-privately). Without knowing the concurrent composition theorem, it might be possible that some $k>1$ analysts can collude by coordinating their (interactive) queries to the database and extracting much more sensitive information. Our result refutes the possibility of such an attack. In particular, suppose each data analyst has only an $(\varepsilon,\delta)$-DP amount of privacy “quota”. Then, even if they collude and spend their privacy budget in whatever way, their computation result is still $(O(\sqrt{k\log(1/\delta^{\prime})}\varepsilon),k\delta+\delta^{\prime})$-DP with respect to the private database.

Proof of Main Results

In this section, we show the proof of our results. We start with a very brief proof overview. We prove Theorem 1 by a reduction to the sequential composition of $k$ (approximate) randomized response mechanisms. This generalizes the idea developed by Vadhan and Wang (2021). To prove Theorem 2, we take a completely different approach, and our technique offers new tools to analyze Rényi DP. Namely, we propose an alternative characterization of Rényi divergence (Lemma 4), which allows for a fine-grained account of the privacy loss in the complex interaction involving multiple mechanisms. The characterization of Rényi divergence might find itself useful in other applications.

Notation. Let $P,Q$ be two distributions supported over $X$. For a real $\eta>0$, we say that $P\geq\eta Q$, if for every $S\subseteq X$, it holds that

Furthermore, we say $P\equiv Q$, if $P$ and $Q$ are identically distributed.

To prove Theorem 1, we follow the approach by Vadhan and Wang (2021), where they showed that one can simulate two $(\varepsilon,0)$-indistinguishable interactive systems by post-processing a randomized response mechanism. This simulation enables them to reduce the concurrent composition to a sequential composition, and the optimal composition theorem follows. It was asked as an open question in Vadhan and Wang (2021) whether the same simulation can be carried out for approximate DP. We answer this question affirmatively.

Review of the Vadhan-Wang approach. It would be instructive to review the proof by Vadhan and Wang (2021) first. Let ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ be the pair of systems by running the private mechanism on a pair of neighboring data sets. The adversary $\mathcal{A}$ interacts with ${\mathcal{M}}^{b}$ for some $b\in\{0,1\}$ and wants to find out the value of $b$. An intuitive yet delicate fact due to Vadhan and Wang (2021) is that, if ${\mathcal{M}}^{0}$ and ${\mathcal{M}}^{1}$ are $(\varepsilon,0)$-indistinguishable, then there exist two systems ${\mathcal{N}}^{0},{\mathcal{N}}^{1}$ such that, for every adversary $\mathcal{A}$, the distribution of $\mathbf{IT}(\mathcal{A}:{\mathcal{M}}^{b})$ is identical to $\frac{e^{\varepsilon}}{1+\varepsilon}\mathbf{IT}(\mathcal{A}:{\mathcal{N}}^{b})+\frac{1}{1+e^{\varepsilon}}\mathbf{IT}(\mathcal{A}:{\mathcal{N}}^{1-b})$. This enables one to simulate the many-round interaction between $\mathcal{A}$ and ${\mathcal{M}}^{b}$ by running a one-round randomized response mechanism.

Note that the left hand side of (2) can be simulated by a sequential composition of $k$ randomized response mechanisms. Invoking the optimal composition theorem for sequential composition (Kairouz et al., 2015; Murtagh and Vadhan, 2018) concludes the proof.

Extension to approximate DP. Now, if ${\mathcal{M}}^{0}$ and ${\mathcal{M}}^{1}$ are $(\varepsilon,\delta)$-indistinguishable with $\delta>0$, there might not be a nice decomposition of ${\mathcal{M}}^{b}$ into $\frac{e^{\varepsilon}}{1+e^{\varepsilon}}{\mathcal{N}}^{b}+\frac{1}{1+e^{\varepsilon}}{\mathcal{N}}^{1-b}$. Still, it is plausible to conjecture that there is a decomposition of ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ with four systems ${\mathcal{N}}^{0},{\mathcal{N}}^{1},{\mathcal{E}}^{0},{\mathcal{E}}^{1}$ such that for each $b\in\{0,1\}$,

Our main technical result in this subsection proves the existence of such a decomposition.

Two systems ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ are $(\varepsilon,\delta)$-indistinguishable, if and only if there are four systems ${\mathcal{N}}^{0},{\mathcal{N}}^{1},{\mathcal{E}}^{0},{\mathcal{E}}^{1}$ satisfying the following: for every adversary $\mathcal{A}$ and $b\in\{0,1\}$, it holds that

Theorem 3 implies Theorem 1 by a similar reduction to (approximate) random response. For completeness, we include a proof in Appendix A.1.

We prove Theorem 3 by establishing a series of lemmas. In the following, we state these lemmas and explain their intuition. We defer the formal proof to Appendix A.1.

Suppose ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ are $(\varepsilon,\delta)$-indistinguishable. There are two systems ${\mathcal{E}}^{0},{\mathcal{E}}^{1}$ satisfying the following.

For every adversary $\mathcal{A}$ and $b\in\{0,1\}$, it holds that $\mathbf{IT}(\mathcal{A}:{\mathcal{M}}^{b})\geq\delta\cdot\mathbf{IT}(\mathcal{A}:{\mathcal{E}}^{b})$.

For every adversary $\mathcal{A}$, every set of transcripts $S\subseteq\{(x_{i},y_{i})_{i\in[T]}\}$ and $b\in\{0,1\}$, it holds that

Roughly, Lemma 1 says that there are two systems ${\mathcal{E}}^{0},{\mathcal{E}}^{1}$ that capture the low-probability “bad behavior” of ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$. It is the primary technical contribution of this subsection. We prove Lemma 1 by explicitly constructing the two systems ${\mathcal{E}}^{0},{\mathcal{E}}^{1}$. That is, we specify the probability density functions $\Pr[{\mathcal{E}}^{b}((x_{j},y_{j})_{j<i},x_{i})=y_{i}]$ for ${\mathcal{E}}^{0},{\mathcal{E}}^{1}$ step by step, in the increasing order of $i=1,2,\dots,T$.

Suppose ${\mathcal{M}},{\mathcal{E}}$ are two systems such that for every adversary $\mathcal{A}$, it holds that $\mathbf{IT}(\mathcal{A}:{\mathcal{M}})\geq\delta\mathbf{IT}(\mathcal{A}:{\mathcal{E}})$. Then there is a system ${\mathcal{N}}$ such that for every adversary $\mathcal{A}$, it holds that

For intuition, suppose $P,Q$ are two distributions such that $P\geq\delta Q$. Then one can easily find a distribution $Q^{\prime}$ such that $P\equiv\delta Q+(1-\delta)Q^{\prime}$. The proof of Lemma 2 extends this simple idea.

Suppose ${\mathcal{N}}^{0},{\mathcal{N}}^{1}$ are $(\varepsilon,0)$-indistinguishable. Then there are two systems ${\mathcal{N}}^{0^{\prime}},{\mathcal{N}}^{1^{\prime}}$ such that for every adversary $\mathcal{A}$, it holds that

Wrap-up. We can conclude the proof for Theorem 3 now. The “if” direction is obvious: the existence of a decomposition satisfying (4) implies that ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ are $(\varepsilon,\delta)$-indistinguishable. For the other direction, we start by constructing ${\mathcal{E}}^{0},{\mathcal{E}}^{1}$ using Lemma 1. Then we construct ${\mathcal{N}}^{0},{\mathcal{N}}^{1}$ by Lemma 2. Lemma 1 and 2 together ensure that ${\mathcal{N}}^{0}$ and ${\mathcal{N}}^{1}$ are $(\varepsilon,0)$-indistinguishable, which enables us to invoke Lemma 3 and decompose ${\mathcal{N}}^{0},{\mathcal{N}}^{1}$ into ${\mathcal{N}}^{0^{\prime}},{\mathcal{N}}^{1^{\prime}}$. $({\mathcal{E}}^{0},{\mathcal{E}}^{1},{\mathcal{N}}^{0^{\prime}},{\mathcal{N}}^{1^{\prime}})$ forms the final decomposition. It is straightforward to verify that they satisfy (4).

2 Rényi Differential Privacy

Our result for Rényi differential privacy (Theorem 2) takes a completely different approach.

An intuition. Let ${\mathcal{M}}_{1}$ be an $(\alpha,\varepsilon)$-Rényi DP mechanism. Intuitively, $(\alpha,\varepsilon)$-Rényi DP means that ${\mathcal{M}}_{1}$ has $\varepsilon$ unit of privacy budget and can distribute it to $T$ queries. Viewing the privacy budget as a form of “deposit”, we hope to argue that two or more independently running mechanisms spend their deposit independently, and an adversary cannot trigger any mechanism to spend more privacy budget than it holds by interacting with other mechanisms.

However, unlike some intuitive and easy-to-measure resources such as time and energy, the notion of privacy loss looks somewhat illusive. Even worse, we need to reason about this elusive resource in a stochastic process consisting of interactions with multiple systems. It was not clear how one can quantify the privacy loss in such an interactive and complex process. Nonetheless, we manage to find a new approach to do so.

An alternative characterization for Rényi DP. We introduce the following characterization of Rényi divergence based on Hölder’s inequality and duality. That is, we prove

Suppose $P,Q$ are two distributions supported over ${\mathcal{Y}}$. For every $\alpha>1$ and $B\geq 0$, let $\beta=\frac{\alpha}{\alpha-1}$ be the Hölder conjugate of $\alpha$. The following statements are equivalent.

Note that if we let $\alpha\to\infty$, then Lemma 4 converges to a characterization of pure-DP. That is, $D_{\infty}(P\|Q)\leq B$ if and only if $\Pr[P=y]\leq e^{B}\Pr[Q=y]$ for every $y\in{\mathcal{Y}}$.

Lemma 4 provides a convenient tool to reason about the privacy loss in an interactive environment consisting of multiple rounds. Intuitively, this is because Condition $2$ in the statement above is more amenable to a “hybrid argument”. However, to quantify the privacy loss during an interaction, we still need to find a way to track the privacy loss.

When ${\mathcal{Y}}$ is a finite set, the integral coincides with an equivalent summation. i.e.,

We will use integral and summation interchangeably.

In this notation, Lemma 4 can be equivalently stated as $D_{\alpha}(P\|Q)\leq B$ if and only if $P$ is $\beta$-dominated by $e^{B}Q$ for $\beta=\frac{\alpha}{\alpha-1}$ .

Let $\beta\geq 1,B\geq 0$ be two reals. Let $\alpha=\frac{\beta}{\beta-1}$. For each $y_{1}\in{\mathcal{Y}}_{1}$, define

Proof for a $3$-round toy example. We are ready to describe the proof for Theorem 2. To illustrate the idea, we prove a toy case here and defer the full proof to Appendix A.2. The proof for the toy case includes all the important ideas. Extending it to a full proof is straightforward.

We describe the toy scenario now. Suppose there are two mechanisms ${\mathcal{M}}_{1},{\mathcal{M}}_{2}$ that run on a sensitive input bit $b\in\{0,1\}$. The interaction consists of $3$ rounds. The adversary $\mathcal{A}$ communicates with ${\mathcal{M}}_{1},{\mathcal{M}}_{2},{\mathcal{M}}_{1}$ in order, and outputs the response $(y_{1},y_{2},y_{3})$. For brevity, we assume that each response $y_{i}$ contains a copy of the query message $x_{i}$, so that we recover the whole transcript $((x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3}))$ only from the responses.

Let $P,Q\in\Delta({\mathcal{Y}}\times{\mathcal{Y}}\times{\mathcal{Y}})$ be the output distribution when $\mathcal{A}$ interacts with $({\mathcal{M}}^{0}_{1},{\mathcal{M}}^{0}_{2})$ and $({\mathcal{M}}^{1}_{1},{\mathcal{M}}^{1}_{2})$, respectively. Suppose ${\mathcal{M}}_{1},{\mathcal{M}}_{2}$ are $(\alpha,\varepsilon_{1})$, $(\alpha,\varepsilon_{2})$-Rényi DP respectively. Our goal is to prove that

where $\beta=\frac{\alpha}{\alpha-1}$ is the Hölder conjugate of $\alpha$. Let $P_{1},P_{2},P_{3}$ be the projection of $P$ onto the three rounds, and let $P_{i}|_{y_{<i}}$ denote the distribution of $y_{i}$ conditioning on $y_{1},\dots,y_{i-1}$. Also define the same notation for $Q$. Then we write

For every $y_{1}\in{\mathcal{Y}}$, let ${\mathcal{M}}^{0}_{1}|_{y_{1}}$ (resp. ${\mathcal{M}}^{1}_{1}|_{y_{1}}$) denote the interactive system ${\mathcal{M}}^{0}_{1}$ (resp. ${\mathcal{M}}_{1}^{1}$) conditioning on that it has answered $y_{1}$ to the first query (recall we have assumed that $y_{1}$ contains $x_{1}$). Formally, for every $b\in\{0,1\}$, $(x_{2},y_{2}),\dots,(x_{t},y_{t})$ and $x_{t+1}$, define

Here, we used inequalities of the form $\sum_{y}P(y)\cdot h(y)\leq\left(C\cdot\sum_{y}Q(y)\cdot h(y)^{\beta}\right)^{1/\beta}$ three times (they are (8) $\Rightarrow$ (9) $\Rightarrow$ (10) and (11) $\Rightarrow$ (12)). We use underlines to highlight the “$h$” part of each step in the deductions above.

(8) $\Rightarrow$ (9) is the most critical step. To see this, observe that knowing $y_{2}$ does not change the view of the first mechanism, because the second query is sent to the independently running mechanism ${\mathcal{M}}^{b}_{2}$. Therefore, ${\mathcal{M}}^{b}_{1}|_{y_{1}}$ remains the same after conditioning on both $y_{1}$ and $y_{2}$. Now, note that $P_{3}|_{y_{<3}}$ (resp. $Q_{3}|_{y_{<3}}$) exactly describes one round of interaction between the adversary and ${\mathcal{M}}^{0}_{1}|_{y_{1}}$ (resp. ${\mathcal{M}}^{1}_{1}|_{y_{1}}$). Consequently, the information leaked by $y_{3}$ must be subject to the bound (7) and the inequality holds. Having verified (8) $\Rightarrow$ (9), the steps (9) $\Rightarrow$ (10) and (11) $\Rightarrow$ (12) are straightforward.

Having justified (13) for every measure function $h$, we conclude that $D_{\alpha}(P\|Q)\leq e^{\varepsilon_{1}+\varepsilon_{2}}$. A symmetric argument shows that $D_{\alpha}(Q\|P)\leq e^{\varepsilon_{1}+\varepsilon_{2}}$. This completes the proof for the toy example.

Proof sketch for the general case. The proof for the general case extends the idea above with some minor twists. By induction, we only need to prove the composition theorem for the case with two mechanisms and many rounds. An issue worth noting is that $\mathcal{A}$ can choose the next query object based on previous responses. However, we can suppose without loss of generality that $\mathcal{A}$ always communicates with mechanisms alternately, by adding a vanilla query $x^{*}$ to the query space. If the current mechanism is not the one $\mathcal{A}$ wishes to speak with, $\mathcal{A}$ just sends the vanilla query $x^{*}$. The mechanism then returns a fixed response, which does not leak any information. We refer to Appendix A.2 for the detail of the proof.

Conclusion and Future Directions

In this work, we consider the concurrent composition of interactive mechanisms. Regarding the general privacy guarantee under the concurrent composition, our result gives optimal composition theorems for several popular definitions of differential privacy, including $(\varepsilon,\delta)$-DP and Rényi DP. Our work is purely theoretical, and we do not see any negative societal impacts it may cause.

For future directions, we ask whether one can use our composition theorems to design new differentially-private algorithms that may involve running several differentially-private mechanisms in parallel. It is also interesting to explore more practical implications of the concurrent composition phenomena.

We also note that there is a recent interest in fully adaptive compositions of differential privacy, which studies how the data analyst can manage the privacy budget and monitor the privacy loss themselves. In particular, the notion of privacy odometers and filters were proposed to capture these demands Rogers et al. (2016); Feldman and Zrnic (2021); Whitehouse et al. (2022); Lécuyer (2021). This question necessitates a better understanding of information leakage in an interactive environment. Our work developed several new tools and techniques to reason about interactive mechanisms. Can our technique be useful in studying fully adaptive compositions?

Acknowledgements

I am grateful to Jelani Nelson for advising this project and providing useful comments on an early draft of this paper. I would also like to thank Salil Vadhan and Wanrong Zhang for insightful discussions about their work.

X. Lyu was supported by ONR DORECG award N00014-17-1-2127.

References

Checklist

Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? [Yes]

Did you describe the limitations of your work? [Yes] We included a discussion for future directions.

Did you discuss any potential negative societal impacts of your work? [Yes]

Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]

If you are including theoretical results…

Did you state the full set of assumptions of all theoretical results? [Yes]

Did you include complete proofs of all theoretical results? [Yes] The full proofs will be available in supplementary material.

Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]

Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…

If your work uses existing assets, did you cite the creators? [N/A]

Did you mention the license of the assets? [N/A]

Did you include any new assets either in the supplemental material or as a URL? [N/A]

Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]

Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]

If you used crowdsourcing or conducted research with human subjects…

Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

Appendix A Appendix: Missing Proofs

In this appendix, we show the formal proofs for all the lemmas and claims in the main paper.

This subsection present omitted proofs in Section 4.1.

Reminder of Lemma 1. Suppose ${\mathcal{M}}^{0},{\mathcal{M}}^{1}$ are $(\varepsilon,\delta)$-indistinguishable. There are two systems ${\mathcal{E}}^{0},{\mathcal{E}}^{1}$ satisfying the following.

For every adversary $\mathcal{A}$ and $b\in\{0,1\}$, it holds that $\mathbf{IT}(\mathcal{A}:{\mathcal{M}}^{b})\geq\delta\cdot\mathbf{IT}(\mathcal{A}:{\mathcal{E}}^{b})$.

For every adversary $\mathcal{A}$, every set of transcripts $S\subseteq\{(x_{i},y_{i})_{i\in[T]}\}$ and $b\in\{0,1\}$, it holds that

Intuitively, $M^{b}((y_{i})_{i\in[t]},(x_{i})_{i\in[t]})$ is the probability of ${\mathcal{M}}^{b}$ responding $(y_{1},\dots,y_{t})$, conditioning on that the query messages are fixed to $(x_{1},\dots,x_{t})$. Note that knowing $M^{b}((y_{i})_{i\in[T]},(x_{i})_{i\in[T]})$ for every $(x_{i},y_{i})_{i\in[T]}$ uniquely determines the system.

Let $\mathcal{A}$ be an arbitrary adversary. For each $(x_{i},y_{i})_{i\in[t-1]}$ and $x_{t}$, denote

Note that $A((x_{i})_{i\in[t]},(y_{i})_{i\in[t-1]})$ is the probability of $\mathcal{A}$ sending queries $(x_{1},\dots,x_{t})$, conditioning on that the responses to the first $t-1$ queries are fixed to $(y_{1},\dots,y_{t-1})$.

In the following, we will construct two systems ${\mathcal{E}}^{0/1}$ such that, for every $(x_{i},y_{i})_{i\in[T]}$, it holds that

If we have two systems ${\mathcal{E}}^{0/1}$ satisfying the above, then we can verify that they satisfy the lemma statement by combining (16), (17) and (18).

Now we describe the construction. We start by defining for each $b\in\{0,1\}$, $t\leq T$ and every partial history $(x_{i},y_{i})_{i\leq t-1}\in({\mathcal{X}}\times{\mathcal{Y}})^{t-1}$, $x_{t}\in{\mathcal{X}}$ a control function as

For every $t\leq T-1$ and $(x_{i},y_{i})_{i\leq t}$, we also define the following control function:

We need the following two facts regarding the control functions.

For each $b\in\{0,1\}$ and $x_{1}\in{\mathcal{X}}$, it holds that $\mathsf{Lower}^{b}(\emptyset,x_{1})\leq\delta$.

We construct an adversary $\mathcal{A}^{*}$ as follows. $\mathcal{A}^{*}$ is deterministic. It always sends $x_{1}$ as the first query. For every $1\leq t\leq T-1$ and history $(x_{i},y_{i})_{i\in[t]}$, $\mathcal{A}^{*}$ computes the next query as

Given that ${\mathcal{M}}^{0}$ and ${\mathcal{M}}^{1}$ are $(\varepsilon,\delta)$-indistinguishable, we know that

On the other hand, by the definition of $\mathcal{A}^{*}$ and (19), it holds that

This can be verified by tracing how $\mathsf{Lower}^{b}(\emptyset,x_{1})$ is determined from queries $(x_{1},\dots,x_{T})$ (in the “max” operator), and noting that $\mathcal{A}^{*}$ follows exactly the same queries. Combining two equations above concludes the proof of Claim. ∎

For every $b\in\{0,1\}$, $t\leq T-1$ and $(x_{i},y_{i})_{i\leq t-1}\in({\mathcal{X}}\times{\mathcal{Y}})^{t-1},x_{t}\in{\mathcal{X}}$, it holds that

We prove this claim by downward induction on $t$. For the case $t=T-1$, we have by definition that

We justify the deductions briefly. (21) is by definition. (22) uses a simple trick that $\max\left\{a,0\right\}=a+\max\left\{-a,0\right\}$. The last step (23) is by definition again. In particular, we observe that for every $x_{T}\in{\mathcal{X}}$, it holds that

Assume the claim is true for $t+1\leq T-1$. We consider the case of $t$. We have

The first inequality is due to the induction hypothesis. The second inequality is straightforward. This completes the proof for the claim. ∎

The construction. We are ready to describe the construction. In the following, we will assume $\varepsilon>0$. Having shown the construction for every $\varepsilon>0$, the case for $\varepsilon=0$ can be argued by continuity. We will construct ${\mathcal{E}}^{0},{\mathcal{E}}^{1}$ by specifying for every $t\in[T]$ and $(x_{i},y_{i})_{i\leq t}$ the following:

Note that a valid $E^{b}(\cdot)$ uniquely defines a system ${\mathcal{E}}^{b}$. For brevity, we also define $E^{0}(\emptyset)=E^{1}(\emptyset)=1$. Intuitively, we use $\emptyset$ to denote two “empty lists” (i.e., two lists $(y_{i})_{i\leq t},(x_{i})_{i\leq t}$ with $t=0$).

We will construct $E^{b}((y_{i})_{i\leq t},(x_{i})_{i\leq t})$ for $t=1,2,\dots,T$ in order. Throughput the construction, we maintain the following property. For every $0\leq t\leq T$, $(x_{i},y_{i})_{i\leq t}$ and $b\in\{0,1\}$, we require

Meanwhile, for $E^{b}((y_{i}),(x_{i}))$ to describe a valid system, it is necessary and sufficient for it to be non-negative and satisfy the following equation for every $(x_{i},y_{i})_{i\leq t}\in({\mathcal{X}}\times{\mathcal{Y}})^{t}$ and $x_{t+1}$:

Next, we shall prove that we can construct a valid $E^{0/1}$ satisfying (24), (25) and (26). As we have said, we will construct $E^{b}$ gradually in the increasing order of $t\in[T]$. For $t=0$, we have set $E^{0}(\emptyset)=E^{1}(\emptyset)=1$. (24) holds by Claim 1, and (25) holds trivially.

Now let $t<T$. Also let $(y_{i})_{i\leq t}\in{\mathcal{Y}}^{t},(x_{i})_{i\leq t}\in{\mathcal{X}}^{t}$ be two lists. Suppose we have constructed $E^{0/1}((y_{i})_{i\leq t},(x_{i})_{i\leq t})$ that satisfies (24) and (25). For every $x_{t+1}\in{\mathcal{X}}$ and $y_{t+1}\in{\mathcal{Y}}$, we construct $E^{0/1}((y_{i})_{i\leq t+1},(x_{i})_{i\leq t+1})$ in the following.

Fix $x_{t+1}\in{\mathcal{X}}$. We temporarily set

By Claim 2, we know that $\widetilde{E}^{b}$ satisfies (25). By the construction, $\widetilde{E}^{b}$ satisfies (24). However, $\widetilde{E}^{b}$ may fail to satisfy (26). Still, we have

In the following, we show that one can adjust $\widetilde{E}^{b}$ by increasing some $\widetilde{E}^{b}((y_{i})_{i\leq t+1},(x_{i})_{i\leq t+1})$ properly, so that the new $\widetilde{E}^{b}$ satisfies all of (24), (25) and (26).

To begin with, we define for each $b\in\{0,1\}$ the quantity

Intuitively, $\widetilde{E}^{b}$ being tight at $y_{t+1}$ means that we cannot increase $\widetilde{E}^{b}((y_{i})_{i\leq t+1},(x_{i})_{i\leq t+1})$ without increasing $\widetilde{E}^{1-b}((y_{i})_{i\leq t+1},(x_{i})_{i\leq t+1})$.

Here shows our adjustment strategy. We consider each $y_{t+1}\in{\mathcal{Y}}$ in an arbitrary but fixed order. For each $y_{t+1}$, we gradually increase $\widetilde{E}^{0/1}((y_{i})_{i\leq t+1},(x_{i})_{i\leq t+1})$ until one of the following events happens.

Both $\widetilde{E}^{0}$ and $\widetilde{E}^{1}$ get tight at $y_{t+1}$.

Having proven the claim, we know there is a way to adjust $\widetilde{E}^{0/1}$ so that they satisfy all of (24), (25), (26). We then set $E^{0/1}((y_{i})_{i\leq t+1},(x_{i})_{i\leq t+1})$ to be $\widetilde{E}^{0/1}((y_{i})_{i\leq t+1},(x_{i})_{i\leq t+1})$ and finish the construction for $(x_{i},y_{i})_{i\leq t}$ and $x_{t+1}$.

We use the construction above for $t=0,1,\dots,T-1$ in order to construct $E^{0/1}$. It remains to verify that $E^{0/1}$ satisfies the lemma statement. It suffices to verify for every $(x_{i},y_{i})_{i\leq T}\in({\mathcal{X}}\times{\mathcal{Y}})^{T}$ and $b\in\{0,1\}$ that

In fact, since $e^{\varepsilon}>1$, it suffices to verify the second inequality for $b\in\{0,1\}$. This can be verified by utilizing (25): note that $\mathsf{Upper}^{b}((x_{i},y_{i})_{i\leq T})=M^{b}((y_{i}),(x_{i}))-e^{-\varepsilon}M^{1-b}((y_{i}),(x_{i}))$, and (25) tells us that

Re-arranging proves the desired inequality. ∎

Note that to verify the correctness of $E^{0/1}$, we only used the condition (25). It seems that (24) is useless in this proof. However, note that it is possible that $\mathsf{Upper}^{b}((y_{i}),(x_{i}))$ is negative for some $(x_{i},y_{i})_{i\leq t}$, which makes it unclear whether (25) can always be satisfied by a positive valuation of $E$. This is why we need the other control function $\mathsf{Lower}$.

A.1.2 Wrap-up

Reminder of Lemma 2. Suppose ${\mathcal{M}},{\mathcal{E}}$ are two systems such that for every adversary $\mathcal{A}$, it holds that $\mathbf{IT}(\mathcal{A}:{\mathcal{M}})\geq\delta\mathbf{IT}(\mathcal{A}:{\mathcal{E}})$. Then there is a system ${\mathcal{N}}$ such that for every adversary $\mathcal{A}$, it holds that

We follow the notation in Section A.1.1. Namely, for each $(x_{i},y_{i})_{i\leq t}$, define

Also define the same notation for $E$. Then we construct

Since ${\mathcal{M}}\geq\delta{\mathcal{E}}$, we know that $N((y_{i}),(x_{i}))$ is always non-negative. Moreover, $N$ encodes a valid system because

Finally, it is easy to verify $\mathbf{IT}(\mathcal{A}:{\mathcal{M}})\equiv\delta\mathbf{IT}(\mathcal{A}:{\mathcal{E}})+(1-\delta)\mathbf{IT}(\mathcal{A}:{\mathcal{M}})$. ∎

As we have shown in Section 4.1, combining Lemma 1, 2 and 3 together, we can prove Theorem 3 easily. Next, we show how Theorem 3 implies Theorem 1.

Let ${\mathcal{M}}_{1},\dots,{\mathcal{M}}_{k}$ be $k$ mechanisms, where ${\mathcal{M}}_{i}$ is $(\varepsilon_{i},\delta_{i})$-approximate differentially private. We assume without loss of generality that all of ${\mathcal{M}}_{i}$’s hold a bit $b\in\{0,1\}$ as the sensitive data.

We also prepare the decomposition of ${\mathcal{M}}_{i}^{0/1}$ with ${\mathcal{N}}_{i}^{0/1},{\mathcal{E}}_{i}^{0/1}$ as promised by Theorem 3.

To see this, for each ${\mathcal{M}}^{b}_{i}$, consider a two-party communication, where one party is ${\mathcal{M}}^{b}_{i}$, and the other party consists of $\mathcal{A}$ and ${\mathcal{M}}^{b}_{j}$ for $j\neq i$. The second party simulates all the interactions between $\mathcal{A}$ and ${\mathcal{M}}^{b}_{j}$, and only sends queries to ${\mathcal{M}}^{b}_{i}$ when $\mathcal{A}$ queries ${\mathcal{M}}^{b}_{i}$. From the second party’s viewpoint, ${\mathcal{M}}^{b}_{i}$ looks identical to $\delta_{i}{\mathcal{E}}_{i}^{b}+(1-\delta_{i})\frac{e^{\varepsilon}}{1+e^{\varepsilon}}{\mathcal{N}}_{i}^{b}+(1-\delta_{i})\frac{1}{1+e^{\varepsilon}}{\mathcal{N}}_{i}^{1-b}$. Therefore,

Here, we use $(p_{1},p_{2},p_{3})=(\delta_{i},(1-\delta_{i})\frac{e^{\varepsilon}}{1+e^{\varepsilon}},(1-\delta_{i})\frac{1}{1+e^{\varepsilon}})$ and $({\mathcal{M}}^{b}_{i,1},{\mathcal{M}}^{b}_{i,2},{\mathcal{M}}^{b}_{i,3})=({\mathcal{E}}_{i}^{b},{\mathcal{N}}_{i}^{b},{\mathcal{N}}_{i}^{1-b})$ for convenience. Applying this decomposition for every $i\in[k]$ proves (28).

Finally, note that $\mathbf{Output}(\mathcal{S},b)$ is just a post-processing of the sequential composition of $k$ (approximate) randomized response mechanisms. Hence, the optimal sequential composition theorem holds for $\mathbf{Output}(\mathcal{S},b)$, which completes the proof. ∎

A.2 Proofs for Rényi Differential Privacy

In this section, we show omitted proofs for Theorem 2.

We need some technical preparations first. Consider a measure space $(X,\mu)$. For two measurable functions $f,g$, define their inner product as

Recall Hölder’s inequality, which is essential for our proof.

Suppose $\alpha,\beta\geq 1$ are Hólder conjugates of each other (i.e., $\frac{1}{\alpha}+\frac{1}{\beta}=1$). Suppose $f,g$ are two measurable functions. Then we have

The inequality is sharp in the sense that for every measurable function $f$, we have

A.2.2 Proof for lemmas

We are ready to show the proofs now. We start with Lemma 4.

Reminder of Lemma 4. Suppose $P,Q$ are two distributions supported on ${\mathcal{Y}}$. For every $\alpha>1$ and $B\geq 0$, let $\beta=\frac{\alpha}{\alpha-1}$ be the Hölder conjugate of $\alpha$. The following statements are equivalent.

We write $P(y),Q(y)$ as shorthands for $\Pr[P=y]$ and $\Pr[Q=y]$ for brevity. Now, note that $D_{\alpha}(P\|Q)\leq B$ is equivalent to $e^{D_{\alpha}(P\|Q)}\leq e^{B}$, which is further equivalent to

Consider the measure space $M=({\mathcal{Y}},Q)$. By Holder’s inequality, we have

Moreover, since $\frac{P(y)}{Q(y)}$ is non-negative, it suffices to consider only non-negative $h$ in the supremum above. Now we are ready to verify the equivalence.

On the other hand, if Condition $2$ holds, we have

Let $\beta\geq 1,B\geq 0$ be two reals. For each $y_{1}\in{\mathcal{Y}}_{1}$, define

A.2.3 Proof of the composition theorem

We prove the following theorem, which is equivalent to Theorem 2.

Let ${\mathcal{Y}},{\mathcal{Z}}$ denote the response domains of ${\mathcal{M}}_{1},{\mathcal{M}}_{2}$ respectively. Also let $y_{1},\dots,y_{T}$, $z_{1},\dots,z_{T}$ denote the lists of responses returned by ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$ respectively. We assume that each response $y_{i},z_{j}$ contains a copy of the corresponding query message (so that we can recover the whole interaction history just from the responses).

Now, fix $\mathcal{A}$ to be an arbitrary adversary. Let $P,Q\in\Delta(({\mathcal{Y}}\times{\mathcal{Z}})^{T})$ denote the output distributions when $\mathcal{A}$ interacts with $({\mathcal{M}}^{0}_{1},{\mathcal{M}}^{0}_{2})$ and $({\mathcal{M}}^{1}_{1},{\mathcal{M}}^{1}_{2})$ respectively. Our goal is to prove that

We bound $D_{\alpha}(P\|Q)$ below. The bound for $D_{\alpha}(Q\|P)$ is symmetric.

where $\beta=\frac{\alpha}{\alpha-1}$ is the Hölder conjugate of $\alpha$.

For each $i\in[T]$, let $P^{y}_{i},P^{z}_{i}$ be the projection of $P$ onto $y_{i},z_{i}$. For each $i\in[T]$, let $y_{\leq i},z_{\leq i}$ denote the first $i$ responses from $y$ and $z$. Denote $(yz)_{\leq i}=(y_{1},z_{1},\dots,y_{i},z_{i})$. Then, let $P^{y}_{i}|_{yz_{<i}}$ denote the distribution of $y_{i}$ conditioning on $(yz)_{<i}$, and $P^{z}_{i}|_{yz_{<i},y_{i}}$ denote the distribution of $z_{i}$ conditioning on $(yz)_{<i}$ and $y_{i}$. Also define the same notation for $Q$. Then we write

For every $t<T$ and every $y_{\leq t}$, let ${\mathcal{M}}^{0}_{1}|_{y_{\leq t}}$ (resp. ${\mathcal{M}}^{1}_{1}|_{y_{\leq t}}$) denote the interactive system ${\mathcal{M}}^{0}_{1}$ (resp. ${\mathcal{M}}^{1}_{1}$) conditioning on that it has answered $y_{1},\dots,y_{t}$ to the first $t$ queries. Formally, for every $(x_{t+1},y_{t+1}),\dots,(x_{t^{\prime}},y_{t^{\prime}})$ and $x_{t^{\prime}+1}$, define

We also define the same notation for the second mechanism ${\mathcal{M}}_{2}$. Next, define

A symmetric conclusion holds for $P^{z}$ and $z$. Namely

Turning back to (31), we first deduce that

So far we haven’t utilized Claim 3 yet. Denote

Applying Claim 3 on (34) for $P^{z}_{T-1}$ yields that

We proceed to apply Claim 3 on (35) for $P^{y}_{T-1},P^{z}_{T-2},P^{y}_{T-2}\dots,P^{z}_{1},P^{y}_{1}$ in order. We can get

This shows that $P\preceq e^{\varepsilon_{1}+\varepsilon_{2}}Q$, which consequently implies that $D_{\alpha}(P\|Q)\leq\varepsilon_{1}+\varepsilon_{2}$. Similarly, we can bound $D_{\alpha}(Q\|P)\leq\varepsilon_{1}+\varepsilon_{2}$. Combining two bounds together completes the proof. ∎

A.3 Proof for Concentrated DP

In this section, we prove Corollary 1. We recall the definition of zero-concentrated DP and truncated concentrated DP.

Let $\rho>0$ be a real and ${\mathcal{M}}$ be a mechanism. ${\mathcal{M}}$ is called $\rho$-zero-concentrated DP (or $\rho$-zCDP for short), if for every $\alpha\in(1,+\infty)$, ${\mathcal{M}}$ is $(\alpha,\alpha\cdot\rho)$-RDP.

Let $\rho>0,\omega>1$ be two reals, and ${\mathcal{M}}$ be a mechanism. ${\mathcal{M}}$ is called $(\rho,\omega)$-truncated DP (or $(\rho,\omega)$-tCDP), if for every $\alpha\in(1,\omega)$, ${\mathcal{M}}$ is $(\alpha,\alpha\cdot\rho)$-RDP.

Appendix B A Motivating Example of Concurrent Composition

To demonstrate the power of concurrent composition, in this section, we use Theorem 1 to analyze a simple private “Guess-and-Check” algorithm. We remark that this is a rather preliminary application: the weaker concurrent composition theorem by Vadhan and Wang is sufficient to do the job. However, the main purpose of this section is to highlight the importance of concurrent composition, and hopefully inspire researchers to design more sophisticated algorithms.

Discussions. Algorithm 1 is parameterized by an error tolerance parameter $E>0$ and two privacy parameters $c\geq 1,\varepsilon\in(0,1)$. Roughly speaking, it can process queries until identifying at least $c$ queries whose guesses deviate from the true value by at least (roughly) $E$. It works by (concurrently) composing a variant of the sparse vector technique by Lyu et al. with the standard Laplace noise-adding mechanism.

The main advantage of the Lyu et al. SVT is that it only adds noise to the threshold once (Line 2 of algorithm 1), using a much smaller noise, which makes the SVT algorithm more accurate. Since the utility guarantee of the algorithm is not the focus of this work, we omit more discussions here and refer interested readers to [Lyu et al., 2017, Zhu and Wang, 2020] for more detail.

We consider the privacy guarantee of Algorithm 1. In fact, without the concurrent composition framework, it is not clear whether or not Algorithm 1 is really private! If we replace Line 7 of the algorithm by $v_{i}\leftarrow 0$, then the algorithm is indeed $(3\varepsilon,0)$-private, because it is just a faithful implementation of the Lyu et al. SVT. However, in Algorithm 1, the algorithm reports a correct estimation $v_{i}$ for each inaccurate guess, which implies that the future query to the algorithm may depend on $v_{i}$, and thus on the private data set $X$. In this case, the original analysis from [Lyu et al., 2017] does not hold anymore.

Analyzing the privacy. While it is not hard to prove the privacy property of Algorithm 1 by examining the proof of Lyu et al. carefully and applying some modifications, here we show that Algorithm 1 admits a fairly straightforward privacy proof under the concurrent composition framework, using the privacy theorem by Lyu et al. as a black box. We do the analysis now. First, we have the following lemma from [Lyu et al., 2017].

Consider replacing Line 7 of Algorithm 1 with $v_{i}\leftarrow 0$. The resulting algorithm is $(3\varepsilon,0)$-DP.

Combining Lemmas 6 and 7 under the concurrent composition framework directly yields the following result.

Finally, we remark that a similar private “Guess-and-Check” algorithm was also proposed and analyzed by Zhu and Wang , where the authors also considered using a version of SVT without refreshing the threshold after answering each “meaningful” query. Therefore, their algorithm is also subject to the concurrent composition issue, which seems to be overlooked in the original analysis of Zhu and Wang . Since they were working with Rényi DP, our Theorem 2 provides a remedy to this issue easily.