Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?
share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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