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


2 Answers 2

  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.

  • $\begingroup$ If the coin toss among mechanisms are independent, why don't we just write $P(x_2' \in S_2 | x_1 \in S_1)$ as $P(x_2' \in S_2)$? $\endgroup$
    – Vassily
    Dec 14, 2020 at 20:06
  • 1
    $\begingroup$ I think that the randomness in x_i are independent, but the definition of the random variable x_i depends on x_j for j<i. An example would be that x_i is I query the database for a binary response of whether a specific person's name appears in the data. If x_1 = yes, then x_2 is a query for that persons' age. If x_1 = no, then x_2 is a query for a different person's name. The answers returned for x_2 in both cases will involve a sample from some random distribution that is independent form x_1, but x_2 is itself dependent on x_1. $\endgroup$ Feb 24, 2023 at 17:29
  • $\begingroup$ @piggy Hi, in your last step, why you can combine P(x1') with P(x2'|x1)? I don't understand because x1' is different from x1. $\endgroup$ May 25, 2023 at 22:21
  • $\begingroup$ Adding to what @travelingbones said. As DP is defined for all queries in some class $Q$ it does not really matter that the two queries are adaptive or independent. Let $y_1 \xleftarrow{\$} M_1(X, q_1)$, then $q_2\in Q$ is picked according to some function $g(y_1)$. Regardless of how $q_2$ is picked (possibly independently of $y_1$), the outcome would be the same as $M$ is $\epsilon, \delta$-DP for all queries $q \in Q$. Note the distribution $M_2(X, q_2)$ is still affected by $y_1$. Hence writing it that way. $\endgroup$
    – Ari
    Jul 12, 2023 at 17:05

See question and answer here which identifies the same problem in the proof you mention. It also provides a proof in a more general setting that is akin to the one by Piggy Wenzhou.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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