Hands-On Differential Privacy

Appendix E. Composition Proofs

This appendix contains proofs for several theorems from Chapter 2: basic sequential composition, general sequential composition, parallel composition, and immunity to postprocessing. While you won’t need to memorize these to prepare a DP release, working through each step can give you a deeper understanding of the behaviors of a DP mechanism. Further, knowing how to use composition and postprocessing will help you address more DP scenarios and build more complex pipelines.

Theorem: Basic Sequential Composition

Given an ${ϵ}_0$-DP mechanism $M_0\left(D\right)$ and an ${ϵ}_1$-DP mechanism $M_1\left(D\right)$, then applying each mechanism in sequence to a data set $D$ provides $({ϵ}_0+{ϵ}_1)$-differential privacy.

Proof

For notational simplicity, let’s start with the following scenario: you have an ${ϵ}_0$-DP mechanism called $M_0$, an ${ϵ}_1$-DP mechanism called $M_1$, and a data set D. If you apply $M_0$ to D, and then apply $M_1$ to D, the result is $({ϵ}_0+{ϵ}_1)$-DP, that is, the privacy loss sums. In fact, the order doesn’t matter here, so long as they are independent.

For some outcome Y, you can use independence and know that:

$$Pr[M_0\left(D\right)=Y,M_1\left(D\right)=Y]=Pr[M_0\left(D\right)=Y]Pr[M_1\left(D\right)=Y]$$

and for an adjacent data set $D^{\text{'}}$, this also holds:

$$Pr[M_0\left(D^{\text{'}}\right)=Y,M_1\left(D^{\text{'}}\right)=Y]=Pr[M_0\left(D^{\text{'}}\right)=Y]Pr[M_1\left(D^{\text{'}}\right)=Y]$$

Dividing these two statements yields: ...