P. Venkitasubramaniam and V. Anantharam
"On the Anonymity of Chaum Mixes"
Submitted to IEEE Symposium on Information Theory,
2008.
The information-theoretic analysis of Chaum mixing under latency constraints is considered. Mixes are relay nodes that collect packets from multiple users and modify packet timings to prevent an eavesdropper from identifying the sources of outgoing packets. In this work, an entropy-based metric of {\it anonymity} is proposed to quantify the performance of a mixing strategy under strict delay constraints. Inner and outer bounds on the maximum achievable anonymity are characterized as functions of traffic load and the delay constraint. The bounds are shown to have identical first derivatives at low traffic loads.