A lightweight mechanism for dependable communication in untrusted networks

We describe a method for enabling dependable forwarding of messages in untrusted networks. Nodes perform only relatively lightweight operations per message, and only the originator and destination need to trust each other. Whereas existing protocols for dependable communication rely on establishing a verifiable identity for every node, our protocol can operate in networks with unknown or varying membership and with no limits on the creation of new identities. Our protocol supports the maintenance of unlinkability: relays cannot tell whether a given originator and destination are communicating. The destination of each message generates an unforgeable acknowledgement (U-ACK) that allows relays and the originator to verify that the message was delivered unmodified to the destination, but relays do not need to share keys with the originator or destination, or to know their identities. Similarly, the endpoints do not need to know the identities of the relays. U-ACKs can be seen as a building block for dependable communication systems; they enable nodes to measure the level of service provided by their neighbours and optionally to adjust the level of service they provide in return, creating an incentive for nodes to forward messages. Our work is ongoing.