Definition of Differential Privacy

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?

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.

• Thanks, for the answer. I think to be more educative this answer needs some more basics like a sample database, query, and the query result. In the end, we are talking a data and queries, so the connection is crucial to understanding. Nov 22 at 0:01

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.

• @DanielS if the function is trivial (i.e., $\mathcal{K}(x) = 0$ for all $x$) then the probability $\Pr[\mathcal{K}(D_b) = 0 \in S] = 1$. Did I miss something? Nov 18 at 11:42
• It's becoming increasingly unclear to me the scenario that you're trying to describe. Are you trying to describe the case where the family of functions $\mathcal{K}$ is just the family of trivial functions? These are definitely differentially private. If not then there will be a probability that the function is non-trivial. Nov 18 at 12:36
• I edited the answer and deleted the example, thanks for pointing out that it was confusing. Nov 18 at 14:29
• @DanielS could you write a proper answer? Nov 20 at 15:40