[cryptography] The Wandering Music Band

Natanael natanael.l at gmail.com
Thu Jan 8 05:11:23 EST 2015

Den 8 jan 2015 08:03 skrev "realcr" <realcr at 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 signatures could discourage attempts, but this would allow for
sabotage unless you use public checkpointing (and using public
checkpointing makes one-time signatures unnecessary).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150108/afb2b088/attachment-0001.html>

More information about the cryptography mailing list