Concurrent Composition Theorems for Differential Privacy

Introduction

A randomized algorithm $\mathcal{M}:\mathcal{X}\rightarrow\mathcal{R}$ is $(\epsilon,\delta)$-differentially private if for every pair of neighboring datasets $x,x^{\prime}\in\mathcal{X}$, and for every subset of possible outputs $\mathcal{S}\subseteq\mathcal{R}$,

Thus, differential privacy requires that for all neighboring datasets $x,x^{\prime}$, $\mathcal{M}(x)$ and $\mathcal{M}(x^{\prime})$ are close as probability distributions (as measured by the parameters $\epsilon$ and $\delta$). A number of variants of differential privacy have been defined based on other ways of measuring closeness, leading to Concentrated differential privacy (CDP) [DR16, BS16] and Rényi differential privacy (RDP) [Mir17] and $f$-differential privacy ($f$-DP) [DRS19].

2 Interactive Differential Privacy

Definition 1.1 considers only non-interactive mechanisms $\mathcal{M}$ that release query answers in one shot, but data analysts often interact with a database in an adaptive fashion. In fact, many useful primitives in differential privacy such as the Sparse Vector Technique [DNR+09, DNPR10, DR14], and the Private Multiplicative Weights [HR10] allow analysts to ask an adaptive sequence of queries about a dataset. It motivates the study of interactive mechanisms to capture full-featured privacy-preserving data analytics. Here, we view the mechanism $\mathcal{M}$ as a party in an interactive protocol, interacting with a (possibly adversarial) analyst.

An interactive protocol $(A,B)$ is any pair of functions on tuples of binary strings. The interaction between $A$ with input $x_{A}$ and $B$ with input $x_{B}$ is the following random process (denoted $(A(x_{A}),B(x_{B}))$):

Uniformly choose random coins $r_{A}$ and $r_{B}$ for $A$ and $B$, respectively.

Repeat the following for $i=0,1,\ldots$. (a) If $i$ is even, let $m_{i}=A(x_{A},m_{1},m_{3},\ldots,m_{i-1};r_{A})$. (b) If $i$ is odd, let $m_{i}=B(x_{B},m_{0},m_{2},\ldots,m_{i-1};r_{B})$. (c) If $m_{i}=\texttt{halt}$, then exit loop.

The view of a party in an interactive protocol captures everything the party “sees” during the execution.

3 Concurrent Composition

A fundamental problem in differential privacy is studying how the privacy degrades under composition as more computations are performed on the same database. The composition property is particularly useful when we want to ask interactive queries on the same database, and it also allows us to design a complex differentially private algorithm by combining several building blocks. Formally, we define the composition of a sequence of non-interactive $k$ mechanisms $\mathcal{M}_{1},\mathcal{M}_{2},\ldots,\mathcal{M}_{k}$ as the non-interactive mechanism $\mathcal{M}={\text{Comp}}(\mathcal{M}_{1},\mathcal{M}_{2},\ldots,\mathcal{M}_{k})$ defined as

where each mechanism $\mathcal{M}$ is executed using independent random coins.

The composition of non-interactive mechanisms has been studied extensively in the literature. The basic composition theorem [DKM+06] states that the privacy parameters add up linearly when composing private mechanisms. The advanced composition theorem [DRV10] provides a tighter bound where the privacy parameter grows sublinearly under $k$-fold adaptive composition. Later, the optimal composition theorem [KOV15, MV16] gives an exact characterization of the privacy guarantee under $k$-fold composition. The relaxations of differential privacy including zero-concentrated differential privacy (zCDP) [DR16, BS16], Rényi differential privacy (RDP) [Mir17], and $f$-differential privacy ($f$-DP) [DRS19] allows for tighter reasoning about composition. In the abovementioned work, some of them [DRV10, MV16] are framed in a way that the adversary can adaptively choose the mechanisms $\mathcal{M}_{1},\mathcal{M}_{2},\ldots,\mathcal{M}_{k}$, and thus the adaptive composition can be viewed as an interactive mechanism.

