3
$\begingroup$

According to Wikipedia, given a randomized algorithm $\mathcal{A}$, two neighboring datasets $D_1, D_2$, a real number $\epsilon > 0$, $\mathcal{A}$ provides $\epsilon$-differential privacy, if $$ \frac{\mathbb{P}[\mathcal{A}(D_1) \in S]}{\mathbb{P}[\mathcal{A}(D_2) \in S]} \leq e^\epsilon $$ for all subsets $S$ of $\mathcal{A}$’s support.

However, I've stumbled across a different definition of $\epsilon$-DP, where also a lower bound is required: $$ e^{-\epsilon} \leq \frac{\mathbb{P}[\mathcal{A}(D_1) \in S]}{\mathbb{P}[\mathcal{A}(D_2) \in S]} \leq e^\epsilon. $$ Are these two definitions equivalent?

$\endgroup$

1 Answer 1

5
$\begingroup$

Yes, the definitions are equivalent. That the second implies the first is obvious. To see that the first implies the second, note that the datasets $D_1,D_2$ can be interchanged. So, if

$$ \frac{\mathbb{P}[\mathcal{A}(D_1) \in S]}{\mathbb{P}[\mathcal{A}(D_2) \in S]} \leq e^\epsilon $$

for all $D_1,D_2$, then in particular

$$ \frac{\mathbb{P}[\mathcal{A}(D'_2) \in S]}{\mathbb{P}[\mathcal{A}(D'_1) \in S]} \leq e^\epsilon, $$ hence $$ \frac{\mathbb{P}[\mathcal{A}(D'_1) \in S]}{\mathbb{P}[\mathcal{A}(D'_2) \in S]} \geq e^{-\epsilon}, $$ because all values are positive.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for pointing that $D_1$ and $D_2$ are interchangeable. I missed that. $\endgroup$ Aug 16, 2021 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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