Re: [cryptography] The Wandering Music Band

[realcr]

 You still don't get any meaningful security if old band members are
 assumed to be untrusted and you don't use a public checkpointing mechanism.
 Transfer of the title of being the real group must be a one-time only thing
 for each version of the group, and must be impossible to backtrack from.
 Bitcoin enforces this by design.


If you are worried about Synchronization issues within the band itself: I
don't need Bitcoin to solve it. The Band is small, and it has a majority of
correct members.
Therefore I can use some secure multiparty computation to take decisions
within the band, and also remove and add members securely.

I think you overestimate the impact of using Bitcoin.


My problem was that the naive solution makes every band keep a linear
amount of signatures with respect to time, which is too much.
As a solution you proposed Bitcoin, where all the network participants will
remember everything from the beginning of time. That's the opposite of what
I'm trying to do.

I made sure that every operation in the network result in no more than
O(polylog(n)) operations. I am definitely not going to use Bitcoin on it,
where every transaction costs O(n) network complexity.
(Not mentioning the proof of work calculations). It doesn't make sense to
me.

It isn't all our nothing as not all members need to be full nodes, in fact
 none of them have to be.


What if everyone did that?  Bitcoin will stop working properly. (Or it will
become central, and that is what Bitcoin tries to avoid from the first
place.)

The Bitcoin developers is constantly working on scalability, and the
 network is meant to one day be able to handle thousands of transactions per
 second


I It might be true, but it is still O(n) network complexity per
transaction, and lots of proof of work calculations.
The naive solution proposed in my first message will still outperform the
most efficient Bitcoin based solution. (Because it is O(log(n)) network
complexity).




On Thu, Jan 8, 2015 at 1:12 PM, Natanael natanae...@gmail.com wrote:

 Den 8 jan 2015 11:54 skrev realcr rea...@gmail.com:
 
  Hey, thanks again for the reply.
 
  The only notable difference is that in my version you are checkpointing
 the change in th blockchain.
 
  You still have the very same form of signing, but you sign a slightly
 different message (transfer of a colored coin, one Satoshi worth of
 Bitcoin, to a new address) instead of group members XYZ are now the
 official group instead of ABC.
 
 
  I disagree with you, or maybe I have misunderstood you idea. I think
 that Bitcoin is not related here.
 
  Bitcoin is all or nothing. If I want to use it, all the participants of
 the network have to be part of it.
  That means that all the participants of the network have to compute
 hashes all the time.
  In addition, every Bitcoin transaction involves all the participants of
 the network.

 I think you overestimate the impact of using Bitcoin. It isn't all our
 nothing as not all members need to be full nodes, in fact none of them have
 to be. While it is true that all full nodes must store all the
 transactions, and that it gets forwarded in the network among most online
 nodes as it gets published, only the latest one would need to be kept in
 their index of the unspent outputs (UTXO set) from the blockchain. The
 Bitcoin developers is constantly working on scalability, and the network is
 meant to one day be able to handle thousands of transactions per second
 (this is years off, though). The blockchain can easily be stored on MicroSD
 cards!

 Verifying the headers alone for decades worth of hashes takes at most
 minutes on smartphones. And that's a one-time job per header hash, per
 device. Each new header takes much less than a second to process.
 Publishing and verifying the colored coin transactions is trivial too.

  Secrecy is not required. I meant to say that the band has the
 responsibility of keeping the signatures and show them on demand.

 You still don't get any meaningful security if old band members are
 assumed to be untrusted and you don't use a public checkpointing mechanism.
 Transfer of the title of being the real group must be a one-time only thing
 for each version of the group, and must be impossible to backtrack from.
 Bitcoin enforces this by design.

 Other standard public checkpointing mechanisms don't verify if there's
 conflicting messages or not, so then ALL messages that has been
 checkpointed must be stored.

 There are cryptocurrencies with similar functionality (doublespend
 protection, conflicting assignments not allowed) and other trust models (no
 proof-of-work for chain selection). As an example, Ripple is federated, a
 set of trusted nodes agree on the order of transactions. This removes most
 of your performance related issues. But I don't trust it if security is
 important, it seems too ad-hoc. Then there's proof-of-stake which is very
 problematic for a million different reasons (no guarantee there will be
 concensus), but 

Re: [cryptography] The Wandering Music Band

[Michael Rogers]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA256

On 08/01/15 07:03, realcr wrote:
 I think the naive solution I proposed in my first message is more 
 efficient than using Bitcoin, because it does not involve proof of
 work or flooding stuff.
 
 Shortly: Whenever a person is added to the band, all the members
 sign on the new list. Whenever a member leaves the band, all the
 members sign on the new list. The band members keep the signatures
 forever, so they can always prove they where formed originally from
 the original band S.

I think there might be a problem if a majority of members leave the
band one by one and then construct an alternative history:

band_0 = {a,b,c,d}  // original lineup
band_1 = {a,b,c}// d leaves
band_2 = {a,b,c,e}  // e joins
band_3 = {a,b,e}// c leaves
band_4 = {a,b,e,f}  // f joins
band_5 = {a,e,f}// b leaves
band_6 = {a,e,f,g}  // g joins

Now the original members b,c,d create an alternative history:

band_0 = {a,b,c,d}  // original lineup
band_1' = {b,c,d}   // a leaves
band_2' = {b,c,d,h} // h joins

Which is the true lineup, band_6 or band_2'?

A verifier who's seen both histories can tell that b and c have signed
inconsistent statements. But how can a verifier know whether they've
seen all histories that might exist?

Cheers,
Michael
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJUrnpiAAoJEBEET9GfxSfMEqIIAK8ZHAE4XzAmVYg3A7z2kWJA
mUHNoNMHf7198NLH9ddMrLOmKbGYWRko/6VY6dStx8Na3E0O1nAZVO2vdK9oTlBJ
v6O6mmgAuAnG4oKAn3+KQHhGIxIUmsOn7vHTgF6X6l7JlgEnEhwNQ2GZ5azbyEnb
iSxAjy1cnH4uWV8On8nFrBRfv1BkcizoclX1hBxF9b2v0+psNLbS0/EIFuGkonfx
CYGRC117saH9t//kwEZEAk2b8PeNENb/memS4beBJdQNe0oMaiKV/rxXgf2IwnpX
1AdDopBU84EnICiwuB8lwSqhdlKBO07fJ6Slki/l6Fjie9lUlFU/4+rpSNQnzOE=
=98M3
-END PGP SIGNATURE-
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[realcr]

Hey, thanks again for the reply.

 The only notable difference is that in my version you are checkpointing
 the change in th blockchain.

 You still have the very same form of signing, but you sign a slightly
 different message (transfer of a colored coin, one Satoshi worth of
 Bitcoin, to a new address) instead of group members XYZ are now the
 official group instead of ABC.


I disagree with you, or maybe I have misunderstood you idea. I think that
Bitcoin is not related here.

Bitcoin is all or nothing. If I want to use it, all the participants of the
network have to be part of it.
That means that all the participants of the network have to compute hashes
all the time.
In addition, every Bitcoin transaction involves all the participants of the
network.

Assume that there are n participants in the network, and k band members.
using Bitcoin, every change in the band involves O(n) network complexity,
O(n) memory usage to the network (Every participant in the network has to
remember O(1) more data).
I can't really talk about computational complexity here, as the Bitcoin
algorithm never really terminates. We can just say that it costs a lot of
computational power.

In the proposed naive solution, every time a change happens, the band S has
to remember a few more signatures. (About O(k)).
So every change requires O(poly(k)) network complexity (Some protocol
between the band members), O(poly(k)) memory usage to the network (Each of
the band members should remember all the signatures),
and O(poly(k)) computational power (For generating the signatures, and
protocol between the band members).
In my case k is pretty small (You may assume k = O(logn)).

I think that the naive solution outperforms Bitcoin in every way in this
case. Correct me if I'm wrong here.

 The band S doesn't publish the signatures. They only show the signatures
 whenever I ask them.

 Is secrecy a requirement? If so, take a look at Zerocoin/Zerocash (not yet
 released, though). It uses Zero-knowledge proofs for secure mixing of
 coins to preserve privacy. You could also chose to have the group
 periodically rekey and transfer the colored coin even if there's no change,
 just to hide when the change actually happens.


Secrecy is not required. I meant to say that the band has the
responsibility of keeping the signatures and show them on demand.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[Natanael]

Den 8 jan 2015 08:03 skrev realcr rea...@gmail.com:

 Hey Natanael, Thanks for your response.


 It's the chain of signatures always published in an accessible way so
that the original members can't doublespend and claim to be the task
group? Otherwise the blockchain approach is useful for you.


 I think the naive solution I proposed in my first message is more
efficient than using Bitcoin, because it does not involve proof of work or
flooding stuff.

The only notable difference is that in my version you are checkpointing the
change in th blockchain.

You still have the very same form of signing, but you sign a slightly
different message (transfer of a colored coin, one Satoshi worth of
Bitcoin, to a new address) instead of group members XYZ are now the
official group instead of ABC.

 The band S doesn't publish the signatures. They only show the signatures
whenever I ask them.

Is secrecy a requirement? If so, take a look at Zerocoin/Zerocash (not yet
released, though). It uses Zero-knowledge proofs for secure mixing of
coins to preserve privacy. You could also chose to have the group
periodically rekey and transfer the colored coin even if there's no change,
just to hide when the change actually happens.

 The group setting is also solved as-is thanks to both the multisignature
support (m-of-n for up to 15 people), and thanks to ECDSA threshold group
signatures if you prefer these (I'm assuming they also don't limit you to
15 members).

 Using a multisignature scheme I can probably get much shorter signatures,
which is cool.
 I will still have to remember the identities of all the signers, and the
set of signatures to be remembered grows linearly with respect to time.

If you're willing to involve custom Zero-knowledge proofs, you could
generate one showing that a valid chain of signatures exists between the
first and last group. Generating it is essentially O(n), verification is as
good as O(1).

This approach also works with the blockchain such that a person who knows
the current blockchain headers and the first colored coin transaction only
needs to be shown the latest colored coin transaction plus the
Zero-knowledge proof (chaining together multiple ZKP's can make this
O(log(n)) over long periods of time).

Telling them directly what exact block the latest transaction is in means
they just have to look up the Merkle tree hash in that block header from
their index, confirm that the given colored coin transaction is in there
and that the ZKP is valid. To be sure there's been no more recent transfer
of the coin, they look in their Bitcoin blockchain index (one database
lookup of a hash, for full nodes) or ask other nodes if the coin has been
moved yet or not (for lightweight SPV nodes).

Then they proceed as before, show what the address is composed of and prove
they have a private key that is a member of the group.

 Assuming that I use some kind of Threshold signature scheme, how can I
transfer the secret parts to the next members in the band, so that parts of
the secret don't leak to previous members?
 Most of what I read about threshold signatures assumes that some that
some trusted dealer deals the secret parts to the participants.
 How can I move the secret parts to the new band without a trusted dealer?

Don't move it, don't forward shares. Create a new group public key. All
members have one unique share that they are supposed to never reveal. Each
version of the group combine the shares of those members to create their
public key.

 Someone in this thread has mentioned Shamir secret sharing. Considering
this idea,

Insufficient, you need to recover the plaintext at some point with trusted
hardware and trusted users.

 How can I avoid the possibility that some set of corrupt ex-band members
will gather and combine their secret parts?

This is essentially the doublespend problem in cryptocurrencies. The status
of being the right descendant of the group can be represented by a token
which must not be duplicated or claimed to be passed on to multiple groups
(conflicting doublespends). Bitcoin tracks it by enforcing one and only one
official self consistent version of events in the blockchain.

You can only prevent old members from claiming to be the real group by
making some kind of checkpointing information public, with trusted
timestamps. (Unless you forcefully delete their private keys, which is
nearly impossible unless only stored on trusted hardware like a HSM.)

