10
$\begingroup$

I think I have a decent intuitive understanding of what the $\delta$ parameter means in $(\varepsilon,\delta)$-differential privacy: I can explain it to a non-specialist in terms of "what are the chances that something goes horribly wrong".

Even if I understand (and can work with) the formal definition, I'm not sure I could do the same for the $\varepsilon$ parameter. I've recently been asked to design a differentially private mechanism for a simple survey, and I have no idea which $\varepsilon$ to choose in practice nor how to justify this decision.

Ideally, I'd like to successfully explain what a particular choice "means" to somebody who isn't a privacy specialist. Any idea how to do that?

$\endgroup$
8
$\begingroup$

A colleague gave me the following explanation that I think makes a lot of intuitive sense, so I'm reproducing it here. Skip to the last paragraph it you don't care about the proof.

Suppose you're trying to track one individual user, and you're trying to figure out whether they're in the database. You have some prior knowledge about this: $\frac{P(in)}{P(out)}$ is how much more likely you think the user is in the database than isn't.

How does this change once you know the output $O$ of the algorithm? The posterior knowlege can be written as $\frac{P(in|O)}{P(out|O)}$. We can use Bayes' theorem to decompose it:

$$\frac{P(in|O)}{P(out|O)}=\frac{P(in)P(O|in)}{P(out)P(O|out)}=\frac{P(in)}{P(out)}\cdot \frac{P(O|in)}{P(O|out)}$$

If the algorithm is $\varepsilon$-differentially private, then it satisfies $e^{-\varepsilon}\le\frac{P(O|in)}{P(O|out)}\le e^{\varepsilon}$, since there's only one user different between the two scenarios. Using the previous formula, we get:

$$ e^{-\varepsilon} \cdot \frac{P(in|O)}{P(out|O)}\cdot \le \frac{P(in)}{P(out)} \le e^{\varepsilon} \cdot \frac{P(in|O)}{P(out|O)} $$

This is essentially telling us that $e^\varepsilon$ is how much confidence we can gain about whether one user has been added/removed from the data, by looking at the output. When $\varepsilon=\log(2)$, we can gain a factor of $2$ in the knowledge we have: if we had no information at the beginning (say, $P(in)=P(out)=0.5$), now we might have information like $P(in|O)=2/3$ and $P(out|O)=1/3$, but not a bigger difference.

If you want to dive a bit deeper, I wrote a blog post to elaborate a bit on this reasoning and give a concrete example. I also explain how the formula above can be used to find bounds on the possible values of $P(in|O)$ depending on $P(in)$ and $\varepsilon$:

Graph showing the posterior/prior bounds depending on ε

$\endgroup$

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.