patternMinor
Is the differential privacy definition with lower and upper bound equivalent to the definition with just an upper bound?
Viewed 0 times
definitiontheboundequivalentprivacywithlowerjustdifferentialand
Problem
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?
$$
\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?
Solution
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.
$$
\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.
Context
StackExchange Computer Science Q#143189, answer score: 5
Revisions (0)
No revisions yet.