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(D)$ and an ${ϵ}_1$-DP mechanism $M_1(D)$, 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(D)=Y,M_1(D)=Y]=Pr[M_0(D)=Y]Pr[M_1(D)=Y]$$

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

$$Pr[M_0(D^{\prime })=Y,M_1(D^{\prime })=Y]=Pr[M_0(D^{\prime })=Y]Pr[M_1(D^{\prime })=Y]$$

Dividing these two statements yields:

$$\frac{Pr[M_0(D)=Y]Pr[M_1(D)=Y]}{Pr[M_0(D^{\prime })=Y]Pr[M_1(D^{\prime })=Y]}$$

Now, you can group $M_0$ and $M_1$ together:

$$\left[\frac{Pr[M_0(D)=Y]}{Pr[M_0(D^{\prime })=Y]}\right]\left[\frac{Pr[M_1(D)=Y]}{Pr[M_1(D^{\prime })=Y]}\right]$$

By the definition of $ϵ$-DP, the first term is less than or equal to $e^{{ϵ}_0}$ and ...