3
$\begingroup$

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 )

$\endgroup$
  • 1
    $\begingroup$ For asymmetric cryptography, usually the public key is derived from the private key, so at least this part is solved.. $\endgroup$ – gusto2 Aug 28 '18 at 13:26
  • $\begingroup$ This is an instance where what you really need is distributed randomness. But it depends on the cryptosystem: RSA keys are not generated like discrete log-based keys... Also, here is a relevant paper on the latter. $\endgroup$ – Lery Aug 28 '18 at 14:06
  • $\begingroup$ @Lery yes, RSA keys are no like DL, still can be generated in distributed manner. $\endgroup$ – Vadym Fedyukovych Aug 29 '18 at 20:31
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.