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):
- 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.
- 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$"
- 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?