Composition Theorems for Interactive Differential Privacy
Authors: Xin Lyu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
Composition Theorems
Interactive mechanism

Abstract: 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, Renyi 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.

Composition Theorems for Interactive Differential Privacy
Xin Lyu
Department of Electrical Engineering and Computer Science University of California, Berkeley Berkeley, CA, 94720 xinlyu@ berkeley.edu
Abstract
An interactive mechanism is an algorithm that stores data set and answers adap- tively chosen queries to it. The mechanism is called differentially private, if any adversary cannot distinguish whether 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, adversary interacts with k interactive mechanisms parallel and can interleave its queries to the mechanisms arbitrarily. Previously, Vadhan and Wang [2021] proved optimal concurrent composition theorem for pure-differential privacy. We significantly generalize and extend their results. Namely, prove optimal parallel composition properties for several major notions of differential privacy in the literature, including approxi- mate 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 a feature that differential privacy grants us for free.
Concurrently and independently of our work, Vadhan and Zhang [2022] proved optimal concurrent composition theorem for f-DP [Dong et al., 2022], which implies our result for the approximate DP case.
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 [201 7]).
Let M be algorithm that runs on data set x and calculates some information about it. Roughly speaking, M is called differentially private, if the output distribution of AA remains nearly identical when we arbitrarily modify single entry in a..
One essential feature of differential privacy is its composability. Composition captures the scenario where a data analyst runs & differentially private algorithms sequentially, and releases the results afterward. Typically, a composition theorem has the following form: if each of the 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 privacy loss. In this case, composition theorems reveal how the privacy guarantee degrades over time. More importantly, composition theorems allow us build more complex and powerful differentially-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

