Another conundrum..

[Inca]

Let's say i have 10 parties each holding an ECDSA keypair who each securely send me a public key.

I create a newly generated random ECDSA private key and want to break it up into 10 pieces and send it back to them encrypted with their personal public key. Thus only they are able to decrypt the key back to an unencrypted partial private key status.

Now the question I have is what known effective ways are there of distributing the key piecemeal or jumbled such that no individual party can reassemble the key, but that in the event of a number of parties failing to respond to a request to return the piecemeal fragment it is still possible to restore the key from say 5 honest parties?

 

[Bagatell]

What is the use case for this?

 

[Inca]

Just for my own amusement I am creating a protocol for a p2p based market place which is capable of allowing the buying and selling of digital media in a trustless and secure fashion.

Data, encryption keys and bitcoin private keys are distributed amongst nodes to prevent theft and nodes are incentivised to remain online and honest by receiving a sliver of each transaction fee.

I have a functional protocol but keep updating it as I encounter a new idea or solution to a problem.

 

[sickpig]

@Inca cool project indeed!

Do you think that your project as some significant common ground with openbazaar?

 

[Inca]

I am doing this for my own entertainment so open bazaar is almost certainly technically more accomplished - i haven't looked at it in any detail

ill post my efforts on here in a day or two for some high brow critique

 

[Peter R]

Now the question I have is what known effective ways are there of distributing the key piecemeal or jumbled such that no individual party can reassemble the key, but that in the event of a number of parties failing to respond to a request to return the piecemeal fragment it is still possible to restore the key from say 5 honest parties?

The appropriate technique to use is Shamir's Secret Sharing. In your case, n=10 and k=5, meaning that you'd give parts of the secret to 10 people but only 5 of those parts would be required to re-assemble the secret.

I create a newly generated random ECDSA private key and want to break it up into 10 pieces and send it back to them encrypted with their personal public key. Thus only they are able to decrypt the key back to an unencrypted partial private key status.

Perhaps you misspoke, but you can't really encrypt something with their personal pubkey. You should use the elliptic curve Diffie-Hellman instead (which is just their personal pubkey multiplied by your private key [which they can reconstruct because it is also equal to your pubkey multiplied by their privkey]).

 

[Inca]

Shamir Secret Sharing is exactly what I needed thank you Peter R.

Using Dennis Mckinnon's excellent ShamirSS implementation of this scheme for python (with base58 support for bitcoin private keys) yields the following..

>>> priv = random_key()
>>> share = []
>>> share = ShSS.split(10,5,priv)
>>> for x in range(0,4):
... share.pop()
>>> priv1 = ShSS.recover(share)
>>> priv
'43c80c74c4bc4f52faf1ff5f734c713bba5b653bc8c588d8138fe5b79e7268dc'
>>> priv1
'43c80c74c4bc4f52faf1ff5f734c713bba5b653bc8c588d8138fe5b79e7268dc'