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?


1 Answer 1


The definition of ($\epsilon$, $\delta$)-differential privacy does not (nor should not) discuss how one should set $\delta$ as a function of the number of records in the input dataset. If you put a period just after ".. differ by one row" you would have the proper definition (by my judgement).

Importantly, differential privacy definitions are universally quantified over all input datasets they must accept as input, and the number of rows is not a parameter on which they can depend. The $\delta$ in ($\epsilon$, $\delta$) is a constant, not a function of $|D|$.

Moreover, the definitions should not depend on it. Consider a hypothetical mechanism that hashes each row and if all hashes are equal releases the dataset in the clear. This might have a very low probability of disclosure as the size of the dataset grows, but would you want to be the first person to contribute? What guarantee could you make of this algorithm to others with a straight face: "if there are many other participants, and I'm not saying there are, we are unlikely to release your data"?


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.