http://point-at-infinity.org/ssss/Perhaps Shamir's secret sharing scheme may work to do a m-of-n where m<n for a transaction where you want majority of votes.
Situation:
someone makes a bitcoin address with priv key K
he then proceeds to use SSSS in m-of-n scheme with the private key;
then since you'll need m keys to get the priv key K to spend any funds sent to the bitcoin address.
Problems that arise from this solution:
any not known vulnerability of SSSS
trust is spread at the agent that generated the priv key K
this would really be like a bruteforce, perhaps anyone can find this ideas useful or the SSSS;
my 0.01
BTC There seem to be a few possible different approaches to using threshold schemes with bitcoin.
1) Multiparty threshold signatures which are built in to the bitcoin protocol such as P2SH.
2) Threshold signature schemes based on the signature algorithms such as the Schnorr scheme (if Schnorr, hopefully, becomes a part of the bitcoin protocol) and the ECDSA scheme (link in post #8).
3) Secret sharing schemes - the private key is the shared secret.
(this is just the way I prefer to categorise them)
The first two methods enable signers above a certain threshold to produce a signature for a transaction.
The secret sharing schemes allow participants above a certain threshold to create the private key.
In most secret sharing schemes such as the original Shamir scheme there is a dealer who knows the secret and deals out the shares to the participants but there are methods that have no dealer (nobody knows the secret until it is actually reconstructed by enough participants). Clearly having a dealer who knows the ‘secret’ private key is not a good method for bitcoin but if it is a type of no dealer scheme then I think there are situations where there might be reasons for this approach.
I believe it is very difficult to perform most secure multi-party computations without the participants having direct communication with each other which makes it much more difficult as more participants are introduced.
As adam3us pointed out the bitcoin multi-sig may have additional functionality in cases where we want to identify signers. However another multi party signature scheme based around the signature algorithm might be more desirable for some other application. Say, for example, if you wanted to design some type of linkable ring signature.
I suppose that each method must be considered according to it’s application.
In reality nearly all current applications will use the the bitcoin P2SH threshold (multi-sig) method but we have, incidentally, just built a django web app for negotiating the terms of a 2 of 3 escrow type contracts and incorporated a different threshold scheme. For various reasons particular to the simple (2 of 3 escrow) web application we are trying to implement we don’t currently use the signature schemes but use a type of 'shared secret' private key.
I’ll post the protocol in a separate thread for comments/questions.
