Differential Privacy: is the bound for group privacy tight?

Question

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!

Answer 1

Yes, this bound is tight.

The optimal partition selection mechanism introduced in this paper achieves the bound: every step "uses up" 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.)