The basic composition theorem in differential privacy states, that if I have mechanisms $M_1$, which is $(\epsilon_1, \delta_1)$-differential private, and $M_2$, which is $(\epsilon_2, \delta_2)$-differential private, then $M=(M_1,M_2)$ is $(\epsilon_1+\epsilon_2, \delta_1+\delta_2)$-differential private. (It works for more than two mechanisms, but 2 is enough to illustrate my questions.)

For the proof of this theorem, most papers refer to Dwork et al. "Our Data, Ourselves: Privacy Via DistributedNoise Generation" (section 2.2 thm 1, see pictures below) and I have 2 questions on this proof.

  1. The theorem is most of the time stated like above, without any restrictions on the mechanims. But am I right when I say: To be correct, we always(!) need to assume some form of independence? I.e. that the randomness in the mechanisms must be independent? It looks like that, when reading the proof, but it is never stated in the theorem statement (in all other publications I read), that got me worried...

  2. There is one step in the proof that I can't follow: After they use the differential privacy-inequations for each single mechanism, they say:

    If we look at the additive contribution of each of the δ terms, of which there are T, we notice that they are only ever multiplied by probabilities, which are atmost one. Therefore, each contributes at most an additive δ.

I don't understand this part. The $\delta$ terms are not just multiplied by probabilities, but also by the $exp(\epsilon)$ factor. And this factor is not always smaller than 1. It would be helpful if someone can explain that step in the proof to me in more detail.

Thanks in advance for any help.

Here is the proof copied from the paper:

proof of composition theorem

  1. You are right, we need to assume the coin toss of mechanisms are independent to each other, as stated in the proof.

  2. You are right, again. The proof in the paper seems to be problematic. Here's the modified proof: \begin{align} Pr[(x_1, x_2) \in S] &= Pr[x_1 \in S_1] Pr[x_2 \in S_2 | x_1 \in S_1] \\ &\le (\min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1]) + \delta )Pr[x_1 \in S_1] \\ &\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])Pr[x_1 \in S_1] + \delta \\ &\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])(e^\epsilon Pr[x_1' \in S_1] + \delta) + \delta \\ &\le e^{2\epsilon} Pr[(x_1', x_2') \in S] + 2\delta \end{align}

The key to avoid the problem you stated is instead of using $$ Pr[x \in S] \le e^\epsilon Pr[x' \in S] + \delta $$ we use $$ Pr[x \in S] \le \min(1, e^\epsilon Pr[x' \in S]) + \delta $$ for the inequalities.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.