6
$\begingroup$

I don't understand the necessity of introducing the additive term δ in the differential privacy definition. Moreover, reading different papers and blogs they say that because of the δ term the mechanism is "broken" (whatever that means).

I would really appreciate some help in understanding the role and the effect of the δ term.

Many thanks in advance!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

The $\delta$ item is a relaxation of the $\epsilon$-differential privacy notion. The latter is a strong security notion because it requires an algorithm $\mathcal{A}$ to have very close output distributions on "neighbor" datasets $D_1,D_2$ that differ in a single record. From its formal definition

$\Pr[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times \Pr[\mathcal{A}(D_2) \in S]$,

we can see that the probability difference should be small for every output set $S$ even if the probabilities $\Pr[\mathcal{A}(D_1) \in S]$ and $\Pr[\mathcal{A}(D_2) \in S]$ are negligible. In other words, such a requirement needs to hold for very unlikely events. Sometimes we want to relax this definition a little bit to cover more general cases as discussed here, so the $\delta$ item is introduced:

$\Pr[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times \Pr[\mathcal{A}(D_2) \in S]+\delta$.

This essentially means that those highly unlikely "bad" events happen with probability $\leq\delta$. These "bad" events may break $\epsilon$-differential privacy but are properly bounded.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ First of all thank you for your answer. I understood your explanation, but I still cannot get the concrete advantage of introducing δ. Sure you say an unlikely event in $D_1$ can get more likely to happen in $D_2$. But it could before too, as the sign is $\leq$, which means the probability of an unlikely event in $D_1$ can always be greater in $D_2$. Am I missing something here? $\endgroup$
    – primef
    Jul 31, 2018 at 21:40
  • 3
    $\begingroup$ @primef The $\epsilon$-differential privacy definition looks asymmetric but actually symmetric. The condition should hold when you swap $D_1$ and $D_2$ because both $D_1,D_2$ and $D_2,D_1$ are neighbor datasets. The $\delta$ item allows for some bad events that do not fit the strong definition. $\endgroup$
    – Shan Chen
    Aug 1, 2018 at 2:00
  • 2
    $\begingroup$ Thanks again, now I understand the reason why $\epsilon$-differential privacy is defined as strong. I also understand that $\delta$ is the additional probability for which an event would occur, hence the probability for which the differential privacy guarantee breaks. What I'm still missing is the why. Why would I want to allow an error in the algorithm, why would I want to (with probability $\delta$) release a query that discloses confidential data? $\endgroup$
    – primef
    Aug 1, 2018 at 20:07
  • 2
    $\begingroup$ @primef One reason for the $\delta$ relaxation is that those bad events happen with very very small probabilities, e.g., smaller than the inverse of any polynomial in the size of the dataset. In practice, such bad events (that can disclose confidential data) do not even happen (with extremely high probability), so we do not need to care about them. This is similar to the fact that cryptography often guarantees security with high probability instead of absolute probability 1. $\endgroup$
    – Shan Chen
    Aug 2, 2018 at 6:07
  • 2
    $\begingroup$ I'm sorry to be so insistent, but I still don't get the advantage. The fact that the probability for an error is negligible, is more of a reason why ($\epsilon, \delta$)-differential privacy is not that bad and not a reason why I should switch to it coming from $\epsilon$-differential privacy. What is the benefit of ($\epsilon, \delta$)-differential privacy? You mentioned in your first answer "to cover more general cases", could you explain this further? What kind of general cases? $\endgroup$
    – primef
    Aug 2, 2018 at 14:23

Your Answer

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

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