A New Information Leakage Measure for Anonymity Protocols

The main goal of anonymity protocols is to protect the identities of communicating entities in a network communication. An anonymity protocol can be characterized by a noisy channel in the information-theoretic sense. The anonymity of the protocol is then tightly related to how much information is being leaked by the channel. In this paper we investigate a new idea of measuring the information leaked based on how much the rows of the channel probabilities matrix are different from each other. We considered each row of the matrix as a point in the n-dimensional space and we used statistical dispersion measures to estimate how much the points are scattered in the space. Empirical results showed that the two proposed measures KLSD and KLMD are sensitive to the modifications of the attacker capabilities and most importantly they are stable when the a priori distribution on the secret events changes. We show that a variant of KLSD coincides with the classical notion of mutual information which gives the latter an interesting geometric interpretation. The same idea of statistical dispersion is used in a new decision function when the protocol is re-executed several times.