Return to 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)$ be two instances drawn with a probability distribution $\mu$ over the set $S^n \times S^n$ then the protocol $P$ is to be called $``\epsilon-differentially$ $private"$ if the following holds,

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

• Now why does this make sense? Whats the intuition?

• How is this related to the bounded derivative definition?

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?