# About the definition of “differential privacy” in communication complexity

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?

• Where have you seen this definition? It doesn't make much sense, though it is implied by the usual definition (but seems much weaker). – Yuval Filmus Jul 9 '15 at 4:17
• "The Limits of two-party differential privacy" by Toniann, Vadan, Reingold, Talwar, Mironov, McGregor – user6818 Jul 9 '15 at 7:05
• @YuvalFilmus It would be great if you could kindly explain why this definition makes sense and what is the idea it is trying to capture. – user6818 Jul 9 '15 at 7:51
• I can't find this definition there. Instead, they have the usual definition of differential privacy. On page 16 in the version people.cs.umass.edu/~mcgregor/papers/11-2pdp.pdf I see that they are deriving your condition as a consequence of differential privacy. – Yuval Filmus Jul 9 '15 at 13:25
• Differential privacy is defined on page 4 (Definition 2.1). Take it as an exercise to deduce your condition from that definition. – Yuval Filmus Jul 9 '15 at 19:15

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.
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$.