> > Sorry, I should've read your formulation more carefully.
Don't worry about it :) We wrote lots of stuff since the first message, it's hard to trace it back to the original message. @Natanael: I think I understand now that our different opinions are due to different concepts of adversarial model. You are implicitly assuming that NONE of the previous versions of the group > will ever have a majority of members that are dishonest and pretend the > later reassignments didn't happen. > Michael wrote: the same problem exists if any version of the band contains a dishonest > majority. > My short answer to this: (The long answer follows below) - You have to wait a very long time until there is not a majority of correct nodes in the band. - The network is maintained in such a way that you pay for membership. Therefore the Adversary will not be able to stay long enough. The long Answer: Assume that there is some network of nodes. Some of those nodes are correct, and some of them are corrupt. Correct nodes are honest. They run your code. Corrupt nodes can do anything. (They can collude, etc). All the corrupt nodes are controlled by one Adversary. Also assume that it costs something to be in the network. Something that you pay periodically. (It will take me some time to explain what is that thing, so just assume it's true). In addition, it is given that the Adversary is bounded. More specifically, the Adversary can maintain (1/4)n corrupt nodes for some time. The rest (3/4)n nodes are correct. Let S be the band. It is some set of k nodes, where at least (2/3)k are correct nodes. In every step one of the following happens: - A random node (from the set S) leaves the set. - A random node (from the world) joins the set. The set is always of size at least k. k ~ polylog(n). You can think of k as log(n)^2, for example. I conjecture that the amount of correct nodes in the band will stay above (2/3)k for many steps. To make this conjecture more rigorous, I include here a very approximate calculation. Assume that in every step we get a random set, chosen uniformly from all the nodes in the world. If we assume that the world is really big, a binomial distribution should be a good approximation. We should calculate the probability of having less than (2/3)k correct nodes in a random set of size k. That would be about p_f := Pr[ B(k,3/4) <= (2/3)k ]. (p_f stands for probability for failure). By Chernoff's inequality, we get that p_f = Pr[ B(k,3/4) <= (2/3)k ] <= exp(-C * (1/k) * ((3/4)k - (2/3)k)^2) = exp(-C * k) If we pick k = log(n)^2, we get p <= exp(-C * log(n)^2) = 1 / ( n^( log(n)*C ) ). If I have not made any fatal mistake here (I might have, I calculated it just now :) ), then we conclude the following: If the network is of size n=2^30, then one have to wait about (2^30)^30 = 2^900 steps until there is no majority of correct nodes in the band. I consider 2^900 steps to be "never happens". Of course this is not the real calculation. The real one involves some Markov chain, and I don't know how to solve it. But I think it does give some idea regarding what I should expect.
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
