From my understanding of security protocols, it should be easy to do these two choices safely and fast, as it amounts to choosing a random element in S_N and filling lots of matrix entries with random elements between 1 and a

----- Forwarded message from Paul-Olivier Dehaye <paul-olivier.dehaye@math.uzh.ch> ----- Date: Fri, 23 Aug 2013 03:08:59 +0200 From: Paul-Olivier Dehaye <paul-olivier.dehaye@math.uzh.ch> To: tor-dev@lists.torproject.org Subject: [tor-dev] Global semi-passive adversary: suggestion of using expanders Reply-To: tor-dev@lists.torproject.org Hello, Thank you for working on Tor. I have a suggestion and would appreciate input. Please bear with me as I have a limited understanding of the design of Tor and all the different threats that it is meant to mitigate. Below, a (?) indicates a place where I need some confirmation that my understanding is correct, and N indicates either the number of Tor nodes, the number of end-users, or the amount of traffic (I assume these are all linearly related). As far as I can tell, the main threat by a global passive adversary comes from traffic analysis (?). This attack should become easier as the number of Tor nodes increases (?): Tor uses a clique topology, so the number of edges potentially carrying traffic grows like N^2. A dual way to see this is that not enough mixing can happen around a node for incoming/outgoing edge pairs, bar injecting a huge amount of fake traffic. To compensate, it seems natural to look for a sparse yet highly mixing network topology. Mathematically, those are called expanders [1]. A typical example of a family of expanders would be the Erdos-Renyi model [2], and indeed I have found in the literature suggestions for basing anonymizing protocols on such a model. The analysis in the presence of an active adversary becomes very difficult though. Alternatively, one could use a different method for constructing that expander topology, working "all at once". This comes from recent mathematics research (<= 5 years, certainly not my own, see [3]). The graph is then a Cailey graph [4] in a matrix group (the group is fixed and determined by an approximation to the number of Tor nodes, such as nearest third power of a prime number). In some sense this construction interpolates between mixing chains and Tor, and can be seen as a lot of mixing chains interwoven. In the setting of Tor, constructing the Cailey graph would require making two distributed randomize choices: - a matching of elements of the group to Tor nodes (possibly 2:1 for some Tor nodes) - a small subset of generators for the Cailey graph prime p, with some rejection. Once that is done, the network topology is fully determined, and with very high probability gives an expander. This means that traffic gets mixed up in very few hops. The number of hops needed grows as log N, with a constant that can be mitigated by chosing a large generating set above. This is the only downside I see (apart from difficulty to explain the math behind this): the latency would increase, from 3 in the current protocol to maybe 10 or so. I don't know the details of the behaviour of the constants in the last paragraph, and would appreciate feedback from the list before looking too much into this. Paul Dehaye [1] http://en.wikipedia.org/wiki/Expander_graph [2] http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model [3] http://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expand... 15 and remark below [4] http://en.wikipedia.org/wiki/Cayley_graph _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5