If you only publish hashes to keep the activity secret until it has to be
used, then each member must remember all key activity that's been
checkpointed to show exactly what all hashes represent to prove that
they're the legitimate descendant. All group members MUST at all times
agree on ONE AND THE SAME official public chain of commitments which
represent the official chain of events.

If previous members can not be fully trusted, you CAN NOT rely on any
non-public activity that can be repeated in contradicting ways. Using
one-time 

Re: [cryptography] The Wandering Music Band

[Natanael]

Den 8 jan 2015 11:54 skrev realcr rea...@gmail.com:

 Hey, thanks again for the reply.

 The only notable difference is that in my version you are checkpointing
the change in th blockchain.

 You still have the very same form of signing, but you sign a slightly
different message (transfer of a colored coin, one Satoshi worth of
Bitcoin, to a new address) instead of group members XYZ are now the
official group instead of ABC.


 I disagree with you, or maybe I have misunderstood you idea. I think that
Bitcoin is not related here.

 Bitcoin is all or nothing. If I want to use it, all the participants of
the network have to be part of it.
 That means that all the participants of the network have to compute
hashes all the time.
 In addition, every Bitcoin transaction involves all the participants of
the network.

I think you overestimate the impact of using Bitcoin. It isn't all our
nothing as not all members need to be full nodes, in fact none of them have
to be. While it is true that all full nodes must store all the
transactions, and that it gets forwarded in the network among most online
nodes as it gets published, only the latest one would need to be kept in
their index of the unspent outputs (UTXO set) from the blockchain. The
Bitcoin developers is constantly working on scalability, and the network is
meant to one day be able to handle thousands of transactions per second
(this is years off, though). The blockchain can easily be stored on MicroSD
cards!

Verifying the headers alone for decades worth of hashes takes at most
minutes on smartphones. And that's a one-time job per header hash, per
device. Each new header takes much less than a second to process.
Publishing and verifying the colored coin transactions is trivial too.

 Secrecy is not required. I meant to say that the band has the
responsibility of keeping the signatures and show them on demand.

You still don't get any meaningful security if old band members are assumed
to be untrusted and you don't use a public checkpointing mechanism.
Transfer of the title of being the real group must be a one-time only thing
for each version of the group, and must be impossible to backtrack from.
Bitcoin enforces this by design.

Other standard public checkpointing mechanisms don't verify if there's
conflicting messages or not, so then ALL messages that has been
checkpointed must be stored.

There are cryptocurrencies with similar functionality (doublespend
protection, conflicting assignments not allowed) and other trust models (no
proof-of-work for chain selection). As an example, Ripple is federated, a
set of trusted nodes agree on the order of transactions. This removes most
of your performance related issues. But I don't trust it if security is
important, it seems too ad-hoc. Then there's proof-of-stake which is very
problematic for a million different reasons (no guarantee there will be
concensus), but the network performance issues from Bitcoin remains here.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[realcr]

 Now the original members b,c,d create an alternative history:


I assume that the original band has a majority of correct members.
Therefore at least two out of {b,c,d} are correct, and they will not create
alternate history.

The original formulation is included:

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.




