How to generate a distributed private key?

Question

Shamir's Secret Sharing scheme is really interesting but the pain point is that the secret is generated by one trusted party, then the shares are distributed to other peoples.

Is there any scheme using distributed key generation in order to:

Generate a public key using multiple private keys

Generate a private key using a threshold of shared private keys

The private key is generated in a distributed way

I learned about DKG ( https://github.com/dfinity/dkg/blob/master/example.js )

Answer 1

Here's a paper that talks about a pre-commit DKG in detail https://eprint.iacr.org/2019/114.pdf. It also includes some repudiation and decommitment features.

As a summary, each party does these steps:

1. roll a random number
2. publish the hash of (some dlp-hard-group-generator to the power of that random number)
3. after you get everyone's hashes, publish g to the power of that random number along with a signature, using g, proving ownership of that same random number
4. as long as everyone's hashes match up, compute the LagrangeSum(g) for the group
5. now you have a distributed M-Of-M key, and a public key corresponding to it, and a proof-of-secret key too. any dishonest players result in the whole protocol failing
6. you can redistribute this key to M-Of-N players using VSSS.

A more broadly referenced solution is the ECDKG here:

https://pdfs.semanticscholar.org/3c52/35523be1d305de6dbf3433965c99d9fe4aea.pdf

Which relies on publishing and verifying commitments to polynomial coefficients, and secret communications between parties to ensure sharing was done correctly. It is more robust to dishonest players, and ultimately works in 2 rounds for M of N instead of the 3 rounds (above).

IMO, the pre-commitment scheme is both easier to understand and easier to get right.