Anonymous Communication via the "Bus" method (A follow up to the earlier TOR post)

After reading the post on TOR, I felt compelled to right about this!

The purpose of TOR (onion routing) is to provide a means of anonymous communication.
The reason we need a means of anonymous communication is as such: currently, we have excellent methods of “encrypting” messages sent between pairs! However, although encryption makes it such that the content of a message is hidden, it is still possible to determine who is communicating, and an adversary can cut off communication between a communicating pair (this would be extremely detrimental in say making an important business transaction, or to take it a step further, covert military operations).

As the writer of the TOR post stated, TOR is an example of onion routing, where using successive layers of encryption each router (“onion router”) only knows its predecessor and successor but not the overall route. However, there is a problem with this type of routing! It is possible to observe traffic flows at the ends of the network so attackers can in some instances deduce whether or not two entities are communicating. (ref 2)

A model to improve the degree of anonymity is the busing model (which is in fact inspired by the real-life public transportation system which is used by people without vehicles, such as myself). The possible senders and receivers can be represented as bus stations and the information they are sending as passengers. This idea can be applied to the digital world by having a “bus” traverse through a network of n nodes, where node i sends a message destined for node j with probability p to a bus of m seats. The reason this model is anonymous is because the traffic pattern is fixed, and “passengers” (information) cannot be observed getting on and off the bus. (ref 1)

This model has yet to be used for significant practical purposes. One of the biggest obstacles in implementing this model is that with this setup is there are only a limited number of seats (resources) on the bus so it is possible a message sent by a node will overwrite a message sent by a previously visited node yet to reach its proper destination.

In fact, I am doing research regarding this model and as a SURF (hopefully, I guess I figure out April 1st) I am exploring ways to make this model feasible (to provide robustness against this problem of “overwriting” while keeping the amount of resources constant; in fact I feel I have found some improvements so if this subject interests you post comments and I will happily answer your questions).

Anyways, I couldn’t pass up a chance to talk about this; this is my current (and only) area of research so I give a special thanks to the person who wrote the TOR post which allowed me to talk a bit about the busing model for anonymous communication!

A few pertinent references:
1)Beimel, A., Dolev, S.. Buses for Anonymous Message Delivery. In 2nd International Conference on FUN with Algorithms, pages 1-13, Carleton University Press, 2001.
2)Roger Dingledine, Nick Mathewson, Paul Syverson. Tor: The Second-Generation Onion Router. Usenix Security 2004, August 2004.