private algorithms from simple primitives, and argue the privacy guarantee of the combined algorithm 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 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 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. sequential composition theorem completely fails to capture this scenario. Also, in practice, deployments of DP algorithms often demand 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- cerc-connettrated DP and truncated concentrated DP.
1.1 Setup
Before we continue, set up necessary pieces of notation. We use X' and Y to denote the domain of query messages and responses, respectively. We assume that both X' and 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 set S, denote by A(S) the set of all possible distributions supported over S. We define interactive systems below.
Definition (Interactive system), An interactive system is a (randomized) algorithm M: (Xx))) x X' + A()). The input to M is an interaction history (I1, 31), (22, V2)...., (Iz, ve) E (X' x ) together with a query Tz-1- The output of M is denoted by yc-1 ~ M( ythiett It+1).
A technicality worth mentioning is that due to the internal memory and randomness of an interactive system M, the response of M to the (t + 1)-th query might be correlated with its responses to previous queries. Although the internal randomness of M is not explicitly stated as parameter, Definiton captures this correlation by requiring that each query #++1 to M is attached with the interaction history (#1, V1)..... (I2, This history is sufficient for determining the conditional distribution of the response M((I;, M:)velq 11+1) without specifying the internal randomness and memory.
We make a distinction between mechanisms and systems. By "mechanism" mean differentially private algorithm MM that holds sensitive input d and answers queries about it. When applied to a concrete input d, M induces an interactive system, denoted by Md. According to the definition of differential privacy, studying the privacy of a mechanism boils down to studying the pair of systems (Md, Md ) induced by running M on every pair of neighboring inputs (d, d'). For brevity, we usually assume W.L.O.G. that the input only consists of a single bit E (0, 1}, and we compare the induced by .M.
two systems
Concurrent composition. We define concurrent composition of interactive systems. Suppose Mi. M1.M,....,NN are k systems. The concurrent composition of them is an interactive system COMP (M1 ... MR) with query domain [k] X' and response domain V. An adversary is (possibly randomized) query algorithm A: ([k) x X' x - + A[K]] x X).. The interaction between A and COMP(M is a stochastic process that runs as follows. A first! computes a pair (i,, 21) E [R] X, sends a query 21 to Mi, and gets the response y1. In the t-th step, A calculates the next pair (ic, 222) based on the history, sends the t-th query 24 to M, and receives yt. There is no communication or
We assume it is always the adversary who sends the first message. This is without loss of generality: we can let the first message sent from the adversary to each system be an "Initiliazation" query. Having received the initialization query, the system returns either starting message or simply a "SUCCESS" symbol.

---

interaction between the interactive systems. Each system M, can only see its own interaction with A. Let IT(A: ,,,...,,MM denote the random variable recording the transcript of the interaction.
In the special case k = 1, there is only one system M and the adversary is interacting with it. We define approximate differential privacy for interactive mechanisms in this case.
Definition 2 (Indisinguishabbiity and (s, OD-)), Two interactive systems M .M' .M.MM' are called (s, 6)- indistinguishable if for every b E {0, 1}. every adversary and every collection of transcripts S S ((r, ))) , it holds that
Pr[IT((: M³) S] S ef Pr[IT(A:
+
Let M be an interactive mechanism. M is called (E, appproxmmme differentially private (or (e, 0)- for short), if for every two neighboring data sets d and d', the systems M and M are (e, (c,6)-ina indistingguisaabl..
1.2 Differential Privacy in Concurrent Compositions
We study the privacy guarantee under concurrent compositions. Let M .,....,, Mf. be k interactive mechanisms, each satisfying (s, 6--D. Consider their concurrent composition COMP ... M.). We want find the smallest parameters e', 8' such that COMP(M;) satisfies (=',8')_DP, In the sequential composition, the adversary A interacts with M,'s 's in order and cannot interlcave its queries. In this case, is known by the advanced composition theorem [Dwork et al., 2010] that IT(A: Mi))
M ................................ MQ) and IT .M!....M.). are (O( log(1/8) (1)))))) kö -iidissiinuuishabl..
However, in general, the adversary can interleave its queries arbitrarily, and the differential privacy guarantee warranted by COMP(M:) is less clear. Vadhan and Wang [2021] study this question. They showed that in the special case = O, an optimal composition holds for (M,) That if we can prove an (E', upper bound on the privacy parameter for sequential compositions of M M MY. then the concurrent composition (MMP(M)) also enjoys the same (d
the first formally
Vadhan and Wang [2021] also considered the case 5 >> 0 (i.e., approximate DP). However, for this case, they only showed an upper bound on E', 8' that is inferior to the basic composition in the sequential setting. It was asked as 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. 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 fDDP [Dong et al., 2022] etc. Compared with the standard notion of (c, -appooixie DP, these variants of DP either allow for simplified analysis of private algorithms or give sharper bounds of privacy guarantee. In the sequential composition, the composition property 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 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 they do in the sequential composition.
Approximate differential privacy. () is arguably the most widely studied notion of differ- ential privacy and is deemed the "standard" definition of DP. As our first main result, we show an optimal concurrent composition theorem for approximate DP.
Theorem 1.
Let Mi...., Mr be k interactive mechanisms that that each mechanism M, satisfies (E,, d Then COMP(M (M....M;) is (E', .8) 8'D-DP, where e', 8 given by the optimal (sequential) composition theorem [Kairouz et al., 2015, Murtagh and Vadhan, 2018].
the same data set. Suppose
In particular, when the privacy parameter for each mechanism is the same (c, 8), their concurrent composition satisfies Olyk log(1//))) + -DP for all 8' e (0, 1).
3

---

Rényi differential privacy. Rényi differential privacy was first defined by Mironov [2017]. We recall its definition.
Definition& 3 (Rényi divergence and differential privacy). Let P.Q be two distributions supported over X. For each
1, define the Rényi divergence of order a of P from Q as
(a(l)) =
log
E z>P
Two interactive systems are called (a, Ré-éé close, if for every adversary A and every E (0,1), it holds that
Dr (IT((A:: M :M-")) S.
Let M be mechanism. MM is called (a, ('-nyi differentially private (or (a, RD-D for short), if for every two neighboring data sets and d', the systems M and M are (ax, e)-Réy close.
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 Mi,Ma are (a, and (2,,e))RDPP respectively, then the composition of Mi and M2 is (a + R2)-DDP. Our next theorem generalizes this result to the concurrent composition setting.
Theorem 2. Let Mi,..., My be k interactive mechanisms that run on the same data set, Suppose that each mechanism M; is (o,, --D... Then COMP(M is Ek E
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 the full version of the paper.
Corollary 1. Let
are k interactive mechanisms that on the same data set. Suppose that each mechanism M; is TJ-DCDP (resp. (Pt,W))ICPP) Then COMP(M,... MM... is (E 9))- zCDP (resp. (Ex Pt, WCDW)))
Theorem 1, 2 and Corollary provide compelling evidence that the adversary gains no advantage by interleaving its queries to independently running mechanisms. Consequently, interactivity can be viewed as 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 optimal concurrent composition theorem for f-DP [Dong al., 2022]. By the standard connection, their result implies the optimal concurrent composition theorem for approximate DP. However, techniques very different than theirs. Their result is stronger, it is known that approxiamte-DD 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 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).
3 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 e > 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, 7 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 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 any algorithm. and argue the privacy guarantee of the whole computation by black-box applying Theorems 1 and (depending on whether we are working with (a, 6)DP or RDP). To illustrate the idea, in the full version of the paper, we apply Theorem to analyze a simple algorithm: private "Guess-and 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 data center that holds the private information of individuals and offers data analysts access to the database (interactively and iiieerentially-rivvaeehle Without knowing the concurrent composition theorem, it might be possible that some & 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 (e. 8)-DP amount of privacy "quota". Then, even if they collude and spend their privacy budget in whatever way, their computation result is still (O(vk) /k log( (1)8'))), k5 8DD with respect to the private database.
4 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 reduction the sequential composition of l (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 real vy > we say that P 11, if for every S C X, it holds that
Pr (r E S] n Pr E S). Z>P
Furthermore, we say P = Q if P and Q are identically distributed.
4.1 Approximate Differential Privacy
To prove Theorem 1, we follow the approach by Vadhan and Wang [2021], where they showed that one can simulate two (e, -)-inniisinguuihable interactive systems by post-processing randomized response mechanism. This simulation enables them to reduce the concurrent composition to sequential composition, and the optimal composition theorem follows. 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 M .M' be the pair of systems by running the private mechanism on a pair of neighboring data sets. The adversary A interacts with M for some b E {0, 1) and wants to find out the value of An intuitive yet delicate fact due to Vadhan and Wang [2021] is that, if MD and M are (e, D--iidiittinuuisablee, then there exist two systems N WV such that, for every adversary A,
the distribution of IT Md) is identical to + ITA: A/8) Tम (T :\--b). This enables one to simulate the many-round interaction between A and M by running a one-round randomized response mechanism.
5

---

In more detail, let RRA denote the standard randomized response mechanism, defined as follows. RR only accepts one query. On the query, RR ignores the query message, returns b with probability Ife and returns 1 - b otherwise. We modify A to new adversary A': A'' first sends a query to RR and receives a bit b' Then A' simulates the interaction between A and N and outputs the transcript (i.e., (AAA= -N )). Let Output(A's RRR) denote the output distribution of A' when interacting with RR. It is clear that
e² I+E
1 l
Output(A' RR
IT(A:A")
IT(A: = M*).
Therefore, A' simulates the interaction between A, MM faithfully, by a single query to RR
Now, suppose the adversary A is interacting with k mechanisms .i...., MY. in parallel. For each i E [k]. assuming that Mn and M; are (e,, 0)-inddisinguuihable there is a decomposition of MP. MM by some NP and AA. Again, we modify A new mechanism A''. A'' first queries Byg- RR e, E [k] in order, and receives & bits by....,,yy Then A' simulates the interaction between. A
and (Nr)) sejK and outputs the transcript. One can show that
Output(A': "RR IT(A: M
MD).
Note that the left hand side of (2) can be simulated by sequential composition of k randomized response mechanisms. Invoking the optimal composition theorem for sequential composition [Kairouz et al., 2015, Murtagh and Vadhan, 2018) 8] concludes the proof.
Extension to approximate DP. Now, if M and M are (e, iidistiitnine with 5 > 0, there might not be a nice decomposition of M into e' - + - Still, it is plausible to conjecture that there is decomposition of M M² with four systems No, "",,,,, 0 EL such that for each & E {0, 1}.
M = 88 + +(1+ (1) (1) c (1 12
Our main technical result in this subsection proves the existence of such decomposition.
Theorem 3. Two systems M t are (s, -iidissttinngiillll if and only if there are four systems
No ",,N,, _ Ed satisfying the following: for every adversary A and E {0, 1}, holds that
IT IT(A: = AIT(A:E)) (1 + ( e
+ (1T 1+E IT(A:N
1 1+e IT(A:13-))) (4)
Theorem implies Theorem by similar reduction to (approximate) random response. For the full proof, see the full version of the paper.
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 the full version of the paper.
are (E, Lemma 1. Suppose (nn. dibissiiiiisi There two systems E", satisfying the following.
For every adversary A and E {0, 1}, holds that IT M²) 2 8- I.((:AA: : E¹)
For every adversary A. every set of transcripts S {(1,, M)emm and b {0, 1), it holds that
Pr[IT(A: M E S] - P:(T 8 E S]
e (Pr[IT(A:
E S] (r(IT(A: E
Roughly, Lemma says that there are two systems 8 gd that capture the low-probability "bad behavior" of M It is the primary technical contribution of this subsection. We prove Lemma I by explicitly constructing the two systems E gl. That is, we specify the probability density functions Pr[E" (2z), 24) y.] for E" Ed step by step. in the increasing order of i = 1,2....,

---

Lemma 2. Suppose M. E are two systems such that for every adversary A, it holds that IT (AA: M) 2 (IT(A:E) Then there system N such that for every adversary A, holds that
IT(A: M) = (IT((: (1- (1)))
For intuition, suppose P. are two distributions such that P 2 8Q. Then one easily find distribution Q' such that P 5Q (1 ö)Q'. The proof of Lemma 2 extends this simple idea. Lemma (Vadhan and Wang [2021]). Suppose No ,N' are (s, (E.D)-indisiinnuishhblle Then there are two systems A .NV such that for every adversary A, it holds that
e IT(A:N") 1+ IT(A:AUL-'',
1
IT(A:N*)
1+e e
Wrap-up. We can conclude the proof for Theorem now. The "if" direction is obvious: the existence of decomposition satisfying (4) implies that M MM are (s, ( (id-))nnditinuuihaabbe For the other direction, we start by constructing 8" ", using Lemma 1. Then we construct A . by Lemma 2. Lemma and together ensure that A and A1 are (e, 00--iinnistinguuihhabe which enables us invoke Lemma 3 and decompose Ao ! into A .NV', (E "P.EE,,"" '','"' ,A'') forms the final decomposition. It is straightforward to verify that they satisfy (4).
4.2 Rényi Differential Privacy
Our result for Rényi differential privacy (Theorem 2) takes a completely different approach.
An intuition. Let M1 be an (a, Ré-ééy DP mechanism. Intuitively, (a. Ré-Rén DP means that Mi has unit of privacy budget and can distribute it to T queries. Viewing the privacy budget as form of "deposit", we hope to argue that two or more independently running mechanisms spend their deposit independently, and adversary cannot trigger any mechanism spend more privacy budget than it holds by interacting with other mechanisms.
intuitive and easy-to-measure resources such time and energy, the notion of privacy loss looks somewhat illusive. Even worse, we need to reason about this clusive resource in stochastic process consisting interactions with multiple systems. It not clear how one can quantify the privacy loss in such an interactive and complex process. Nonetheless, we manage to find new approach do
However, unlike
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
Lemma 4 (An alternative characterization of Rényi divergence). Suppose P. Q are two distributions supported over y. For every a > 1 and B 2 0, let a following statements are equivalent.
be the Hölder conjugate of a. The
Da((Pl)) < B.
For every function
R220 it holds that By-p(h(y)]
Ey-o@h(y)))114
Note that if we let a - xc, then Lemma 4 converges to characterization of pure-DP. That is, Dao QPI < and only Pr[P = y] < B Pr(Q = y] for every y E 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 find a way track the privacy loss.
Measure theory setup. Before we continue, it would be more convenient to switch to a measure- theoretic language. Consider two measures P. Q space (P and Q are not necessarily probability measures), we say that P is 3-dominated by Q. denoted by P Σg Q, if for every measurable function f: 20 it holds that
|f = / f(0)dP()) (frOP(R())
1/8
= =Iflle..
7

---

When y is finite set, the integral coincides with an equivalent summation. i.e.,
/ (())dp()> Σ P(v)f(y)
We will use integral and summation interchangeably.
In this notation, Lemma 4 can be equivalently stated as (a(P)) I if and only if P 8- dominated by e Q for 3 = a-1
The following lemma is essential for us.
Lemma 5. Let V1 222 be space. Consider distributions P, Vi x V22 Assume supp P) supp(Q) = = xY2. Let P1, P2 be the margin of P on V1, For each E V1, denote by P21Pi=y: the marginal distribution of y2 conditioning on y1. Also define the same notation for Q.
Let B 2 1, 2 0 be two reals. Let 3 T-T-
For each E 33,, define
(1(11) inf Pal: 3s K Q2lei=m
Suppose P 3g Q. Consider the measure spaces (V1, Pi (1n) (1 and (2). We have
P/ 33 e eQi
Intuitively, the function f(y1) serves as the role of "privacy budget monitor". To see this, an adversary A and think of (v1, 3/2 as the responses of the system the adversary?. After observing Y1, the adversary wants to distinguish between two conditional distributions P: and Q2 Q.=w At this moment, ((11) shows up an upper bound of "extra information" that the adversary can extract by utilizing their second query. Alternatively, E(y1) quantifies the amount of the remaining privacy budget the mechanism has after outputting 1/1 On average, the function & (111) provides fine-grained control of the privacy loss in the sense that P/ 3 Q1.
Proof for 3-round toy example. We are ready to describe the proof for Theorem 2. To illustrate the idea, we prove toy case here and defer the full proof the full version of the paper. The proof for the toy case includes all the important ideas. Extending it to full proof is straightforward.
We describe the toy scenario now. Suppose there are mechanisms M1 that run on sensitive input bit & E (0, 1). The interaction consists of 3 rounds. The adversary A communicates with M2, MM order, and outputs the response (3/1 3/2 y3). For brevity, we assume that each response Y/ contains copy of the query message Tú, so that we recover the whole transcript ((z1, M1), (I2, 82), (23, ya)) only from the responses.
Let P.Q E A(Y x y x y) be the output distribution when A interacts with (M,. and My), respectively. Suppose M1, M2 are (a, (a,ez)-Rény) DP respectively. Our goal is to prove that
max (DI())))) (QI
+
We bound Da below. The bound for Da PQ is symmetric. Be Lemma 4, it suffices to show that for every h x y y R20 that
1/8
Σ
P(y)h()) <
ccite2
Σ
Qu))((y))
(5)
V= u2.
(V
where 8 a-I is the Hölder conjugate of Let Pt,Ps Pa be the projection of P onto the three rounds, and let Pilyer denote the distribution of ys conditioning on y1..... ... V--1- Also define the same notation for Q. Then we write
(((())) Σ
Σ Pslves (ws) )) 98
Σ
P(y)h(y) = Σ (1
Pelpx
(6)
y= y= B2-33))
Ma
"Although the query made by A not explicitly recorded, the pair (31, y2) can capture this information by requiring that each response ys must be attached with the query message n.. This does not leak any additional information because 2; is solely chosen by A.
8

---

For every 91 E y. let Miln, (resp. Milg, denote the interactive system M (resp. Mi) condi- tioning on that has answered y1 the first query (recall we have assumed that y1 contains xT). Formally, for every b E {0,1}, 1), (22, (2), (Te, Ue) and 21+1, define
Milu ((z), Uilasss = (i (i)sss
Next, define
(1())) exp
sup Atadversary
DD (IT Mil, :M)ll())))))))))
From Lemma 5, one can show that Pie 2//3-0
1 e0i Turning back to (5), we then have
Σ
(1 Σ
Palvi (82)
Σ
Palueo (vs)
(8)
21
82
1/8
Σ
Pi( Σ
((((1))
Voluca (vllva(uaa)h (va)
(9)
393
1/8)
< Σ
Pi(in)
Σ
Q2lun (w2)
Σ
Qslvca (V)))
(10)
1/0
Σ
(1)1))
Σ
Q2lur (122
Σ
Qalvess (1s))((
(11)
322
us
Qalucs (1s) ()))())))))))))))))
1/8
eattr Σ
Qi(y1) Σ
Q2lun (1/2)
Σ
(12)
21
82
1/8
e Σ Q())((y))
(13)
M(v)a) three times (they are (8) + (9) - (10) and (11) - (12)). We use underlines to highlight the "h" part of each step in the deductions above.
Here, we used inequalities of the form Eg P(y) MV) s E, ewv)
(8) + (9) the most critical step. 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 M Therefore, M remains the same after conditioning on both yı and y2- Now, note that P3 Palves (resp.
Qolucca) exactly describes one round of interaction between the adversary and M l9 (resp. M Consequently, the information leaked by ys must be subject to the bound (7) and the inequality holds. Having verified (8) = (9), the steps (9) = (10) and (11)= = (12) are straightforward.
Having justified (13) for every symmetric argument shows that (Q) I t This completes the proof for the toy example.
function h, conclude that (all)) S efits, A
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 A can choose the next query object based on previous responses. However, we can suppose without loss of generality that A always communicates with mechanisms alternately, by adding vanilla query x to the query space. If the current mechanism not the one wishes speak with, A just sends the vanilla query x². The mechanism then returns fixed response, which does not leak any information.
5 Conclusion and Future Directions
In this work, we consider the concurrent composition of interactive mechanisms. Regarding the general privacy guarantee under the concurrent composition, result gives optimal composition

---

11118///6611166466 theorems for several popular definitions of differential privacy. including (e, 6)-P 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 cefferentialll-privaat algorithms that may involve running several differentially-priinn 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 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 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
Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput., 50(3), 2021. doi: (0.1137/6MM100344 URL http:::/ddoi..rg/////
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography 14th Interna- tional Conference, TCC 2016-B, Beijing, China, October 31 November 3, 2016, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 635-658, 2016. doi: 10.1007/ 978-3-662-53641-44 24. URL https::/tteetc httpp:://doi.rrtee 10.
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 46. ACM, 2018. doi: 10.1 10.1145/3188745 3188946. URL https::t//// http:/doo..ooo org/ 10. 1145 1145/3188744 3388/388888854488 3188946.
Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series (Statistical Methodology), 84, 2022.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found.
Trends Theor. Compur. Sci., 9(3-4):211-44) 107407, 2014. doi: 10.156 /0400000042. URL https: //doi.org/10/ wtt.://./................. 1561/04000000042.
Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/1603.01187,
2016. http://////axi org/ att/a/aa//1100 01887.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Serge Vaudenay, editor, Advances in Cryptology- EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg. Russia, May 28 June 1, 2006, Proceed- ings, volume 4004 of Lecture Notes in Computer Science, pages 486-503 Springer, 2006a. doi: 10.1007/1 17616791_121 29. URL https::/ddot org/ 10. 1007 01t0//11166699900
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings.
10

---

volume 3876 of Lecture Notes in Computer Science, pages 265-284 Springer, 2006b. doi: 10.1007/116818788 14. URL httpp::/ddoo.rgg//// 111111000011111188111
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009, pages 381 881-390. ACM, 2009, URL https:tp////. //tw///oiii.oo wtwpiioorg//// 10. 1145/1536414 1536467.
doi: 10.1 10.1145/1534414.1555
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51-60. IEEE Computer Society, 2010. doi: 20.1109/FOCS.2000.22 URL https: //ooi.//oiio/ org/10. 1109/ /FO09//CC...0 RDCC.2000.1. 2010.12.
Vitaly Feldman and Tijana Zmic. Individual privacy accounting via 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 ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 28080-28091, 2021. URL https: htt.tp::///prooedinnee BC773446044455800455400000000
Neu-
wwwrriss.ccppppe//ee/ 202//hahh/h////// Abstract. html.
Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In 5/th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 61-70. IEEE Computer Society, 2010. doi: URL https: http://ti.o.//////////... 20///10.22 1119/100CCC 2010. 85.
10.1109/FOCS.201000
Michael Hay. Marco Gaboardi, and Salil Vadhan. A programming framework for opendp, 2020. URL https::///pjoocctttt iq. harvard. edu/files
hdt//t/les/ppnnttttll/////////// http///pee///////ppn//////////// opendp--
programming 1tw.g//rrrrraerro.11...a00001000
1_01.pdf.
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 Leurning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 1376-1385. JMLR.org, 2015, URLhttp: html..
//proceedings.
mlr, .al.diinnnnmm.......mmmmm..m...m
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/ www./bg/////..........ooooe abs//a/3....//a/////aa/a/./aaa// 01399.137..
Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proc. VLDB Endow., 10(6):637-648, 2017. doi: 1011778/3053300055311 URL
http://www. vldb.
Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pages 263-275. IEER Computer Society, 2017. doi: 10. 10.1109/CSE2207.11 URL https:///oi..oooe org/ 1109 1190/CFF.201... 11
Jack Murtagh and Salil P. Vadhan. The complexity of computing the optimal composition of differential privacy. Theory Comput., 14(1):1-35, 2018. doi: 20.4066trc.2011..014aa000 URL
https://doi. org/11 10. 4086/toc. 2018. v014a008.
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. 2016 2016/hash/58cc http:////cc00002aaaa000002232...
http:ppooeednss.eeeeee Abstract html.
Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 765-774. ACM, 2010. doi: 10.1
1806689.1806799 URL https: //tee:///ooi /doii //t///iio///////////// org/10 01144/11066680 1806794.
11

---

Salil Vadhan and Wanrong Zhang. Concurrent composition theorems for differential privacy. 2022.
doi: 10.48550/ARXV..200..00 08335. URL htt.tppp///.xiioooo//a////////// 08335..
Salil Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 347-450. Springer International Publishing, 2017. doi:
10.1007/978- 3-319-57004 _1_7. URL https://dol. http:///ooo.rr///////o 10. 1007/078--000 3-19----1-----1 --1-7----11---7-----8- 8_7.
Salil P. Vadhan and Tianhao Wang. Concurrent composition of differential privacy. 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. 10.1007/988-3-000-0005---- https://doi org/10 10. 1007/978-333 030 90453-14111000 1_20.
URL
Justin Whitchouse, Aaditya Ramdas, Ryan Rogers, and Zhiwei Steven Wu. Fully adaptive composi- tion in differential privacy. CoRR, 105555220 2022. doi: 10448550/axx..22233058881 URL https://doi org/10 10. 48544/ 2203 05481.
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: An- mual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: http///poeeeen...eeeeee httppscccpppppeee httcc//pppe////////eee/ /hash/ ebb11eell1177734400066666002222. Abstract html.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We included a discussion for future directions.
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The full proofs will be available in supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) 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]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xE95r1f8YKs", "reviewer": "Reviewer_PTTm", "summary": "This paper deals with exploring the “cost” of a concurrent composition of *interactive* DP mechanisms, compared to the (standard) non-interactive case.\n \nThe well-known composition theorems for DP mechanisms only hold when the mechanisms are non-interactive.\nHowever, not all known mechanisms are non-interactive. The best example is the Sparse-Vector Technique, which is a very popular interactive mechanism, where the adversary in each round can (adaptively) choose a new query.\nA natural question that arises is whether we can generalize the well-known composition theorems for non-interactive mechanisms to the interactive case in which several mechanisms can be executed concurrently (or alternatively, does it matter if we compose them sequentially or concurrently in terms of the obtained privacy guarantee?)\n \nIt is important to note that in other settings, the answer to similar results is not always positive. For instance, in the context of interactive proof systems, it is well-known that parallel-repetition does not increase soundness as sequential repetitions for 2-prover (and multi-prover) games and for interactive arguments (aka, computationally sound proofs).\n \nHowever, in the context of interactive DP mechanisms, the situation seems more positive.\n \nVadhan and Wang 21 initiate the study of concurrent composition of interactive mechanisms. They showed that composing pure DP interactive mechanisms has the same cost as composing non-interactive mechanisms. However, for approximate DP mechanisms (i.e., with a parameter $\\delta>0$), they only provided a very basic (and wasteful) composition theorem.\n \nThis work makes two major steps towards a positive answer: First, they extend the tight technique of Vadhan and Wang 2021 in the pure DP case for the approximate DP case, yielding that the cost of concurrent composition of approximate DP interactive mechanisms is the same as in the non-interactive case. Second, they provide a similar result (using a different technique) for Renyi DP, which in particular implies such results for other popular notions of privacy like zCDP and tCDP. \n", "questions": "High-Level Questions:\n1) I’m wondering if each privacy loss measure (e.g., $(\\varepsilon,\\delta)$-DP, Renyi-DP, f-DP) requires a unique and tailored proof technique, or if one can find more general high-level arguments for showing equivalences between sequential and concurrent composition of interactive mechanisms.\nCan you explain (in high level) why the proof technique for $(\\varepsilon,\\delta)$-DP does not hold for Renyi-DP (and vice versa)? \n2) What about other approximate notions of differential privacy, i.e., approximate zCDP which is also very useful. Can you provide tight composition theorems for it by somehow combining your two results?\n\n\nTechnical Question:\n1) In the supplementary material, lines 548-551, there are four cases, and you claim that “It is easy to see that if none of the above happens, we can keep increasing $tE^{0/1}$ “. Can you elaborate? E.g., what happens if $tE^0$ is tight at $y_{t+1}$ but $tE^1$ is not? Why $Gap_1$ must be zero in that case?\n\nMinor issues/typos:\n1) Line 16: [Dwork et al. 2016] ->  [Dwork et al. 2006]\n2) Line 20: A remains -> M remains\n3) Line 90: $(\\alpha,\\varepsilon)$ -> $(\\varepsilon,\\delta)$\n4) I suggest to write $(\\varepsilon,\\delta)$-DP instead of writing $(\\varepsilon,\\delta)$-approximate DP all the time. This is very standard. You can mention it in Definition 2.\n5) Line 180: $IT(N^b:A)$ should be $IT(A:N^b)$ (be consistent).\n6) Line 213, the right term: missing $\\in S$ in both terms.\n7) Paragraph 216-223: Presents a different proof technique than what is written in the supplementary material. \n8) “The bound for $D_{\\alpha}(P||Q)$” -> “The bound for $D_{\\alpha}(Q||P)$”\n9) Line 324: $Z_T$ -> $z_T$\n\nMinor issues/typos in the supplementary material:\n1) Equation 18 (and other places): What is the difference between $E^b$ and $\\mathcal{E}^b$?\n2) Line 493: the -> then\n3) Line 497: contron -> control\n4) Equation 21: Why don’t you use the notation of $M^b((y_i),(x_i))$?\n5) Equation 22 and many other places: Write max{*} instead of max(*) to make it more readable. \n6) Equation after line 513: No second term in the max.\n7) I suggest replacing $tE$ with $\\tilde{E}$.\n8) Line 598: $B_1,\\ldots,B$ $->$ $B_1,\\ldots,B_k$.\n9) Equation after line 603, right term: $M_1^b -> M_{1,j}^b$ and  $M_k^b -> M_{k,j}^b$.\n", "limitations": "In the “Conclusion and Future Directions” section (section 4), the authors address the limitations of their results.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The results are important and impressive.\n2) The proof techniques of both cases (DP and Renyi-DP) are interesting.\n3) Overall, the paper is well-organized, and looks sound - All proofs are provided in the supplementary material. I read the full proof for the DP case and I didn’t find something false (There were a few things that I didn’t understand, see my questions below).\n\nWeaknesses:\n1) I find the two different proof techniques for $(\\varepsilon,\\delta)$-DP and Renyi-DP as a disadvantage rather than an advantage. It is unclear to me if there is something inherently different between the privacy loss measures in this context of sequential vs concurrent composition.\n2) While the authors did an effort to give an intuition for the proof in the Renyi-DP case, I still couldn’t understand the idea behind all the calculations.\n3) There are many typos and other minor issues in the writing (see examples in the next paragraph).\n\nOverall, I think the strengths of this paper are more significant than its weaknesses, so I recommend accepting it.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TfJZqIs0hP", "reviewer": "Reviewer_2XK9", "summary": "The paper, as the title suggests, studies optimal composition theorems for interactive differential privacy, following the framework of [Vadhan and Wang 2021] and resolving one of the open questions in that paper.\n", "questions": "See below", "limitations": "Unfortunately, I still find the paper missing an important piece, which is an explicit example illustrating how concurrent composition offers more than the existing framework ([Mironov, 2017] and [Dong et al., 2022]. Are there algorithms that previous works cannot analyze tightly or previous analysis is wrong/faulty? I also couldn't find anything helpful in [Vadhan and Wang 2021].\n\nThe framework seems novel indeed. However, if I were to do it, I would break each \"system\" $M_i$ into smaller pieces. Namely, as in Definition 1, each $M_i$ is a randomized mapping $Y^*\\to Y$ and hence can be decomposed into a sequence of traditional mechanisms: $M_{ij}:Y^j\\to Y,j=0,1,2,\\ldots$. If each of these $M_{ij}$ is private, then one can compose using the existing results even when they interleave (say the adversary decides to use $M_{i_t,t}$ after observing $t$ outcomes). What does interactive DP offer exactly? I would like to see an explicit playground where this question can be answered clearly.\n", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the simplified definitions of interactive system and concurrent composition, compared to [Vadhan and Wang 2021].\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Neo28RWsJo5", "reviewer": "Reviewer_wWSd", "summary": "This paper studies the concurrent composition of interactive differentially private mechanisms. It shows optimal parallel composition properties of approximate DP and RDP.", "questions": "See the weaknesses.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper studies an important problem. Currently, interactivity is one of the major obstacles in DP deployment. The previous optimal composition theorems only hold for sequential composition. Studying concurrent composition is timely research.\n\nWeaknesses: Most of the paper is sound to me, however, I have a few concerns.\n\n1. My main concern 1: on page 2, in the setup, the paper describes that ``A first computes a pair ... sends a query x_1 to M_{i_1} and gets the response.'', which is only one case in the interactive setting. The algorithm can send the first message to adversary A as well. The proof technique for the two cases might be different. For example, it claims that ``Again, we modify A to a new mechanism A' first queries RR...'' on page 5, which is only for one case.\n\n2. My main concern 2: I'm not sure if Corollary 1 is immediate from Theorem 2, since zCDP allows for varying \\alpha in the Renyi divergence. I don't see how the proof can be directly generalized here. This paper needs to justify this claim.\n\n3. In the proof of RDP, the proof assumes the order of the messages, which needs justification. The order lemma in [VW21] only holds for approximate DP but not RDP, although I'm convinced it's true (still, there should be a lemma to prove this before using this fact.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "086DNOcxAp", "reviewer": "Reviewer_uLrt", "summary": "This work studies the problem of concurrent composition for differential privacy. The authors provide formal proofs for differential privacy guarantees for parallel composition for different notions of differential privacy. First, they extend the results by Vadhan and Wang [2021] on concurrent compositions with pure differential privacy, then they extended those results to also include other privacy notions such as Renyi DP and zero-concentrated DP.", "questions": "If possible, it would be nice to discuss how the adversary can use the query history to gain more information from the current query.", "limitations": "The authors discuss the limitations of the work, where possible future directions and extensions are discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies a significant problem, and the results are original. Extending the results for sequential composition theorems to concurrent theorems is an important step towards better understanding privacy. This work is interesting towards at least some audience.\n\nThe paper is well written and clear, however, some issues need to be clarified. The paper needs some proofreading still, but next are some examples of things to double check:\n\n-The distinction between mechanisms and systems is mentioned in section 1.1, however, in laters parts of the paper, it seems that those are used interchangeably. For instance, on page 2, \"Suppose $M_1,M_2,\\cdots, M_k$ are $k$ systems.\" As from the definition above, should those be mechanisms instead?\n\n- In section 1.2, \"that $IT(A: M_1^0,\\cdots,M_k^0)$ and $IT(A: M_1^0,\\cdots,M_k^0)$, shouldn't the second one have superscript $1$?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept