B.2 Efficient Anonymous Group Communication

- Dr. Tim Grube -

This subproject addresses the important challenge of efficiency in anonymous communication. Solving this challenge is essential to provide anonymity in group communication.

Every exchanged message leaks metadata: this information describes the communication itself with, among others, sender, recipients, frequency of the communication. While the law protects this information, it is often published and misused with consequences for the participants of the communication---often consequences particular for the senders of information.

Anonymous communication systems like Tor break the link between senders and recipients of messages and diminish emerging metadata. However, their design requires duplicating messages for all recipients early, mostly at the sender itself. With that, the system has to handle an unnecessary burden of processing identical messages. This dissertation contributes a novel mechanism that establishes communication groups such that the message duplication is pushed as close to the recipients as possible. This dissertation also shows that this efficiency improvement does not come at costs of anonymity.

Moreover, the group establishment mechanism increases the robustness of the communication against users that leave and join the communication system. To encounter the additional information leakage, different mechanisms to share routing information are introduced and discussed under the angle of efficiency and anonymity. To also protect senders of messages, this dissertation adapts Dining-Cryptographer networks to enable sender anonymity with an adjustable trade-off between efficiency and anonymity.


The scientific contributions of this subproject fall into the following categories:

1. Efficient Communication Overlays: A novel overlay establishment mechanism is presented. This mechanism adapts Ant Colony Optimization (ACO) to connect senders and recipients with a reduced number of connections while the anonymity remains stable.

2. Reliable Communication under Churn: Churn often disrupts communication overlays, this thesis proposes a mechanism to counter this disruptions and increase the robustness of the communication. For that, the ACO-based mechanism utilizes residual pheromones to reconnect subjects to the communication overlay.

3. Routing Information Exchange considering Efficiency and Anonymity: Four methods to share routing information, namely successor lists, successor lists with multi-layer encryption, Bloom filters, and distributed lookup tables, are introduced into the anonymous communication setting, discussed and evaluated with respect to their properties concerning efficiency and anonymity.

4. Efficient and Effective Sender Protection: A novel mechanism based on asymmetric dining-cryptographer networks (ADCnets) is proposed to improve the efficiency of sender protection without degrading anonymity over time. Moreover, the trade-off between efficiency and anonymity can be controlled.