Effectiveness of probabilistic attacks on anonymity of users communicating via multiple messages

Abstract

A major objective of any system-wide attack on an anonymity system is to uncover the extent to which each user of the system communicated with each other user. A probabilistic attack attempts to achieve this objective by arriving at some probability values for each of the system's possible input-output message pairs of reflecting actual communication. We show that these values lead to a probability distribution on the set of all possible system-wide communication patterns between users, and develop a combinatorial technique to determine this distribution. We give a method to measure from this distribution the effectiveness of any such attack or, alternatively, the level of anonymity remaining in the system in the aftermath of the attack. We also compare our metric with three earlier attempts in the literature to solve a similar problem, and demonstrate that the scope of our metric is far wider than those of all earlier ones.