Differential privacy on multiple queries – what is the behavior?

Question

Differential privacy framework still continue to be obscure in the following case:

If I make a set of queries, I can join their output to restore the original data. For this issue we have composition theorems that grants that every query consume just a "piece" of my $\epsilon$, so we can continue to answer queries for the total query "session" until I have pieces of my $\epsilon$.

So, my question is: what does "session" means? An attacker can make many sessions?

I think that is not very realistic that an user (that can be an attacker) can access just for a single "session" of queries (if we intend for "session" a "set of query that an user can make") . He could find a system to make "many sessions" (for example with different identities or similar, or working together with other attackers).

So, in these cases, how differential privacy works? Is there something that I misunderstand?

Answer 1

It would be helpful to have a link to the paper you are referring to. But the basic composition theorem says that each query $i$ an attacker sends to the database will just add its corresponding $\varepsilon_i$ to the total $\varepsilon$ of the entire process: $\varepsilon=\sum_i\varepsilon_i$. So "session" probably means "single query" in the context of your question.

And yes, your objection is a good one. If you use differential privacy in an interactive context, then you need to either:

• split your total privacy budget across all users (and when it runs out, stop anyone from querying the database);
• or assume that your users are not collaborating, and have some authentication in place to make sure each user cannot go above the privacy budget by connecting to the system as multiple people.