Matthew Toseland wrote: > Encrypted tunnels via random routing and rendezvous: > > Partly as a result of reading the Rumour Riding paper, Michael has proposed > that we simply rely on random walks, instead of routing towards a specific > location. The advantage is it doesn't provide location samples, and we can > make the paths shorter than in the previous option (thus we can tune the > tradeoff between the part of the network that could have originated it vs the > cost). However, it is likely to be less reliable, and therefore require many > random walks, many nodes have an opportunity to get a predecessor sample > and/or the keys. Also imho it will frequently produce tunnels that are *too* > short. I'll let Michael elaborate on it.
OK, rumour riding [1] was designed for Gnutella-like networks, but it should work on any fast-mixing topology (social networks are generally thought to mix quickly, not sure about Kleinberg small worlds but I'd be surprised if they didn't). The basic idea is that instead of performing a search itself, the initiator chooses a random node (called the sower) to perform the search and pass the results back to the initiator through an encrypted tunnel. To find a sower, the initiator encrypts the query with a random symmetric key and sends the ciphertext and the key on independent random walks through the network. The first node to receive both the ciphertext and the key recovers the plaintext and acts as the sower. It's possible to show that this happens reasonably quickly in a fast-mixing network, especially if the initiator sends out multiple copies of the ciphertext and the key. I don't agree that random routing is more likely than rendezvous-at-a-key to produce tunnels that are too short - we can tune the expected tunnel length by varying the number of copies we send out, trading off anonymity against efficiency. We might also be able to reduce the traffic overhead by using a two-of-n secret sharing algorithm instead of a symmetric cipher, so any node that receives at least two shares becomes the sower, whereas with rumour riding a node that receives two copies of the ciphertext or two copies of the key can't become the sower. Cheers, Michael [1] http://www.ieee-icnp.org/2006/papers/s1a3.pdf
