Anonymity and Unlinkability in Electronic Communications

Imagine a set of communication partners wants to keep their communication links secret. Consider the case where untrustworthy parties are able to observe every communication, which implies not only that they can detect the content of the communication, but also who is communicating and who is listening. Using this information, the untrustworthy parties try to link communicating parties. This, in a nutshell, is the problem of anonymous and unlinkable communication in computer networks. By use of encryption techniques the content of messages can be kept private. However, the communication links can still be detected. Since the addresses of sending and receiving parties are contained in the header of every message sent over the network, an untrustworthy party needs only to eavesdrop a single message of the communication in order to link sender and receiver. Additional techniques have to be used to hide this information. We address this problem in this thesis. We define measures for anonymity and unlinkability that are based on the information theoretic notion of entropy. These measures are used first to evaluate different approaches for anonymous and unlinkable communication and second, to show the effectiveness of attacks on these protocols. We present existing techniques for anonymous and unlinkable communication and highlight weak points of these techniques by applying attacks to them. In these attacks, known as traffic analysis attacks, the attacker basically tries to collect as much information about the communication as possible and then makes deductions concerning the communication links. We show that these traffic analysis attacks are applicable to many existing techniques. Furthermore, we introduce a new traffic analysis attack, namely the slotted packet-counting attack. Motivated by these findings, we present a protocol for unlinkable communication in computer networks. We prove that this protocol leaks no information on communication links in the case where attackers are able to observe any communication in the network. By this means, the protocol guarantees a user-defined degree of unlinkability. We also show that the protocol generates a minimal amount of extra messages for achieving a given degree of receiver anonymity, i.e. where an attacker is not able to detect the receiver of a message