Differential Privacy: What is the 'game' between data holder and adversary?

Question

I have been reading the Differential Privacy (DP) literature for some time to get familiar with it. I feel comfortable with the Math and Stats foundations of it, but I am suffering a bit from the 'setting' of response release.

What I don't get is, the traditional definition of Differential Privacy says that any two neighbors should be indistinguishable from each other under an event. Since this holds for any neighbors and any possible event, all the individuals in the database are 'hidden'. But, what is the setting behind this definition? For example, some potential settings may be (with counter-examples):

1. We let the user (adversary) send the same query about the true database at hand (say $D$), and since we have DP, then the true query will not be able to found by the adversary. Counter-example: The adversary can ask the same query many times, average responses, and obtain the true query.
2. We give the user a single response. We also let the user know the true distribution of the additive noise. Then, he can try any possible 'candidate' database, and try to find the true database, but he will fail since the DP definition holds. Counter-example: After we send the response to the user, we should disappear and the user should try figuring out $D$ himself. This does not make any sense. Although, the most convenient mathematical definition to me is "even if the adversary knows the true noise distribution, and just one sample of our response, he won't figure out $D$"
3. We let the user ask a query only one time, so we never release multiple responses. Counter-example: If this is a one-time thing, then DP definition wouldn't make much sense. We can just sample a standard normal noise, and since we give a single sample of our response, the adversary won't be able to figure out anything. So DP should be of use in a repeated setting.

I lack knowledge in database systems. I just want to learn, in what setting does the DP definition makes sense? What kind of a game is going on between the data holder and the adversary?

Answer 1

What differential privacy guarantees is that the query output communicates at most a small multiple of $\varepsilon$ bits of information about any individual (row). I now comment on each setting outlined in your question:

1. Independently repeated queries constitute several distinct releases. There is a straight-forward composition theorem (See e.g. Sect 3.5) that follows directly from the definition of differential privacy. It states that aggregate privacy-loss is at most the sum of the individual privacy-losses of the constituent releases. So, in this case, the results of $k$ repeated queries of an $\varepsilon$-differentially private mechanism taken together constitute a $(k\cdot\varepsilon)$-differentially private release. If the adversary is supplying the queries, a typical mitigation strategy is to enforce query limits. You may also need to worry about collusion.

2. This is a non-issue. Again, from the definition of $\varepsilon$-differential privacy, one can argue that after observing the contents of the release, an adversary's posterior remains point-wise close to their prior. Specifically, for any candidate "true" database, the ratio of the posterior to the prior lives in the range of $[e^{-\varepsilon}, e^\varepsilon]$. Thus, when $\varepsilon$ is small, this remains close to 1 and the adversary can only negligibly improve upon their initial guess.

3. This is valid and does not contradict the definition of differential-privacy which, even in this case, ensures that even if the adversary possesses a lot of knowledge of the database, say even all up to a single row, they remain unable to conclude about its presence or absence with certainty.

Just to make sure I answer the question as asked, one formulation as a game is the following: Fix a privacy mechanism, $\mathcal{A}$. An attacker chooses a pair of databases $D_1$, and $D_2$ that differ only by insertion (or deletion) of a single record, gives these to a 3rd party which randomly evaluates either $\mathcal{A}(D_1)$ or $\mathcal{A}(D_2)$ and returns the result to the attacker, without indicating which database was used as input. The attacker knows the exact contents of $D_1$, $D_2$, and is given a full specification of the privacy mechanism $\mathcal{A}$, so that the attacker can independently evaluate $\mathcal{A}$ over $D_1$, $D_2$, or any input of their choosing. The goal of the attacker is to guess whether the provided evaluation is $\mathcal{A}(D_1)$ or $\mathcal{A}(D_2)$.

A good mechanism is one where the attackers success over random guessing is remains small. Intuitively, if the attacker is unable determine the input database from the result even with knowing the complete contents of $D_1$, $D_2$, and being permitted full knowledge of and experimentation with $\mathcal{A}$, it must be that the result carries little information about the row in which the databases differ.