On Thu, Jan 8, 2015 at 2:38 PM, Michael Rogers mich...@briarproject.org
wrote:

 -BEGIN PGP SIGNED MESSAGE-
 Hash: SHA256

 On 08/01/15 07:03, realcr wrote:
  I think the naive solution I proposed in my first message is more
  efficient than using Bitcoin, because it does not involve proof of
  work or flooding stuff.
 
  Shortly: Whenever a person is added to the band, all the members
  sign on the new list. Whenever a member leaves the band, all the
  members sign on the new list. The band members keep the signatures
  forever, so they can always prove they where formed originally from
  the original band S.

 I think there might be a problem if a majority of members leave the
 band one by one and then construct an alternative history:

 band_0 = {a,b,c,d}  // original lineup
 band_1 = {a,b,c}// d leaves
 band_2 = {a,b,c,e}  // e joins
 band_3 = {a,b,e}// c leaves
 band_4 = {a,b,e,f}  // f joins
 band_5 = {a,e,f}// b leaves
 band_6 = {a,e,f,g}  // g joins

 Now the original members b,c,d create an alternative history:

 band_0 = {a,b,c,d}  // original lineup
 band_1' = {b,c,d}   // a leaves
 band_2' = {b,c,d,h} // h joins

 Which is the true lineup, band_6 or band_2'?

 A verifier who's seen both histories can tell that b and c have signed
 inconsistent statements. But how can a verifier know whether they've
 seen all histories that might exist?

 Cheers,
 Michael
 -BEGIN PGP SIGNATURE-
 Version: GnuPG v1.4.12 (GNU/Linux)

 iQEcBAEBCAAGBQJUrnpiAAoJEBEET9GfxSfMEqIIAK8ZHAE4XzAmVYg3A7z2kWJA
 mUHNoNMHf7198NLH9ddMrLOmKbGYWRko/6VY6dStx8Na3E0O1nAZVO2vdK9oTlBJ
 v6O6mmgAuAnG4oKAn3+KQHhGIxIUmsOn7vHTgF6X6l7JlgEnEhwNQ2GZ5azbyEnb
 iSxAjy1cnH4uWV8On8nFrBRfv1BkcizoclX1hBxF9b2v0+psNLbS0/EIFuGkonfx
 CYGRC117saH9t//kwEZEAk2b8PeNENb/memS4beBJdQNe0oMaiKV/rxXgf2IwnpX
 1AdDopBU84EnICiwuB8lwSqhdlKBO07fJ6Slki/l6Fjie9lUlFU/4+rpSNQnzOE=
 =98M3
 -END PGP SIGNATURE-

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[realcr]

 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

Re: [cryptography] The Wandering Music Band

[Michael Rogers]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA256

On 08/01/15 13:21, realcr wrote:
 Now the original members b,c,d create an alternative history:
 
 
 I assume that the original band has a majority of correct members. 
 Therefore at least two out of {b,c,d} are correct, and they will
 not create alternate history.

Sorry, I should've read your formulation more carefully. But as
Natanael pointed out, the same problem exists if any version of the
band contains a dishonest majority.