In many cases, analysts may wish to perform multiple interactive analyses on the same dataset concurrently, which raises the question of concurrent composition, first studied for differential privacy in [VW21]. In this setting (illustrated in Figure 1), an adversary can arbitrarily interleave its queries to several differentially private mechanisms, and those queries might be correlated and depends on the answer received in other mechanisms. As a motivating example, several organizations might set up multiple DP query systems on datasets that may refer to the same set of individuals. Each query system has its own privacy budget $\epsilon$. Suppose an adversary can concurrently access those systems, and a query sent to one system might depends on all the previous messages that received from other systems. For example, when we run two Sparse Vector mechanisms $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ concurrently, the queries for $\mathcal{M}_{1}$ depends on previous answers from $\mathcal{M}_{2}$, and vice-versa, but we only know the overall privacy guarantees for $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ when they are executed independently. If the executions were sequential, meaning that the adversary completes its interaction with $\mathcal{M}_{1}$ before issuing any queries to $\mathcal{M}_{2}$, then we can hardwire the answers from $\mathcal{M}_{1}$ into the adversary’s strategy. When attacking $\mathcal{M}_{2}$, the privacy loss for $\mathcal{M}_{2}$ will be bounded as usual. But when the queries are interleaved, it is no longer clear how to define a fixed adversary strategy against either of the mechanisms $\mathcal{M}_{1}$ or $\mathcal{M}_{2}$. It is not clear if the adversary can run any concurrent attack to break the privacy guarantees, and therefore, we wish to provide a provable guarantee to account for the total privacy loss in such systems. Formally, the concurrent composition of interactive mechanisms is defined as follows.

