Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
$\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.
