On Anonymity Metrics for Practical Anonymous Communication Protocols

Anonymous communication protocols are indispensable to protect users' privacy in open networks such as the Internet. Therefore they have wide application, e.g., electronic voting, and enormous research has been conducted on them. However, since it is difficult to devise general 'anonymity metrics' for practical anonymous protocols such as Crowds, few attempts have been made so far to establish such measures. Therefore, toward anonymity evaluation of practical anonymous networks, first we propose and formalize two novel anonymity metrics for practical anonymous communication networks. Next we shall discuss whether or not deterministic protocols can provide anonymity efficiently in terms of computational complexity. Unfortunately, we can show that it is difficult to build efficient anonymous networks only by means of deterministic approaches. We also run simulation experiments and discuss the results