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?


1 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.

  • 1
    $\begingroup$ There is a standard definition that if satisfied implies the mechanism is "good" in the sense outlined above. The standard definition says, effectively, that when epsilon is small there there exists no good "event" that can be used to distinguish a pair of adjacent databases. The standard definition makes precise (as a function of epsilon) how much they are allowed to differ. Yes. That is a good way to think about it. Each release comes with some privacy loss, it is up to you decide how to keep that loss limited. $\endgroup$ Commented Jun 13, 2020 at 20:50
  • 1
    $\begingroup$ To elaborate, on the standard definition we consider two databases to be adjacent if they differ by the presence of a single row. Let S denote a set of possible outputs of a privacy mechanism A. We think of S as an events which "occurs" when A outputs a value in S. Let P1(S) (P2(S)) denote the probability that S occurs when A is evaluated on D1 (D2, resp.). Then a privacy mechanism A is eps-DP if, for any pair of adjacent databases D1, D2, and any event S, e^(-eps) <= P1(S)/P2(S) <= e^eps. $\endgroup$ Commented Jun 13, 2020 at 20:52
  • 1
    $\begingroup$ Not precise on what you mean by share the true distribution of the noise. For instance, though, suppose A is a privacy mechanism returning the record count. Then A(D) could return the count of the records in D plus a number sampled from the Laplace distribution with scale 1/eps. It's okay to reveal that this is how A functions, but not the value return by the Laplace distribution separately from the count. $\endgroup$ Commented Jun 13, 2020 at 21:01
  • 1
    $\begingroup$ Exactly! I was meaning with distribution that the adversary knows additive noise's distribution, e.g., 1/eps-scaled Laplace distribution. This is also the case if we do not say the distribution but allow the adversary run our algorithm on any database he provides, where he can learn the noise distribution with infinite computational power. But if we just return a response on the asked query, and if we have $k*\epsilon$ budget, then we should stop after $k$ queries, if my understanding is correct. $\endgroup$ Commented Jun 13, 2020 at 21:07
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ Commented Jun 13, 2020 at 21:07

Your Answer

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

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