Definition of Differential Privacy

Question

Can someone please explain the definition of differential privacy. Here is the one which I see and am unable to understand it: Its from this paper. I do not understand the use of $S$ here and also what does coin tosses of $\kappa$ mean here? Is it that the probability is over the choice of the randomized function $\kappa$ which is uniformly random from a set $K$ of functions? Also why does this intuitively make sense?

Answer 1

As noted already, you are correct in your interpretation of the coin tosses: this simply is terminology for the sampling of a random function from $\mathcal K$. The use of subsets is to cope with continuous functions where the probability of any individual value is 0.

Let's consider how we would want privacy preservation to work when our family of functions produces discrete outputs each with non-zero probability. We might hope that including omitting/adding one element to a data set has a small relative, probability of changing the output of the function (we cannot hope for 0 probability unless our family of functions is constant for all inputs and this captures very little information). Our first thought may therefore be to require that for all elements $x\in\mathrm{Range}(\mathcal K)$ we have $$\mathrm{Pr}_{\mathcal K}[\mathcal K(D_1)=x]\le\exp(\epsilon)\mathrm{Pr}_{\mathcal K}[\mathcal K(D_2)=x].$$ In fact this statement is equivalent to the quoted definition in the discrete case. Clearly the statement in the survey implies our first thought definition because we may take $S=\{x\}$. On the other hand, given any subset of discrete outputs $S$ we have $$\mathrm{Pr}_{\mathcal K}[\mathcal K(D_1)\in S]=\sum_{x\in S}\mathrm{Pr}_{\mathcal K}[\mathcal K(D_1)=x]$$ so if our first thought definition holds we have $$\mathrm{Pr}_{\mathcal K}[\mathcal K(D_1)\in S]\le \sum_{x\in S}\exp(\epsilon)\mathrm{Pr}_{\mathcal K}[\mathcal K(D_2)=x]=\exp(\epsilon)\mathrm{Pr}_{\mathcal K}[\mathcal K(D_2)\in S].$$ Thus our first thought is actually equivalent to the definition used.

However when we move to functions with continuous ranges, we could easily find ourselves in the situation where our first thought is meaningless because both probabilities are zero for all $x$. This does not mean that information cannot be inferred e.g. if there is a large jump in the value output by $K$ when we omit/add the extra element. However, the definition given does not have this defect as $S$ can be a continuous interval (or even a union of several continuous intervals) and the probability of the output lying in these ranges will not be zero for all possible choices of ranges. Thus the definition used is equivalent to what we might first conceive in the discrete case, but also has the advantage of retaining meaning in the continuous case.

Answer 2

I'll do my best to break it down. You have some randomized function (algorithm if you prefer) $\mathcal{K}$ that will take a dataset as input and output something about it (e.g., a noisy average of all values). Here, the noise injected by $\mathcal{K}$ into the output is determined by the random coin tosses (random bits sampled by $\mathcal{K}$), as you correctly intuit.