Abstract:Rerouting mechanism is adopted by rerouting-based anonymous communication systems such as Mixes, Onion Routing, and Crowds, to store and forward data in application layer. With this, users can communicate in an indirect way. Thus, identity information such as IP addresses can be effectively hidden against eavesdropper. This mechanism, however, can result in extra overhead in performance such as communication delay and participant payload, which may affect the applications of anonymous communication systems. In this paper, the participant payload induced by the rerouting mechanism is studied quantitatively. By investigating the establishment of rerouting paths in detail, a probability formula for calculating the participant payload is derived, which proves that the participant payload is determined by the number of participants, the number of rerouting paths, and the probability distribution of length of the rerouting paths. By applying this formula to a practical anonymous communication system, Crowds, a precise expected participant payload 1/(1-Pf)+1 can be derived, which significantly improves Reiter and Rubin's original analysis O((n+1)/((1(Pf)2n), and demonstrates that the participant payload in Crowds remains constant and is independent of the variation of the number of participants in Crowds. Simulation results are presented to testify the theoretical analysis. The conclusions can provide a theoretical support for the design and implementation of anonymous communication systems.