On the Trade-Off between Relationship Anonymity and Communication Overhead in Anonymity Networks

Motivated by applications in industrial communication networks, in this paper we consider the trade-off between relationship anonymity and communication overhead in anonymity networks. We consider two anonymity networks; Crowds that provides unbounded communication delay and Minstrels, proposed in this paper, that provides bounded communication delay. While Crowds hides the sender´s identity only, Minstrels aims to hide the receiver´s identity as well. However, to achieve bounded message delay it has to expose the sender´s identity to a greater extent than Crowds. We derive exact and approximate analytical expressions for the relationship anonymity for these systems. While Minstrels achieves close to optimal anonymity under certain conditions, our results show that, contrary to expectations, increased overhead does not always improve anonymity.