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.
