"Anonymity under Light Traffic using a Network of Mixes"
P. Venkitasubramaniam and V. Anantharam
47th Annual Allerton Conference on Communications, Control, and Computing, Monticello, IL, Sep. 2008.

The analysis of a multi-source single-destination network of mixes is considered under strict latency constraints at each mix. Mixes are relay nodes that accept packets arriving from multiple sources and release them after variable delays to prevent an eavesdropper from perfectly identifying the sources of outgoing packets (also, the contents of the packets are encrypted to prevent these from being used to correlate the arrivals to the mix with its departures). Using an entropy-based measure to quantify anonymity, the anonymity provided by such a single destination network of mixes is analyzed, with the focus on light traffic conditions. A general upper bound is presented that bounds the anonymity of a single-destination mix network in terms of a linear combination of the anonymity of two-stage networks. By using a specific mixing strategy, a lower bound is provided on the light traffic derivative of the anonymity of single-destination mix networks. The light traffic derivative of the upper bound coincides with the lower bound for the case of mix-cascades (linear single-destination mix networks). Thus, the optimal light traffic derivative of the anonymity is characterized for mix cascades.