<p>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.</p>

<p>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 <a href="https://arxiv.org/abs/1611.02315" rel="noreferrer">most</a>) 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.  </p>

<hr>

<p>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.  </p>

<p>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$.</p>

<hr>

<p>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 <a href="https://arxiv.org/pdf/1611.03814.pdf" rel="noreferrer">here</a>, and <a href="https://asokan.org/asokan/research/SP_in_ML_MLBP_lecture.pdf" rel="noreferrer">here</a>.  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?</p>

<p>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)?</p>

CC BY-SA 4.0
2018-07-02T18:13:26.007Z
Potentially related recent work: https://arxiv.org/pdf/1802.03471.pdf
Thomas Steinke
CC BY-SA 3.0
2017-10-26T14:12:15.090Z
Yep, that's a good idea. I don't know of any works that discuss it.
usul
CC BY-SA 4.0
2020-07-12T04:43:47.717Z
This paper is very much along the lines of what you are describing: https://arxiv.org/abs/1903.09860
Elle Najt
<machine-learning><application-of-theory><db.databases><st.statistics><security>
Differential privacy and data poisoning
WuTheFWasThat
# Differential privacy and data poisoning

(Asked by: username_0 on 2017-10-19)

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](https://arxiv.org/abs/1611.02315)) 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](https://arxiv.org/pdf/1611.03814.pdf), and [here](https://asokan.org/asokan/research/SP_in_ML_MLBP_lecture.pdf). 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)?

**Tags:** machine-learning, application-of-theory, db.databases, st.statistics, security

> **Comments:**
> **username_2**: Yep, that's a good idea. I don't know of any works that discuss it.  
> **username_1**: Potentially related recent work: https://arxiv.org/pdf/1802.03471.pdf  
> **username_3**: This paper is very much along the lines of what you are describing: https://arxiv.org/abs/1903.09860  

---

## 0 answers

