2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ which inequality are you checking for tightness? motivate a bit more. $\endgroup$ – kodlu Sep 13 '20 at 1:10
  • $\begingroup$ @kodlu $Pr[M(x)=y] \le e^{2\epsilon} Pr[M(x'')=y] + (1+e^\epsilon)\delta$ for $x$ and $x''$ differ by two records. $\endgroup$ – Piggy Wenzhou Sep 13 '20 at 2:19
2
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.