[cryptography] The Wandering Music Band

realcr realcr at gmail.com
Wed Jan 7 16:14:27 EST 2015

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
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 :)


On Wed, Jan 7, 2015 at 6:48 PM, andrew cooke <andrew at 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 at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150107/cea545c7/attachment-0001.html>

More information about the cryptography mailing list