HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the differential privacy definition with lower and upper bound equivalent to the definition with just an upper bound?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#143189, answer score: 5

Revisions (0)

No revisions yet.