About the definition of "differential privacy" in communication complexity

Question

In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense.

So the two parties $A$ and $B$ draw two strings $X$ and $Y$ from the set $S^n$ where $S$ is some finite set. Let $P$ be the protocol. Now if $z_1 = (X_1,Y_1)$ and $z_2 = (X_2,Y_2)$ are two instances drawn with a probability distribution $\mu$ over the set $S^n \times S^n$ then the protocol $P$ is called "$\epsilon$-differentially private" if the following holds:

$$e^{-2 \epsilon n} \leq \Pr[P(z_1) = p] / \Pr[P(z_2) = p] \leq e^{2 \epsilon n}$$

• Now why does this make sense? What's the intuition?

• How is this related to the bounded derivative definition?

Answer 1

Your definition is wrong. The correct definition is as follows. A protocol $P$ is $\epsilon$-differentially private (for $\epsilon > 0$) if for any two inputs $Z_1,Z_2$ differing in a single coordinates and any $p$, $$ e^{-\epsilon} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^\epsilon. $$ For small $\epsilon>0$, $e^\epsilon \approx 1 + \epsilon$, and $e^{-\epsilon} \approx 1 - \epsilon$; the quantity $e^\epsilon$ is easier to work with compared to $1+\epsilon$, since $e^{\epsilon_1} e^{\epsilon_2} = e^{\epsilon_1+\epsilon_2}$, whereas $(1+\epsilon_1)(1+\epsilon_2) \approx 1 + \epsilon_1 + \epsilon_2$ holds only approximately.

Another small note: the upper bound implies the lower bound and vice versa.

The definition implies that for any two inputs $Z_1,Z_2$ that differ in at most $d$ places, $$ e^{-\epsilon d} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon d}. $$ In particular, if the inputs have length $m$, then for any $Z_1,Z_2$ we have $$ e^{-\epsilon m} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon m}. $$ In your case $m = 2n$.