Hey, Thank you for all the responses. I figured out that I left some important details out, probably because I thought about it for a long time. I'm sorry about that. I will try to formulate it again:
Assume that the world contains correct people (People you can trust) and corrupt people (Those you can't trust). Also assume that the world has a majority of correct people (If it helps, you may assume 3/4 correct people). I am given a set S which contains k members (The music band). Assume that a majority of this set is correct. >From time to time: - A random person (From the world) joins the band. (With good probability this new member is correct). - A random person (From the band) leaves the band. ( The band always have at least k people. The full story is that if the band becomes too big, it is splits into two bands. If the band becomes too small, it dies. But you can forget about all this and just assume that the band always have at least k people. ). Note that those steps leave the set with a majority of correct people with high probability. Assume that I met the original band. At some point in the future I meet some group of people (Maybe none of them was in the original band). How can they prove to me that they were formed from the original band by a set of steps as described above? And the real question I care about: How can they prove to me that a majority of them is correct? It's pretty important that the amount of data the band keeps should be no more than logarithmic in the amount of steps that have occurred. I think that linear is just too much data to store. @Jonathan: I think the threat model here is the Byzantine model. I hope that it answers your question. @Dave: Your point of view is interesting :) @Alexandre: I still haven't read the article. I will check it out. thanks. @Andrew: The trusted majority is about what I meant. I didn't know about the ship of theseus. cool :) real http://www.freedomlayer.org On Wed, Jan 7, 2015 at 6:48 PM, andrew cooke <and...@acooke.org> wrote: > On Thu, Jan 08, 2015 at 03:33:24AM +1100, Dave Horsfall wrote: > > On Wed, 7 Jan 2015, realcr wrote: > > > > > I am looking for some crypto primitive to solve a problem I have. > > > > [...] > > > > I guess, if it is really a band application as opposed to something more > > abstract, it boils down to what you mean by "descendants". At least one > > founding member left? Are the offspring of same OK? Some musos can be > > really purist about this. > > i'd suggest that you can assume that there is always a majority of members > who > can be trusted. so you need something that can follow a trusted majority, > even if they include no-one who is original. > > fwiw, when searching for previous work, this kind of problem is often > referred > to as "the ship of theseus" (preserving identity of the whole when all > parts > are replaced) - http://en.wikipedia.org/wiki/Ship_of_Theseus > > andrew > _______________________________________________ > cryptography mailing list > cryptography@randombit.net > http://lists.randombit.net/mailman/listinfo/cryptography >
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
