Towards a Practical Complexity-Theoretic Analysis of Mix Systems

The mix architecture, proposed by Chaum in 1981, allows for messages to be sent and received anonymously in computer networks. This talk will introduce the mix architecture and some of the most well known attacks for identifying users. Following this, the talk will analyse the average-case complexity of a provably optimal exact attack against the mix design, providing a practical complexity-theoretic metric for the strength of abstract mix systems.