(I don't necessarily agree that Bitcoin in the only answer, but I
can't see another answer.)

Cheers,
Michael
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJUrp15AAoJEBEET9GfxSfME6wH/2AGTz/xH0aRtAMxeWIgu6Ie
xXxt+uL/4JhpZWEnCK+SYXmoKLh9OLJVSVUw2U1mcA1pZdj/KGk1RnLerU+w8D5c
e8FwvrNsVqPMLjwYRtrNXJje9UJlRLti1jlZxchg4Xj6gYWpuS8lJev2bT6He7aj
ylhiBvhzvvdTYzC1iA9yNOpxM4dGHWWXuj/sUUWvPVHEIpG7iQPs9XH/pYOTbLJU
NNzNjYwkObJvGCgo20dHlQ2+Vr7UNLk6O+ZXZvZORfSlEgnKLF7/HUTrTRTxsjnO
7Iy7gFbmHswnWWeaa3DGl9xoJxHpZJoCMNshYdAuEYOykulPyqqw9KOEtgcxxmk=
=Gvzr
-END PGP SIGNATURE-
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[realcr]

Hey Natanael, Thanks for your response.


 It's the chain of signatures always published in an accessible way so that
 the original members can't doublespend and claim to be the task group?
 Otherwise the blockchain approach is useful for you.


I think the naive solution I proposed in my first message is more efficient
than using Bitcoin, because it does not involve proof of work or flooding
stuff.

Shortly: Whenever a person is added to the band, all the members sign on
the new list. Whenever a member leaves the band,
all the members sign on the new list. The band members keep the signatures
forever, so they can always prove they where formed originally
from the original band S.

Example:

If the original band, band_0 = {a_0,a_1,a_2,a_3}, and a new member (a_4)
joins, we get a new band {a_1,a_2,a_3,a_4}.
If we denote the new list as band_1 := (a_0, a_1,a_2,a_3,a_4) then we need
the following signatures to prove the change:

sign[a_0](band_1), sign[a_1](band_1), sign[a_2](band_1), sign[a_3](band_1)

If the member a_1 now leaves the band, we denote band_2 =
(a_0,a_2,a_3,a_4), and we need the following signatures to prove the change:
sign[a_0](band_2), sign[a_2](band_2), sign[a_3](band_2), sign[a_4](band_2)
(Note that we might not be able to get a_1's signature, because maybe he
just failed somehow).

So far, after those two changes, we have to carry about 8 signatures.
If someone asks the group to prove that they have a majority of correct
nodes, they can just prove their current
identities, and send the 8 signatures.
(I can probably get away with less than 8 signatures, but the asymptotic
nature of the amount of signatures needed doesn't really change).

The band S doesn't publish the signatures. They only show the signatures
whenever I ask them.

The group setting is also solved as-is thanks to both the multisignature
 support (m-of-n for up to 15 people), and thanks to ECDSA threshold group
 signatures if you prefer these (I'm assuming they also don't limit you to
 15 members).


Using a multisignature scheme I can probably get much shorter signatures,
which is cool.
I will still have to remember the identities of all the signers, and the
set of signatures to be remembered grows linearly with respect to time.

Assuming that I use some kind of Threshold signature scheme, how can I
transfer the secret parts to the next members in the band, so that parts of
the secret don't leak to previous members?
Most of what I read about threshold signatures assumes that some that some
trusted dealer deals the secret parts to the participants.
How can I move the secret parts to the new band without a trusted dealer?

Someone in this thread has mentioned Shamir secret sharing. Considering
this idea,
How can I avoid the possibility that some set of corrupt ex-band members
will gather and combine their secret parts?
​
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[realcr]

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

Re: [cryptography] The Wandering Music Band

[Natanael]

Den 7 jan 2015 22:14 skrev realcr rea...@gmail.com:

 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.

It's the chain of signatures always published in an accessible way so that
the original members can't doublespend and claim to be the task group?
Otherwise the blockchain approach is useful for you.

The Bitcoin blockchain solves the problem of trustlessly transferring
ownership. The group setting is also solved as-is thanks to both the
multisignature support (m-of-n for up to 15 people), and thanks to ECDSA
threshold group signatures if you prefer these (I'm assuming they also
don't limit you to 15 members).

Group S_1 creates a colored coin by sending the smallest denomination of
Bitcoin to an address created using the public keys of all current members
(must not be mixed with other coins). The threshold is defined such that m
must be larger than half of n (the size of the group).

When any change is made, group S_2 is then created and the colored coin is
sent to a new address created from the public keys of all members in this
new group, and the threshold is adjusted if necessary.

Keeping only the blockchain headers and asking Bitcoin nodes for the
transactions following the original colored coin transaction (SPV security
model), you can track it to the latest address, and thus to the latest
version of the group, the current descendant (S_n).

You can verify that the group member(s) you meet is indeed part of the
current version of the group by asking them to sign a nonce as a challenge
with their private key and show the rest of the public keys from the group
(such that the Bitcoin address can be recreated, to verify his public key
is part of the group).
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[Warren Kumari]

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

Re: [cryptography] The Wandering Music Band

[Dave Horsfall]

On Wed, 7 Jan 2015, realcr wrote:

 I am looking for some crypto primitive to solve a problem I have.

[...]

Fascinating...  If it helps, I know a couple of musos who are in that 
position, and also have a geeky bent, so I'll pass along anything that 
they may have to say.

Deep Purple would have some difficulty, of course (I think Jon Lord was 
the last founding member, and he left), but Led Zeppelin would have no 
problem (when Bonzo dropped out, so did they, but Jason -- his son -- has 
done a gig or two since then).

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.

-- 
Dave Horsfall DTM (VK2KFU)  Bliss is a MacBook with a FreeBSD server.
http://www.horsfall.org/spam.html (and check the home page whilst you're there)
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Wandering Music Band

[andrew cooke]

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