Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The overall DP under the strong composition theorem for k-mechanisms is ($\epsilon \sqrt{k log(1/\delta)}$, k$\delta$) such that each individual mechanism has ($\epsilon, \delta$)-DP.
But what if say, 25% of the total k-mechanisms have $(\epsilon_1, \delta_1)$-DP, while the remaining 75% mechanisms have $(\epsilon_2, \delta_2)$-DP. What would the overall DP be under the rules of strong composition in this case?
In this case, you would need to use the optimal composition theorem of Murtagh and Vahdan (see theorem 1.4 of Concurrent Composition of Differential Privacy by Vadhan and Wang for example).
This says that the mechanisms can be combined into an $(\epsilon_g,\delta_g)$ mechanism whenever $\epsilon_g\ge 0$ satisfies $$(1+\exp(\epsilon_1))^{-0.25k}(1+\exp(\epsilon_2))^{-0.75k}\left(\sum_{i=0}^{0.25k}\sum_{j=0}^{0.75k}\binom{0.25 k}i\binom{0.75 k}j\mathrm{max}\left(\exp(i\epsilon_1+j\epsilon_2)-\exp(\epsilon_g+(0.25k-i)\epsilon_1+(0.75k-j)\epsilon_2)\right)\right)\le 1-\frac{1-\delta_g}{(1-\delta_1)^{0.25k}(1-\delta_2)^{0.75k}}.$$
