On Distributed Key Generation

Introduction

Distributed key generation is an interesting key generation mechanism that exploits the Shamir Secret Sharing (SSS) scheme in a nested manner to create a ceremony where no trusted dealer is required to generate the actual shares of a private key.

Lagrange Interpolation

SSS exploits Lagrange interpolation, which states that one can uniquely determine a polynomial of degree at most from points. Let be the set of indices of those points. The Lagrange basis polynomial for party is:

The interpolating polynomial is then:

Hence, we have derived a unique polynomial of degree at most from the points. is called the Lagrange interpolating polynomial.

Shamir Secret Sharing With Trusted Dealer

Before we move on to the DKG, consider that a trusted dealer generates a random polynomial of degree at most :

where is the secret key that is to be split and distributed, and are chosen randomly. Thus, is the constant term of the polynomial and is known to the dealer.

For each of the secret share holders, the dealer evaluates a share for each party , with a chosen distinct non-zero . Then dealer distributes the party its share . Since none of the share holders have knowledge of , none of them can actually calculate alone.

To recover from party shares, choose a quorum with . Lagrange interpolation recovers the dealer's original polynomial:

However, reconstruction only needs the constant term . Each participant contributes its share weighted by:

Here, the Lagrange coefficient is:

(The value is party 's share, not its secret.)

After all contributing participants provide their weighted shares, the secret is recovered as:

Thus secret is recovered from shares only.

Distributed Key Generation

In DKG, we remove the role of the dealer entirely. Instead, only share holders participate in a key-generation ceremony to eventually calculate the shares of a private key unknown to all parties.

This time, instead of a dealer randomly generating a degree- polynomial, each party randomly generates its own polynomial of degree at most :

For reasoning about the resulting shares, define the aggregate polynomial:

Performing DKG is equivalent to performing a SSS with as the polynomial that is chosen by dealer. But as we can see, no one entity knows more than one of the functions .

The final secret is the sum of the constant terms of the individual polynomials:

Party privately sends party the evaluation and keeps for itself. After party has received one evaluation from every party, its final secret share is:

Thus, each party has received their secret shares.

It works because the eventual result is the same as performing the SSS ceremony with function .

The recovery of the secret works the same as before with SSS since all of the principles apply to polynomial and secret shares generated.