The MIX technique forms the basis of many popular services that offer anonymity of communication in open and shared networks such as the Internet. In this paper, fundamental limits on the anonymity provided by the MIX technique are found by considering two different settings. First, we consider an information theoretic setting to determine the extent of information inherent in observations of the traffic passing through the MIX.We show that if the size of sender anonymity sets is less than the total user population, the information contained in traffic observations is sufficient to deduce all communication relationships between senders and receivers using the MIX. More importantly, we show that even if every user sends a message in each communication round, it is possible to compromise the anonymity significantly. We precisely characterize the extent of compromised anonymity in each case.

In the second setting, we assume that the attacker has unlimited computational resources and is free to choose any attack algorithm. We derive tight upper and lower bounds on the minimum number of observations required to deduce all recipient peer-partners of a targeted user. The analysis done in these two settings reveals many discrete mathematical structures inherent in anonymity sets, and the intuition gained from these structures can be used when designing or using a MIX based anonymity technique.