I am reading the paper - "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response". enter image description here

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.

| improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.