So this paper is definitely interesting. One thing we should ask ourselves, though, is if we are OK with there being a non-uniform key distribution. Seems essential to me.
This might be a good temporary solution though. Doing markov chains with neighbors is a decent idea. The question is if we can replace it with a function whose output is equally hard to forge but also fairly random. There may be some simple operation we can perform on the output to make the distribution more equal. Also, I'm seeing their simulator source code but not their implementation code. On Thu, May 2, 2013 at 6:42 PM, Matthew Toseland <[email protected]>wrote: > On Tuesday 05 Mar 2013 15:57:58 Matthew Toseland wrote: > > A paper accepted by INFOCOM 2013 claims to: > > 1) Show that our view of Kleinberg is unrealistic because we do not have > the sideways lattice links - the closest connection to the target isn't > always closer to the target than we've been so far. > > 2) Prove that we can't have polylog routing, and show that perverse > cases where the best route will take us further away are increasingly > common as networks grow, and > > 3) Propose a new algorithm that is provably polylog. > > > http://www.p2p.tu-darmstadt.de/publications/details/?no_cache=1&tx_bibtex_pi1[pub_id]=TUD-CS-2013-0036 > > ("A Contribution to Analyzing and Enhancing Darknet Routing", Roos & > Strufe) > > > > Performance simulations show it is similar to ours or better depending > on the properties of the network, via a parameter C, "the maximal distance > to the closest neighbor over all nodes", i.e. if our closest links are > close enough, our current algorithm should work, but if not, their version > is significantly faster. > > > > The new algorithm changes backtracking and keeps a list of marked nodes > - all nodes visited AFAICS, or at least nodes where it backtracked. > Obviously this has security implications, but on darknet this is less > important than on opennet, and we really should have a separate tunnel > setup system for the very paranoid (e.g. based on Pisces). > > > > Having said that: > > - All the topologies simulated showed acceptable HTL for a 100,000 node > network, even using our current simplistic algorithm. Granted that's > somewhat idealized... > > - We can use redundancy to some degree to avoid perverse parts of the > keyspace breaking important functionality. I've suspected that "perverse > parts of the keyspace" exist for some time, and that seems to be the > paper's main concern; and it does not solve the problem either, it merely > limits it. > > - Right now hardly anyone uses darknet, and Michael Grube still hasn't > finished dealing with Pitch Black. > > > > His homepage also has some rather vague ideas under "open theses" on > censorship attacks on opennet via flooding; I suspect this was written by > his supervisor who may not have investigated the matter fully. IMHO > flooding opennet is a rather expensive attack, it's probably much easier to > MAST your target and take them offline IRL! :) > > http://www.p2p.tu-darmstadt.de/people/stefanie-roos/ > > > And they provide a new swapping algorithm too, which is simpler to > implement, only uses local information, is faster and far more attack > resistant: > > http://www.ukp.tu-darmstadt.de/fileadmin/user_upload/Group_P2P/share/publications/Attack_Resistant_Network_Embeddings_for_Darknets.pdf > > Now if only we really had a 10,000 node darknet to run these algorithms > on! Making it easy to build a darknet has to be a high priority. >
_______________________________________________ Devl mailing list [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
