4
$\begingroup$

The definition of differential privacy says that an algorithm $M$ is $(\epsilon,\delta)$-differentially private if

$$P(M(x \in D) \in S)\leq e^\epsilon P(M(x \in D')\in S) + \delta$$

where $D,D'$ differ by one row and $\delta$ is $\text{negligible}$ in the number of database rows, so $\delta< \frac{1}{p(n)}$ with $n$ being the number of database rows; why do we take $n$ as parameter for this negligible function?

$\endgroup$
4
$\begingroup$

$\varepsilon$-differential privacy is absolute: for any pair of databases, you cannot gain more than a small amount of probabilistic information about a single individual. When you add or remove an individual in your database, all possible outputs of your algorithm can appear with similar probability.

By contrast, $(\varepsilon,\delta)$-differential privacy allows this process to fail sometimes: you can have an output that happens with $\delta>0$ probability if the individual is present, and never happens otherwise. If you're super unlucky and this output comes out of your algorithm, an attacker can know that the individual in question is in the set.

Now, how often does that happen? How many users in the dataset are at risk? Well, each user has a $\delta$ probability that this might happen to them. So on average, this will happen $\delta \cdot n$ times (expected value of a binomial law of parameters $(n,\delta)$).

You want $\delta \cdot n$ to be small, because you don't want to leave any user at risk. If $\delta=\frac{1}{100\cdot n}$, you can say "with 99% probability, this bad scenario doesn't happen". But if delta is not a negligible function in $n$, then on average, your algorithm will leave some users at risk when $n$ grows.

$\endgroup$
  • $\begingroup$ thanks @Ted, but why "you can have an output that happens with δ >0 "? isn't output probability P(M(x∈D′)) (for D')? $\endgroup$ – volperossa Mar 23 '17 at 18:53
  • $\begingroup$ Yes, so for a database D', some output $S$ has a small chance $\delta$ of happening, while for another adjacent database D, it can absolutely not happen. So if the attacker observes $S$ and knows that the database is either D or D', they can now that it's actually D' and not D, with certainty. They have gained certainty on the data even though the process was probabilistic. That can't happen if $\delta=0$. $\endgroup$ – Ted Mar 29 '17 at 15:05

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.