2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Where have you seen this definition? It doesn't make much sense, though it is implied by the usual definition (but seems much weaker). $\endgroup$ – Yuval Filmus Jul 9 '15 at 4:17
  • $\begingroup$ "The Limits of two-party differential privacy" by Toniann, Vadan, Reingold, Talwar, Mironov, McGregor $\endgroup$ – user6818 Jul 9 '15 at 7:05
  • $\begingroup$ @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. $\endgroup$ – user6818 Jul 9 '15 at 7:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 9 '15 at 13:25
  • 1
    $\begingroup$ Differential privacy is defined on page 4 (Definition 2.1). Take it as an exercise to deduce your condition from that definition. $\endgroup$ – Yuval Filmus Jul 9 '15 at 19:15
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.