Let $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ be interactive mechanisms. $\mathcal{M}=ConComp(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ is the concurrent composition of mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ defined as follows:

Random sample $r=(r_{1},\ldots,r_{k})$ where $r_{j}$ are random coin tosses for $\mathcal{M}_{j}$.

Inputs for $\mathcal{M}$ consists of $x=(x_{1},\ldots,x_{k})$ where $x_{j}$ is a private dataset for $\mathcal{M}_{j}$.

$\mathcal{M}(x,m_{0},\ldots,m_{i-1};r)$ is defined as follows:

Parse $m_{i-1}$ as $(j,q)$ where $j=1,\ldots,k$ and $q$ is a query to $\mathcal{M}_{j}$. If $m_{i-1}$ cannot be parsed correctly, output halt.

Extract history $(m_{0}^{j},\ldots,m_{t-1}^{j})$ from $(m_{0},\ldots,m_{i-1})$ where $m_{i}^{j}$ are all of the queries to mechanism $\mathcal{M}_{j}$.

Output $\mathcal{M}_{j}(x_{j},m_{0}^{j},\ldots,m_{t-1}^{j};r_{j})$.

Vadhan and Wang [VW21] showed that the advanced and optimal composition theorems extend to the concurrent composition of interactive pure DP mechanisms.

Suppose that for all non-interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ such that $\mathcal{M}_{i}$ is $(\epsilon_{i},\delta_{i})$-differentially private for $\delta_{1}=\delta_{2}=\ldots=\delta_{k}=0$, their composition ${\text{Comp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ is $(\epsilon,\delta)$-differentially private. Then for all interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ such that $\mathcal{M}_{i}$ is $(\epsilon_{i},\delta_{i})$-differentially private for $\delta_{1}=\delta_{2}=\ldots=\delta_{k}=0$, the concurrent composition ${\text{ConComp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ of interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ is $(\epsilon,\delta)$-differentially private.

They prove this by reducing the analysis of interactive pure DP mechanism to that of analyzing the Randomized Response mechanism [War65, DMNS06]:

Suppose that $\mathcal{M}$ is an interactive $(\epsilon,0)$-differentially private mechanism. Then for every pair of neighboring datasets $x,x^{\prime}$, there exists an interactive post-processing function $\mathcal{P}$ such that for every adversary $B\in\mathcal{B}$, we have

Here $\mathcal{P}$ is an interactive post-processing function that depends on $\mathcal{M}$ and a fixed pair of neighboring datasets $x,x^{\prime}$. It receives a single bit as an output of $RR_{\epsilon}(0)$ or $RR_{\epsilon}(1)$, and then interacts with the adversary $A$.

Note that Theorem 1.1 and Theorem 1.2 do not apply to the case where the composed mechanisms $\mathcal{M}_{i}$ are $(\epsilon_{i},\delta_{i})$-DP for $\delta_{i}>0$. In this case, [VW21] only show a bound that is similar to the “group privacy” property of $(\epsilon,\delta)$-DP. In particular, if $\epsilon_{1}=\epsilon_{2}=\ldots=\epsilon_{k}=\epsilon$ and $\delta_{1}=\delta_{2}=\ldots=\delta_{k}=\delta$, they show that the concurrent composition ${\text{ConComp}}(\mathcal{M}_{1},\mathcal{M}_{2},\ldots,\mathcal{M}_{k})$ is $(k\epsilon,\frac{\exp(k\epsilon)-1}{\exp(\epsilon)-1}\delta)$-differentially private. This is suboptimal even compared to basic composition. It left as an open problem that if any composition theorems for non-interactive mechanisms can extend to all variants of DP interactive mechanisms.

Does Theorem 1.1 extend to other variants of DP (such as $(\epsilon_{i},\delta_{i})$-DP with $\delta_{i}>0$, Rényi DP, $f$-DP)?

4 Our Results on Concurrent Composition

In this paper, we close this gap and show that any composition theorems of non-interactive mechanisms also extend to the concurrent composition of interactive DP mechanisms for approximate DP. In particular, we show that Theorem 1.1 extends to the case that $\delta_{i}>0$:

Suppose that for all non-interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ such that $\mathcal{M}_{i}$ is $(\epsilon_{i},\delta_{i})$-differentially private for $i=1,2\ldots,k$, their composition ${\text{Comp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ is $(\epsilon,\delta)$-differentially private. Then for all interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ with finite communication such that $\mathcal{M}_{i}$ is $(\epsilon_{i},\delta_{i})$-differentially private for $i=1,2\ldots,k$, the concurrent composition ${\text{ConComp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ of interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ is $(\epsilon,\delta)$-differentially private.

We also handle general $f$-DP as defined and discussed in the section below.

Suppose that for all non-interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ such that $\mathcal{M}_{i}$ is $f_{i}$-DP for $i=1,2\ldots,k$, their composition ${\text{Comp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ is $f$-DP. Then for all interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ such that $\mathcal{M}_{i}$ is $f_{i}$-DP for $i=1,2\ldots,k$, the concurrent composition ${\text{ConComp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ of interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ is $f$-DP.

Theorem 1.3 follows directly from Theorem 1.4 because $f$-DP defined below captures $(\epsilon,\delta)$-DP as a special case [WZ10, DRS19]. Interestingly, the generalization to $f$-DP is important for our proof, even if we only want to prove Theorem 1.3. We explain the detailed proof technique in the section below.

In summary, our results show that there is no extra privacy loss due to the concurrent access to multiple interactive mechanisms. We can now safely run multiple interactive differentially private algorithms in parallel, while allowing communication with all them during their executions.

5 f𝑓f-DP and Interactive vs. Noninteractive Hypothesis Testing

$f$-differential privacy ($f$-DP) [DRS19] is a generalization of $(\epsilon,\delta)$-differential privacy based on the hypothesis testing interpretation of differential privacy. Differential privacy attemps to measure the difficulty of distinguishing two neighboring datasets based on the ouput of a mechanism. Specifically, an adversary considers the following hypothesis testing problem:

For any two probability distributions $Y$ and $Y^{\prime}$ on the same space, define the trade-off function $T(Y,Y^{\prime}):\rightarrow$ as

where the infimum is taken over all (measurable) rejection rules $\phi$.

Proposition 1.7 gives the necessary and sufficient condition for $f$ to be a trade-off function.

A function $f:\rightarrow$ is a trade-off function if and only if $f$ is convex, continuous, non-increasing, and $f(x)\leq 1-x$ for $x\in$.

$f$-DP allows the full trade-off between type I and type II errors in the simple hypothesis testing problem to be governed by a trade-off function $f$. A larger trade-off functions implies stronger privacy guarantees.

Let $f$ be a trade-off function. A mechanism $\mathcal{M}:\mathcal{X}\rightarrow\mathcal{R}$ is $f$-differentially private if for every pair of neighboring datasets $x,x^{\prime}\in\mathcal{X}$, we have

$(\epsilon,\delta)$-DP is a special case of $f$-DP, taking $f=f_{\epsilon,\delta}$, where $f_{\epsilon,\delta}=\max\{0,1-\delta-\exp(\epsilon)\alpha,\exp(-\epsilon)(1-\delta-\alpha)\}$ [WZ10, DRS19].

To prove Theorem 1.4 (and hence Theorem 1.3), we prove the following analogue of Theorem 1.2, showing that every interactive $f$-DP mechanism can be simulated by an interactive post-processing of a non-interactive mechanism.

For every trade-off function $f$, every interactive $f$-DP mechanism $\mathcal{M}$ with finite communication, and every pair of neighboring datasets $x,x^{\prime}$, there exists a non-interactive $f$-DP mechanism $\mathcal{N}$ and an randomized interactive post-processing mechanism $\mathcal{P}$ such that for every adversary $B\in\mathcal{B}$, we have

Similarly to Theorem 1.2, in the case of $(\epsilon,\delta)$-DP, one can take the non-interactive mechanism $\mathcal{N}$ as the $(\epsilon,\delta)$-Randomized Response mechanism of [KOV15]. Indeed, [KOV15] shows that every non-interactive $(\epsilon,\delta)$-DP mechanism can be simulated as a post-processing of $(\epsilon,\delta)$-Randomized Response.

Theorem 1.4 follows from Theorem 1.5 in the same way as Theorem 1.1 follows from Theorem 1.2. Indeed, Theorem 1.4 implies that to analyze the concurrent composition of interactive mechanisms $\mathcal{M}_{i}$, it suffices to consider the composition of the non-interactive mechanisms $\mathcal{N}_{i}$. As a result, composition theorems for non-interactive mechanisms extend to the concurrent composition of interactive $f$-DP mechanisms.

Theorem 1.5 is an interesting statement about statistical hypothesis testing even without the application to differential privacy. Normally, hypothesis testing is presented as the task of distinguishing between two distributions or sets of distributions. This is a noninteractive task: a sample from the distribution is generated and given to the hypothesis tester, which then tries to decide whether the distribution is in $H_{0}$ or $H_{1}$. However, suppose instead we consider the task of distinguishing between two interactive mechanisms $\mathcal{M}_{0}$ and $\mathcal{M}_{1}$, each of which responds to queries in a randomized and stateful manner. Since the mechanisms are stateful, the hypothesis tester may never learn everything there is to know about the mechanism; in particular it cannot find out how the mechanism would have answered if different queries had been asked in the past. This is in contrast to ordinary hypothesis testing, where the full sample from the distribution is given to the hypothesis tester. Nevertheless, by viewing $\mathcal{M}_{0}$ as $\mathcal{M}(x)$ and $\mathcal{M}_{1}$ as $\mathcal{M}(x^{\prime})$, Theorem 1.5 implies that the two interactive mechanisms $\mathcal{M}_{0}$ and $\mathcal{M}_{1}$ can be simulated perfectly by noninteractive random variables $\mathcal{N}_{0}=\mathcal{N}(x)$ and $\mathcal{N}_{1}=\mathcal{N}(x^{\prime})$ such that even if we give $\mathcal{N}_{0}$ or $\mathcal{N}_{1}$ to a hypothesis tester in its entirety (thereby revealing how $\mathcal{M}_{0}$ or $\mathcal{M}_{1}$ would answer all questions), it cannot distinguish them any better than it could distinguish $\mathcal{M}_{0}$ and $\mathcal{M}_{1}$. The trick, of course, is that the simulation is “perfect” only when executing a single interaction with $\mathcal{M}_{0}$ or $\mathcal{M}_{1}$ (with no rewinding to explore multiple paths in the interaction tree).

The proof of Theorem 1.5 relies on the following two lemmas.

Let $f$ be a trade-off function, and suppose we have random variables $X$, $Y$ and $X^{\prime}$, $Y^{\prime}$ such that

Then there exists couplings $(X,Y)$ and $(X^{\prime},Y^{\prime})$ such that

To prove Theorem 1.5 using Lemmas 1.6 and 1.7, our strategy is to apply induction on the number of messages exchanged (which we can do since $\mathcal{M}$ has finite communication by assumptions). To reduce $k$ rounds of interactions to $k-1$ rounds, we consider the subsequent interaction conditioned on the first message. Depending on whether the first message sent from the mechanism $\mathcal{M}$ or the adversary $B$, we consider the following two cases.

Case 1. The adversary $B$ sends the first query $q_{1}$ to the mechanism $\mathcal{M}$. Fix a pair of neighboring datasets $x,x^{\prime}$. Fixing $q_{1}$, we denote the subsequent interactive mechanism by $\mathcal{M}_{q_{1}}$. By induction, $\mathcal{M}_{q_{1}}$ can be simulated by a post-processing of a non-interactive $f$-DP mechanism $\mathcal{N}_{q_{1}}$. Then we obtain $\mathcal{N}(x)$ and $\mathcal{N}(x^{\prime})$ by coupling the pairs $\mathcal{N}_{q_{1}}(x)$ and $\mathcal{N}_{q_{1}}(x^{\prime})$ on all the values of $q_{1}$, which is finite by our assumption of finite communication. We note that the coupling lemma 1.6 extends to finite number of random variables $Y_{1},\ldots,Y_{k}$ and $Y^{\prime}_{1},\ldots,Y^{\prime}_{k}$ by induction on $k$. Following the coupling lemma, we have $T(\mathcal{N}(x),\mathcal{N}(x^{\prime}))\geq f$. We can combine the interactive post-processing mechanisms $\mathcal{P}_{q_{1}}$ for all $q_{1}$ to obtain the interactive post-processing $\mathcal{P}$ that simulates $\mathcal{M}(x)$ and $\mathcal{M}(x^{\prime})$ from $\mathcal{N}(x)$ and $\mathcal{N}(x^{\prime})$. Thus, we have Theorem 1.5 holds for $k$ rounds of interactions.

6 Independent Work by Lyu

In independent and concurrent work, Lyu [Lyu22] proves Theorem 1.3 with a different argument. They show that every interactive $(\epsilon,\delta)$-DP mechanism can be simulated by interactive post-processing of a non-interactive $(\epsilon,\delta)$-DP mechanism, via an argument that is specific to $(\epsilon,\delta)$-DP that does not seem to generalize to arbitrary tradeoff functions $f$. Indeed, they leave the the general case of $f$-DP as an open problem, which is solved by our Theorems 1.4 and 1.5.

On the other hand, Lyu [Lyu22] also proves an optimal concurrent composition theorem for Rényi DP of any fixed order. In an earlier version of our paper [VZ22], we also claimed such a result, but our proof was incorrect (except for the case of Rényi DP of order $\alpha=1$),Specifically, we stated and used a chain rule for Rényi divergence that only holds for order $\alpha=1$ (i.e. KL divergence). as pointed out to us by Lyu. In this revision, we give a simple proof of Lyu’s theorem for Rényi DP by characterizing the optimal adversary strategy in Section 5.

Generalized Definitions of DP Mechanisms

To prove our results and discuss the several variants of differential privacy, it is convenient to introduce a more general abstraction, where distances between probability distributions can be in an arbitrary partially ordered set.

A generalized probability distance measure is a tuple $(\mathcal{D},\preceq,D)$ such that

$(\mathcal{D},\preceq)$ is a partially ordered set (poset).

$D$ is a mapping that takes any two random variables $X,X^{\prime}$ over the same measurable space to an element $D(X,X^{\prime})$ of $\mathcal{D}$.

(Post-processing.) The generalized distance mapping $D$ is closed under post-processing, meaning that for every function $g$, $D(g(X),g(X^{\prime}))\preceq D(X,X^{\prime})$.

(Joint Convexity.) Suppose we have a collection of random variables $(X_{i},X^{\prime}_{i})_{i\in\mathcal{I}}$ and a random variable $I$ distributed on $\mathcal{I}$. If $D(X_{i},X^{\prime}_{i})\preceq d$ for all $i\in\mathcal{I}$, then $D(X_{I},X^{\prime}_{I})\preceq d$.

For the generalized notion $d$-$\mathcal{D}$ DP, the difficulty of distinguishing two neighboring datasets is measured by the generalized distance between the distributions of an adversary’s views. The partially ordered set allows us to compare the level of privacy guarantees of mechanisms.

Let $(\mathcal{D},\preceq,D)$ be a generalized probability distance. For $d\in\mathcal{D}$, we call an interactive mechanism $\mathcal{M}$ $d$-$\mathcal{D}$ DP if for every adversary $B\in\mathcal{B}$ and every pair of neighboring datasets $x,x^{\prime}$, we have

Let us instantiate the standard pure DP and its variants using the definition above by specifying the generalized distances.

Max-divergence is closed under post-processing due to the data-processing inequality. Max-divergence satisfies joint convexity due to the following lemma.

For every two pairs of probability distributions $(P_{0},Q_{0})$ and $(P_{1},Q_{1})$, and every $\lambda\in(0,1)$,

Example: Rényi DP

For two probability distribution $P$ and $Q$, the Rényi divergence of order $\alpha>1$ is

Rényi divergence is also closed under post-processing due to the data-processing inequality, and it satisfies the joint convexity because an analogue of Lemma 2.1 also holds for Rényi divergence:

For every order $\alpha>1$, every two pairs of probability distributions $(P_{0},Q_{0})$ and $P_{1},Q_{1}$, and every $\lambda\in(0,1)$,

Example: f𝑓f-DP.

For $f$-DP, the partially ordered set $\mathcal{D}$ is defined as $(\mathcal{F},\preceq)$, where $\mathcal{F}$ is the set of all trade-off functions that satisfies the conditions in Proposition 1.7. The partial ordering is defined as $f_{1}\preceq f_{2}$ if $f_{1}(\alpha)\geq f_{2}(\alpha)$ holds for all $\alpha\in$. Note that the direction of the inequalities is reversed, corresponding to the fact that a larger trade-off function means less privacy loss. The distance mapping is the trade-off function $T$ in Definition 1.6.

$f$-DP also satisfies the two properties. First, $f$-DP is preserved under post-processing. We will only need to show the joint convexity of $f$-DP.

Suppose we have a collection of random variables $(X_{i},X^{\prime}_{i})_{i\in\mathcal{I}}$ and a random variable $I$ distributed on $\mathcal{I}$. If $T(X_{i},X^{\prime}_{i})\geq f$ for all $i\in\mathcal{I}$, then $T(X_{I},X^{\prime}_{I})\geq f$.

For any random variable $I$ distributed on $\mathcal{I}$. We have

Therefore, we have $T(X_{I},X^{\prime}_{I})\geq f$. ∎

It is useful to work with distance posets that are complete:

A partially ordered set (poset) $(\mathcal{D},\preceq)$ is complete if for every nonempty subset $S\subseteq\mathcal{D}$ has a supremum $\sup(S)$, where $s\preceq\sup(S)$ for every $s\in S$, and $\sup(S)\preceq t$ for every $t$ satisfying $s\preceq t$ for every $s\in S$.

The partially ordered set $(\mathcal{F},\preceq)$, where $\mathcal{F}$ consists of all trade-off functions satisfying the conditions in Proposition 1.7, is complete. Specifically, for $S\subseteq\mathcal{F}$, $\sup S$ is a trade-off function defined as follows.

where $F$ is a random variable that takes value in $S$ and $A:S\rightarrow$ is a function.

Taking the infimum over $F$ and $A$ on both sides, we get $h^{\prime}(\alpha)\leq h(\alpha)$, and therefore, $h\preceq h^{\prime}$.

Next, we shall show that $h$ is a trade-off function. Following the proposition 1.7, it suffices to check the four properties for $h$. We begin with proving the convexity of $h$. For every $a,b\in$, and every $\lambda\in$, we have

Therefore, $h$ is a trade-off function, and $\sup S$ exists.

A convenient consequence of joint convexity is that it suffices to consider deterministic adversaries.

and similarly for $x^{\prime}$. By joint convexity, we deduce:

Coupling and Chain Rule Properties of f𝑓f-DP

In this section, we prove that $f$-DP has the coupling and chain rule properties that we use to prove Theorems 1.4 and 1.5.

We say that a generalized distance $D$ has the coupling property if for any two pairs of random variable $X,X^{\prime}$ and $Y,Y^{\prime}$, we have $D(X,X^{\prime})\preceq d$ and $D(Y,Y^{\prime})\preceq d$, then there exists a coupling of $X$ and $Y$ (denoted as $(X,Y)$), and a coupling of $X^{\prime}$ and $Y^{\prime}$ (denoted as $(X^{\prime},Y^{\prime})$), such that $D((X,Y),(X^{\prime},Y^{\prime}))\preceq d$.

$(\mathcal{F},\preceq,T)$ has the coupling property: Suppose $f$ is a trade-off function and we have random variables $X$, $Y$ and $X^{\prime}$, $Y^{\prime}$ such that

Then there exists couplings $(X,Y)$ and $(X^{\prime},Y^{\prime})$ such that

We prove this lemma using the following result:

Let $P,Q$ be probability distributions on $X$ and $P^{\prime},Q^{\prime}$ be probability distributions on $Y$. The following two statements are equivalent:

Since a function is called a trade-off function if it is equal to $T(P,P^{\prime})$ for some distribution $P$ and $P^{\prime}$, for a given rade-off function $f$, there exists a pair of random variables $P,P^{\prime}$ such that $T(P,P^{\prime})=f$. By the Blackwell Theorem, since $T(P,P^{\prime})=f\leq T(X,X^{\prime})$, there exists a randomized algorithm $\mathcal{P}_{0}$ such that $\mathcal{P}_{0}(P)$ and $\mathcal{P}_{0}(P^{\prime})$ are identically distributed to $X$ and $X^{\prime}$, respectively. Similarly, since $T(P,P^{\prime})=f\leq T(Y,Y^{\prime})$, there exists a randomized algorithm $\mathcal{P}_{1}$ such that $\mathcal{P}_{1}(P),\mathcal{P}_{1}(P^{\prime})$ is identically distributed to $Y,Y^{\prime}$, respectively. We construct a coupling of $X$ and $Y$ as $(\mathcal{P}_{0}(P),\mathcal{P}_{1}(P))$, and a coupling of $X^{\prime}$ and $Y^{\prime}$ as $(\mathcal{P}_{0}(P^{\prime}),\mathcal{P}_{1}(P^{\prime}))$. Then the trade-off function between the two couplings satisfies the following inequality.

where Equation (8) follows from Lemma 2.9 in [DRS19], completing the proof. ∎

To formally state the chain rule property, we need a couple of definitions.

Let $(A,\preceq)$ and $(B,\preceq)$ be complete posets. A function $f:A\rightarrow B$ is continuous if $f(\sup(S))=\sup(f(S))$ for every set $S\subseteq A$.

Observe that every continuous function is monotone: if $a\preceq a^{\prime}$ are elements of $A$, then $f(a^{\prime})=f(\sup(a,a^{\prime}))=\sup(f(a),f(a^{\prime}))\succeq f(a)$.

Let $S$ be a finite set and $|S|=n$. Let $(A,\preceq)$ and $(B,\preceq)$ be complete posets. A function $f:A^{S}\rightarrow B$ is continuous in each variable if for every $i$, and for every $a_{1},\ldots,a_{i-1},a_{i+1},\ldots,a_{n}\in A$, the function $g(x)=f(a_{1},\ldots,a_{i-1},x,a_{i+1},\ldots,a_{n})$ is a continuous function from $A$ to $B$.

As an example, the standard chain rule of KL divergence is as follows.

In Lemma 3.3, we show that $f$-DP has the chain rule property.

The ChainRule function for $f$-DP is given as follows.

The type I error $\alpha_{\phi}$ and type II error $\beta_{\phi}$ are given as

Therefore, the trade-off function between $(X,Y)$ and $(X^{\prime},Y^{\prime})$ satisfies the following inequality:

Let $\delta$ go to , and combining with Equation (12), we have

Next, we shall show that the ChainRule function defined in (10) is continuous in each variable. Our goal is to show that for every $i$, every $S_{i}\subseteq\mathcal{D}$, and for every $f_{1},\ldots,f_{i-1},f_{i+1},\ldots,f_{n}\in\mathcal{D}$, we have

We can interchange the expectation and the infimum in Equation (14) because $A_{j}(f_{i})$, $j=1,\ldots,n$, are independent across $f_{i}\in F_{i}$. We also have that

where (16) is because trade-off functions are convex. Hence,

On the other hand, by setting $A_{j}(F_{i})=\alpha_{j}$ for all $F_{i}\in S_{i}$, the above equal sign is reached.

Concurrent Composition of d𝑑d-𝒟𝒟\mathcal{D} DP

Theorem 4.1 shows that if the generalized distance satisfies the coupling property in Definition 3.1 and the chain rule in Definition 3.4 , then every interactive $d$-$\mathcal{D}$ DP mechanism can be simulated by an interactive post-processing of a non-interactive $d$-$\mathcal{D}$ DP mechanism. This is a generalized statement of Theorem 1.5, as $f$-DP is an example of $d$-$\mathcal{D}$ DP.

Assume that the generalized probability distance measure $(\mathcal{D},\preceq,D)$ satisfies

every $d\in\mathcal{D}$ satisfies the coupling property.

Then for every $d\in\mathcal{D}$ and every interactive $d$-$\mathcal{D}$ DP mechanism $\mathcal{M}$ with finite communication complexity, and every pair of two neighboring datasets $x$ and $x^{\prime}$, there exists a pair of random variables $Y,Y^{\prime}$ and an randomized interactive post-processing mechanism $\mathcal{P}$ such that $D(Y,Y^{\prime})\preceq d$, and for every adversary $B\in\mathcal{B}$, we have

Note that the theorem is stated for mechanisms with finite communication, which is formally defined as follows.

Let $(A,B)$ be an interactive protocol (as in Definition 1.2). We say that $A$ has finite communication if for every $x_{A}$ there is a constant $c$, such that for all $r_{A},m_{1},\ldots,m_{i-1}$, we have

If $\max\{i,|m_{1}|,\ldots,|m_{i-1}|\}>c$, then $A(x_{A},m_{1},m_{3},\ldots,m_{i-1};r_{A})=\texttt{halt}$.

If $\max\{i,|m_{1}|,\ldots,|m_{i-1}|\}\leq c$, then $\sum_{j=0}^{i-1}\left|A(x_{A},m_{1},m_{3},\ldots,m_{j};r_{A})\right|\leq c$.

Here $|y|$ denotes the bit length of string $y$. $B$ having finite communication is defined symmetrically.

Our strategy is to apply the induction argument by the number of rounds of interactions. Fix a pair of neighboring datasets $x,x^{\prime}$. We consider two cases depending on whether the first message sent from the mechanism $\mathcal{M}$ or the adversary $B$.

The adversary $B$ sends the first query $q_{1}$ to the mechanism $\mathcal{M}$. Fixing $q_{1}$, the subsequent interactive mechanism $\mathcal{M}_{q_{1}}$ with input $x$ is defined by

By coupling property, there exists a pair of random variables $Y$, $Y^{\prime}$ and a randomized post-processing function $\mathcal{Q}_{q_{1}}$ such that $D(Y,Y^{\prime})\preceq d$, and we have that

So $Y$ and $Y^{\prime}$ are produced by coupling all possible queries. Then the interactive post-processing $\mathcal{P}$ is defined by $\mathcal{P}_{q_{1}}\circ\mathcal{Q}_{q_{1}}$, i.e.,

Case 2.

The mechanism $\mathcal{M}$ sends the first message $a_{1}$ to the adversary $B$. Let $q_{1},\ldots q_{m-1}$ be the queries from the adversary, and $A_{1},\ldots,A_{m}$ be messages from the mechanism. Fixing $A_{1}=a_{1}$, the subsequent interactive mechanism $\mathcal{M}_{a_{1}}$ is defined by

$\mathcal{M}_{a_{1}}$ uses its randomness to choose uniformly from randomness of $\mathcal{M}$ conditioned on $\mathcal{M}(x)=a_{1}$. Specifically, let $g_{x}$ be a random transformation such that if $R$ is uniform random for $\mathcal{M}$, then for all $x$, $g_{x}(R)$ is uniform on the randomness of $\mathcal{M}$ conditioned on $\mathcal{M}(x)=a_{1}$.

Let $Y_{A_{1}}$ be the random variable that defined as $Y_{A_{1}}|_{A_{1}=a_{1}}\sim Y_{a_{1}}$. $Y^{\prime}_{A_{1}}$ is defined similarly. By the chain rule, we have

Let $Y=(A_{1},Y_{A_{1}})$ and $Y^{\prime}=(A^{\prime}_{1},Y^{\prime}_{A_{1}})$, we define the post-processing $\mathcal{P}$ as

We now use Theorem 4.1 to prove that the concurrent composition of interactive mechanisms can be reduced to the composition of the non-interactive mechanisms.

Suppose that the generalized probability distance $(\mathcal{D},\preceq,D)$ satisfies the chain rule, every $d\in\mathcal{D}$ satisfies the coupling property, and $(\mathcal{D},\preceq)$ is complete. Suppose for all non-interactive mechanism $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ such that $\mathcal{M}_{i}$ is $d_{i}$-$\mathcal{D}$ DP for $i=1,2\ldots,k$, their composition ${\text{Comp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ is $d$-$\mathcal{D}$ DP, then the concurrent composition ${\text{ConComp}}(\mathcal{M}_{1},\ldots,\mathcal{M}_{k})$ of interactive mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ such that $\mathcal{M}_{i}$ is $d_{i}$-$\mathcal{D}$ DP is also $d$-$\mathcal{D}$ DP.

Concurrent Composition of Rényi DP

In this section, we give a different and simpler proof of the optimal concurrent composition of Rényi DP given in [Lyu22]:

We prove this theorem by characterizing optimal $\alpha$-RDP adversary strategy in Lemma 5.5.

We show that the optimal adversary strategy against the concurrent composition of $k$ mechanisms can be decomposed as a product of optimal adversaries against each mechanism independently:

Although this property of the optimal adversary strategy can be derived as a consequence of the optimal concurrent composition of Rényi DP in [Lyu22], we take a different approach to first prove this property and then use it to prove the optimal concurrent composition theorem for Rényi DP.

Our proof relies on the following two properties of Rényi divergence: the monotonicity property in Lemma 5.3 and the independence property in Lemma 5.4. The Rényi divergence is defined as follows.

For two probability distributions $P$ and $Q$, the Rényi divergence of order $\alpha>1$ is

Hence, $D_{\alpha}((U,V)||(U^{\prime},V^{\prime}))$ is monotonically increasing if $D_{\alpha}(V|_{U=u}||V^{\prime}|_{U^{\prime}=u})$ increases. So if $D_{\alpha}(V|_{U=u}||V^{\prime}|_{U^{\prime}=u})\leq D_{\alpha}(W|_{U=u}||W^{\prime}|_{U^{\prime}=u})$, then we have $D_{\alpha}((U,V)||(U^{\prime},V^{\prime}))\leq D_{\alpha}((U,W)||(U^{\prime},W^{\prime})).$

For any two pairs of random variables $U,U^{\prime}$ and $V,V^{\prime}$, if $U$ and $V$ ($U^{\prime}$ and $V^{\prime}$ resp.) are independent, then

The following lemma describes the optimal adversary’s strategy against an interactive mechanism. The proof of Lemma 5.5 uses the monotonicity property of Rényi divergence.

We decompose the view of the adversary into two parts: the first answer $A_{1}$ to the query $q_{1}$, and the view of the subsequent interaction. Fixing $q_{1}$, for every adversary $B$, we have

where (23) follows from Lemma 5.3. It implies that in order to maxmize (22), it suffices to choose $q_{1}$ to maximize the quantity in (23). ∎

We then use Lemma 5.5 to prove Lemma 5.2.

We now prove Theorem 5.1 using Lemma 5.2.

Acknowledgments

We are grateful to Xin Lyu for pointing out the error in the proof of our previously claimed concurrent composition theorem for Rényi DP [Lyu22]. We also thank an anonymous reviewer for pointing out the error in our previous proof of continuity.

References