13
$\begingroup$

A differentially private algorithm takes datasets containing inputs and produces randomized outputs, such that no small change in the dataset can shift the distribution of outputs by too much. This is normally discussed in the context of privacy - when you observe the output, you cannot infer anything about a given input. But it also implies that an attacker with control over just a single input cannot effectively poison the data to change outcomes.

One might say this is useful only in a very weak threat model, compared to, say, a model in which a constant fraction of (or even most) inputs can be poisoned. The main assumption would be that it's costly to create new inputs. But a typical case to want a differential privacy guarantee for is when the unit that the datasets are being measured with respect to is a user of a service, e.g. collaborative filtering settings.


Consider the Netflix dataset, with ~100M ratings from ~500K users, to ~20K movies. In this case, the average movie has only 5K ratings. Thus 1% of users being adversarial would negate any real signals - i.e. many malicious users rating a single movie well to boost it may be indistinguishable from normal behavior. A realistic threat model for Netflix might reasonably assume costly account creation. So the number of poisoned ratings for a given movie is at least proportional to the cost to the attacker.

A more practical attack would be a single user giving bad ratings to all but one movie. This sort of attack would be mitigated by differential privacy. Differential privacy has the property of group privacy, which says a group of size $g$ can blow up outcome probabilities by $e^{g\epsilon}$ instead of $e^\epsilon$. Since cost is assumed to be linear in group size, this would be reasonable for small $g\epsilon$.


Googling for keywords "differential privacy" + "data poisoning" (and variants), I couldn't find a discussion about this, despite many parties being interested in the intersection of privacy and security. For example, see here, and here. In the second pdf, there's even a table with differential privacy in the remedy column for the attack on confidentiality, but not in the column for attack on model integrity. So is there something wrong with my reasoning?

Is my reasoning sound? Are there any works which discuss a threat model similar to what I'm describing (or is it too silly for serious researchers to consider)?

$\endgroup$

migrated from cs.stackexchange.com Oct 23 '17 at 5:44

This question came from our site for students, researchers and practitioners of computer science.

  • 3
    $\begingroup$ Yep, that's a good idea. I don't know of any works that discuss it. $\endgroup$ – usul Oct 26 '17 at 14:12
  • $\begingroup$ Potentially related recent work: arxiv.org/pdf/1802.03471.pdf $\endgroup$ – Thomas Jul 2 '18 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.