On Wed, Jan 7, 2015 at 10:40 AM, realcr <rea...@gmail.com> wrote:
> Hi,
> I am looking for some crypto primitive to solve a problem I have.
>
> Assume that I meet a group of people. call it S. I get to talk to them a
> bit, and
> then they are gone.
>
> This group of people walk together in the world. Sometimes they add a person
> to
> their group, and sometimes they remove one person. (You can assume it's a
> music
> band, then it all makes sense). Generally, though, you may assume that they
> have
> at least k people in the group at all times.
>
> Assume that I meet the resulting group at some time in the future, after
> many
> members were added or removed. How can the new group S' prove to me that
> they
> are the descendants of the original group S?
I think part of this will be more clearly defining what you mean by
"the new group S'".
Let's say the original band ("Kingdom Of Blight", a hardcore
death-metal band) is made up of Alice, Bob, Charlie, Dave and Eric.
Eric leaves (he claims Dave is stifling his creative potential, and
they are all becoming too commercial)
They then have a huge fight about whether or not the kazoo is a valid
instrument, and Alice and Bob split off to form "More Kowbell" and
Charlie and Dave form "Sounds of the Mandolin", a band specializing in
English folk songs from 1820 to 1843.
Who are the actual group now? I'm assuming KoB was still the band
after Eric left? What about when A and B left?
After a while Charlie leaves "Sounds of the Mandolin" and joins "More
Kowbell" - now there is a group of 3 of the original 5. Are they now
the new group S'? (If so, I *think* a this is simply an M of N
problem, so Shamir's Secret Sharing should work.. maybe... )
I think what might be best (in the real world) is for:
A: the identity to be tied to the group name -- the real world has
experience with this, like who owns a sing / IPR / etc.
B: you give a physical object to the original group (like a signed
piece of paper, or unique Hello Kitty statue) and tell them that this
identifies them. They then have to fight amongst themselves to
determine who own it. This does of course mean that one of them could
steal the paper / statue and claim they are the group.
I think the problem is not well enough defined / the band analogy
hides too much of the actual requirements...
W
>
> I include here some of my thoughts about this.
>
> 1. Naive Solution: Remembering lots of signatures.
>
> Every person in the world will have a key pair (of some asymmetric crypto)
> to
> represent his identity. When I first meet the group S, I collect all their
> public keys and keep them.
>
> Whenever a new member x is added to the group S, all the current members of
> S
> sign over the new list: S U {x}. Whenever a member x is removed from the
> group
> S, all the current members of S sign over the new list S \ {x}. The group
> members always have to carry with them all the signatures since the
> beginning of
> time.
>
> When I meet the group at some point in the future, I can just ask them to
> prove
> their current public keys, and also to show me all the signatures since the
> beginning.
>
> My issue with this solution is that the group has to remember more and more
> signatures as time goes by. I wonder if there is a more efficient way.
>
>
> 2. Using "Transitive Signatures"
>
> I have seen two articles about a concept called Transitive Signatures.
> Shortly: Given a signature of x over y, and of y over z, any participant
> will be
> able to generate a signature where x signs over z.
>
> http://people.csail.mit.edu/rivest/MicaliRivest-TransitiveSignatureSchemes.pdf
> https://eprint.iacr.org/2004/215.pdf
>
> I didn't manage to apply this method to my problem though.
>
>
> I will appreciate any idea or hint about how to solve this.
>
> Regards,
> real.
>
>
> _______________________________________________
> cryptography mailing list
> cryptography@randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>
--
I don't think the execution is relevant when it was obviously a bad
idea in the first place.
This is like putting rabid weasels in your pants, and later expressing
regret at having chosen those particular rabid weasels and that pair
of pants.
---maf
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
