Anonymous Communication by Branch-and-Bound

Communication in which the sender and receiver are both anonymous is usually achieved by using a telescoping construction. The channel is established hop-by-hop, where each relay gets to know the previous and next node along the route. All previously published anonymity services have in common that at least one of these information items inevitably becomes visible to an intermediate node. We present a new protocol that improves on the telescoping approach by additionally hiding the previous and next hops even from the forwarding relay itself. Thus, while achieving sender and receiver anonymity, a certain degree of anonymity among the intermediate relays is additionally assured. The hiding is based on uncertainty due to channel-branching in each step. In order to prevent the so-created tree from growing exponentially, we enforce dead end routes that bound the overall traffic. As a neat and complimentary by-product, the communication enjoys a certain robustness against node failure.