In this paper we present a novel approach to enable untraceable communication between pseudonyms. Our work provides strong sender and recipient anonymity by eliminating the need to know of each other’s address.

We use a variation of Chaum mixes to achieve unlinkability between sender and recipient and introduce a concept called extended destination routing (EDR) which relies on routing headers constructed in multiple layers of encryption and published in a distributed hash table (DHT). In order to communicate, a sender requests from the DHT the recipient’s routing header, which is extended and used for routing the message via a mix cascade to this recipient.

This work was performed in the context of the UniTEC reputation system and describes the functionality of its anonymous communication layer, which is completely independent of the other UniTEC layers. Although trust and reputation systems in general are typical application areas for our contribution, the presented concepts are suitable for various other application areas as well. We have implemented a prototype of UniTEC and present results from an ongoing evaluation in our network emulation testbed.