Performance modelling of anonymity protocols

Anonymous network communication protocols provide privacy for Internet-based communication. In this paper, we focus on the performance and scalability of anonymity protocols. In particular, we develop performance models for two anonymity protocols from the prior literature (Buses and Taxis), as well as our own newly proposed protocol (Motorcycles). Using a combination of experimental implementation, simulation, and analysis, we show that: (1) the message latency of the Buses protocol is O(N2)O(N2), scaling quadratically with the number of participants; (2) the message latency of the Taxis protocol is O(N)O(N), scaling linearly with the number of participants; (3) the message latency of the Motorcycles protocol is O(log2N)O(log2N), scaling logarithmically with the number of participants. Motorcycles can provide scalable anonymous network communication, without compromising the strength of anonymity provided by Buses or Taxis.