Differential Privacy: is the bound for group privacy tight? Suppose mechanism $M$ is $(\epsilon, \delta)$-differentially private. For datasets $x$ and $x''$ that differ by 2 elements, we have
$$
Pr[M(x)=y] \le e^{\epsilon} Pr[M(x')=y] + \delta \le  e^{2\epsilon} Pr[M(x'')=y] + (1+e^\epsilon)\delta
$$
where $x$ and $x'$ are adjacent, $x'$ and $x''$ are adjacent. This bound is the one from group privacy. Is this bound tight? If so, can anyone give me a specific example of the mechanism to illustrate that this bound is tight? I'm thinking of randomized response but seems doesn't achieve the $(2\epsilon, (1+e^\epsilon)\delta))$-indistinguishability for $M(x)$ and $M(x'')$.
Thanks a lot!
Yes, this bound is tight.
The optimal partition selection mechanism introduced in this paper achieves the bound: every step &quot;uses up&quot; all the $(\varepsilon,\delta)$ budget available, and for the particular case of $k=2$, the probability of releasing the partition is exactly $(1+e^\varepsilon)\delta$, while this probability is $0$ for $k=0$. The recurrence relationship gives you a tight bound for any $k$.
(Disclaimer: I'm one of the authors of this paper.)