What is Distributed Key Generation (DKG)?

In past articles, we've explained how you can create shares and do arithmetic with those shares. Through worked examples, you've gotten a sense of how you may be able to use the basics of MPC for your needs. However, it still feels very abstract. So this is a good time to introduce a real use case of MPC for which we have a solution: distributed key generation (DKG). In this article, we will go through a very simple and naive DKG protocol.

Say you and your friends want to share a cryptocurrency wallet (or a GitHub SSH key, same idea). However, the homies aren't together to generate a key and then split it into shares. So you want a way to generate a shared key without any single person ever holding the whole thing. A threshold of the friend group should be able to reconstruct the key.

This scenario mimics quite a few real world use cases. Distributed key generation is useful for:

• Generating new cryptocurrency wallets without having the full private key in one place

• Changing the shares for a secret-shared secret without changing the underlying secret, known as share refreshing

• Replacing the dealer in MPC protocols

For the purposes of this article, we will solely focus on keys such as those found in public/private key cryptosystems. However, the concepts here can apply to any underlying secret that isn't a key.

More formally, we are looking to compute key ← rG where r is a random integer in ℤ and G is some generator. Specifically, in MPC, we want to actually compute [r]G. If you've read our previous articles, you have more than enough knowledge to be able to do this.

Fundamentally, we are simply generating [r]. Since G is a known scalar element, [r]G is simply scalar multiplication by a public constant. So, it suffices to show how to get [r].

Explicitly, the protocol works as follows:

1. Each party generates their own randomness rᵢ, say through using a TRNG or /dev/urandom on their local machines.

2. They secret share to the other parties the rᵢ to get [rᵢ]. So party i has their own rᵢ and other parties' [rⱼ] for parties j not equal to i.

3. In order to get [r], each party computes Σ[rᵢ]. Since addition is linear over secret shares, the summation requires no communication among the parties.

4. Then each party can compute [r]G themselves.

Voila, we've generated a key in a distributed fashion.

Let's make that concrete. Work in ℤ₁₇ with 3 parties and threshold 2, so everyone shares with a degree 1 polynomial.

• Party 1 picks r₁ = 5, polynomial f₁(x) = 5 + 3x. Shares: f₁(1) = 8, f₁(2) = 11, f₁(3) = 14

• Party 2 picks r₂ = 11, polynomial f₂(x) = 11 + 7x. Shares: f₂(1) = 1, f₂(2) = 8, f₂(3) = 15

• Party 3 picks r₃ = 9, polynomial f₃(x) = 9 + 2x. Shares: f₃(1) = 11, f₃(2) = 13, f₃(3) = 15

Each party sums the shares they received:

• Party 1: 8 + 1 + 11 = 20 = 3 (mod 17)

• Party 2: 11 + 8 + 13 = 32 = 15 (mod 17)

• Party 3: 14 + 15 + 15 = 44 = 10 (mod 17)

These are exactly shares of f(x) = 8 + 12x, whose constant term is r = 5 + 11 + 9 = 25 = 8 (mod 17). Any two parties can interpolate and recover r = 8, and each party can compute their share times G to jointly derive the public key rG. Nobody ever saw r.

Notice several things about this protocol:

• No communication needed among the parties beyond sending the shares of rᵢ

• Assumes a synchronous network

• Assumes all parties are semi-honest

In practice, networks are messy, and unpredictable. Our Asynchronous DKG solution solves for the setting where the network is asynchronous and parties can be malicious. Schedule your demo today to distribute your secrets