3
$\begingroup$

Differential privacy defines "privacy" of a mechanism $A$ as the "closeness" of the two distribution $Pr[A(D) \in S]$ and $Pr[A(D') \in S]$ where $D,D'$ differ in one element. And the distance between these distributions is multiplicative, i.e.

$\left| \frac{Pr[A(D) \in S]}{Pr[A(D') \in S]} \right| \leq e^\epsilon$

I have difficulty in understanding this choice of this multiplicative distance measure, as opposed to the standard distance (statistical difference) as in cryptography (indistinguishability), i.e.

$|Pr[A(D) \in S] - Pr[A(D') \in S]| \leq neg(.)$

The paper "Calibrating Noise to Sensitivity in Private Data Analysis" by Dwork et al. put forth two reasons for using the multiplicative distance:

  1. It is more stringent, since if one probability is 0, the other must also be 0 (which is not guaranteed when using standard measure of statistical difference). This, I understand.
  2. The leakage (distance between the distributions) must be non-negligible for the utility of the mechanism. This I really struggle to understand. Could anyone give an simple example to illustrate this, please?
$\endgroup$

2 Answers 2

2
$\begingroup$

I can't give an example illustrating why leakage must be non-negligible for the utility of the mechanism, but I can give a proof of why leakage must be non-negligible for the utility of the mechanism.



Let $\;\; U \: = \: \left\{\langle D,D'\rangle : D,D' \text{ differ in one element}\right\} \;\;\;$.


By the triangle inequality, for all $D$ and $D'$, for all $S$,

$|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|$
$\leq$
number_of_elements $\cdot \operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\}$


If number_of_elements is polynomial and $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})\:$ is negligible, then
for all $D$ and $D'$, for all $S$, $\:|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|\:$ is negligible.

If number_of_elements is polynomial and
$\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$
is negligible, then $A$ is statistically close to being independent of $D$.

Therefore, if $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$
is negligible then the mechanism is not useful.

$\endgroup$
-1
$\begingroup$

Differential privacy has been "invented" for a completely different use case scenario than indistinguishability for data privacy. The scenario is that you outsource your data into an untrusted party with that amount of noise that when the untrusted party applies some operations on data , individual data privacy is protected but the aggregate operation is in clear revealed to the server (That is utility). And differential privacy asks for no inference with respect to the existence or no of a specific data record if you know the result of the aggregate function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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