RFC: mechanisms for anonymizing distributed search

[<jcr13 () users sf net>]

Realtime search can be accomplished in a distributed setting by broadcasting a search request through a mesh network so 
that it is processed by all nodes in a particular neighborhood of the network.  Various deterministic mechanisms can be 
used to control the scope of the broadcast (such as TTLs or utility counters).  These mechanisms work well to achieve a 
limited exponential blow-up:  they quickly deliver a message to a large collection of nodes while also ensuring that a 
message does not affect the entire network.

In a setting where the anonymity of searchers and result-senders is important, these deterministic limiting mechanisms 
give attackers too much information about how far a search has traveled and too much control over how much farther it 
will go.

I have been developing mechanisms that work in conjunction with deterministic limiters to make search anonymous.  
Recently, new attacks involving coordinated neighbor nodes were discovered, and I have updated my mechanisms to deal 
with these attacks.

The document describing these mechanisms is here:

http://mute-net.sf.net/utilityCounters.shtml

The discussion of security- and anonymity-related issues starts in section 9.  New materal that deals with 
multi-neighbor attacks starts in section 10.1

Part of the document's focus is on utility counters, an alternative limiting mechanism that is more scalable than TTLs. 
 However, the anonymizing mechanisms will work just as well with more traditional TTL schemes.  Also, as shown in 
section 10.4, utility counters are not compatible with anonymity goals, though they would be a great improvement over 
TTLs in a system where anonymity is not important.

Comments are requested,
Jason Rohrer
--
http://jasonrohrer.n3.net