Reply to Reviewer vdUQ
Thank you for your kind reply.
Our general composition result (Lemma 4.1) follows as an application of Corollary 4 from Dong et al., which directly follows from Theorem 11 from Dong et al. Their Theorem does not only hold for f-DP in particular, but more generally as it only relies on the premise that *‘[...] $f$ is a symmetric trade-off function such that $f(0) = 1$ [...]’*. Note that our Gaussian trade-off function from Corollary 5.1 fulfills this condition as it fulfills all criteria of a trade-off function and is symmetric. Hence, we can directly apply Theorem 11 from Dong et al. to our setting.
We are also happy to provide the outline of the proof of the specific composition result for Gaussian trade-offs which also highlights why their theorems are generally applicable to our trade-off functions. To this end, we consider Theorem 4 by Dong et al., which covers finite compositions (whereas Theorem 11 covers an infinite number of compositions). While this Theorem is stated in terms of $f_i$-DP, note that the $f_i$s are general (not DP specific) trade-off functions that originate from comparing two distributions against one another using hypothesis testing.
The proof then proceeds in the following steps:
Consider 2 sequential tests with trade-off functions $f$ and $g$. We want to compose the results from these two tests in the best possible way (i.e., what is the best trade-off the attacker can obtain that features the results from both tests $f$ and $g$). Trade-off functions can equivalently be represented by pairs of distributions that are being tested against each other, e.g., $f = \text{Test}(P, Q)$, where $P$ and $Q$ are distributions.
Theorem 4 of Dong et al. states that composing tests $f=Test(P,Q)$ and $g=Test(P’,Q’)$ results in the combined trade-off $f \otimes g = \text{Test}(P \times P’, Q \times Q’)$, where $\times$ denotes the joint distribution and $\otimes$ the composed trade-off. As shown in their Lemma C.2, the choice of representation (in terms of $P, Q$) does not matter and has no effect on the result. This part of their proof implies that we can apply their result to testing distributions stemming from both f-DP and f-MIP, as long as we can characterize the tests’ trade-off curves.
As an example, suppose that we are specifically composing the Gaussian trade-offs $g_{\mu_1}$ and $g_{\mu_2}$ with parameters $\mu_1$ and $\mu_2$. Recall that the $g_{\mu} = \text{Test}(N (0, 1), N (\mu, 1))$ is defined via testing two unit Gaussians of variance one at distance $\mu$ to each other. We can then do the following calculation:
$g_{\mu_1} \otimes g_{\mu_2} = \text{Test}(N (0, 1), N (\mu_1, 1)) \otimes \text{Test}(N (0, 1), N (\mu_2, 1))$
$= \text{Test}(N(0, 1)\times N (0, 1), N (\mu_1, 1) \times N (\mu_2, 1))$
$= \text{Test}(N ((0,0)^\top, \mathbb{I}), N ((\mu_1,\mu_2)^\top, \mathbb{I})$
$= \text{Test}(N ((0,0)^\top, \mathbb{I}), N ((\sqrt{\mu_1^2+\mu_2^2}, 0)^\top, \mathbb{I}) = \text{Test}(N (0, 1) \times N (0, 1), N (\sqrt{\mu_1^2+\mu_2^2}, 1)\times N (0, 1))$
$= \text{Test}(N (0, 1), N (\sqrt{\mu_1^2+\mu_2^2}, 1)) \otimes \text{Test}(N (0, 1), N (0, 1)) =
g_{\sqrt{\mu_1^2+\mu_2^2}} \otimes \text{Id} =g_{\sqrt{\mu_1^2+\mu_2^2}}$
We use the fact that a rotation does not change the hardness of the test. The last line follows from the fact that composition with the $\text{Id}$ test (testing two identical distributions) contains no information (formally proven in Dong et al.) and $\mathbb{I}$ denotes a 2x2 unit matrix.
We hope that our clarifications regarding the applicability of Theorem 11/Corollary 4 from Dong et al. and the simple outline of the underlying proof for Gaussian compositions clear the reviewer’s uncertainty. Please let us know if you have further questions.