averaging attack at Google's RAPPOR I am reading the paper - "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response".


I don't understand how the averaging attack works.

I searched for "average attack" but couldn't find a related explanation.

Can someone explain it to me?

Thank you!
If someone has a large set of values:

$$B + \epsilon_0, B+\epsilon_1, B+\epsilon_2, …, B+\epsilon_n$$

One can average all these values together.  If the values of $\epsilon_0, \epsilon_1, \epsilon_2, …, \epsilon_n$ are independently distributed with a mean of 0, the average of these values will be closer to $B$ (essentially reducing the size of the error value by a factor of $\sqrt{n}$ on average).

So, if the attacker has access to a sufficiently large set of values, he can get an arbitrarily close idea of where the underlying $B$ is.

So, what Google is mandating is that you don't get the adversary access to such an independent set of $\epsilon$ values; if you always use the same error vector each time for a specific $B$ value, this averaging tells the adversary nothing he didn't already know.