An Accurate System-Wide Anonymity Metric for Probabilistic Attacks

The authors give a critical analysis of the system-wide anonymity metric of Edman et al. which is based on the permanent value of a doubly-stochastic matrix. By providing an intuitive understanding of the permanent of such a matrix, they show that a metric that looks no further than this composite value is at best a rough indicator of anonymity. They identify situations where its inaccuracy is acute, and reveal a better anonymity indicator. Also, by constructing an information-preserving embedding of a smaller class of attacks into the wider class for which this metric was proposed, they show that this metric fails to possess desirable generalization properties.