Anonymity attacks on mix systems: A formal analysis

Information theory turned out to be very useful in analyzing anonymity attacks in general. The concept of channel information leak is a good indicator of how successful an attack can be. While different information leak measures exist in the literature, the problem of representing anonymity systems using noisy channels has not been well studied. The main goal of this paper is to show how anonymity attacks on mix systems can be formally represented as noisy channels in the information-theoretic sense. This formal representation provides a deeper understanding of mix systems and prepares the field for a more rigorous and accurate analysis of possible attacks. We performed empirical analysis using three information leak measures (mutual information, KLSD, and Min-entropy) which revealed interesting findings about some mix variants. This paper tries to bridge the gap between theory and practice in the field of anonymous communication systems.