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 from points . Given a set of points, first compute the Lagrange basis corresponding to each point as:

The resulting Lagrange interpolating polynomial is:

Shamir Secret Sharing With Trusted Dealer

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

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, dealer evaluates the points and then distributes the evaluations as the secret shares to each party. Since none of the key share holders have knowledge of , none of them can actually calculate alone.

To recover from only party shares, choose a quorum with and use the Lagrange basis polynomials defined above.

Exploiting Lagrange interpolation, the parties can recover the original polynomial that the dealer created. However, we are only interested in calculating , so we evaluate the basis polynomials at :

The secret is then reconstructed directly as:

Hence we have recovered with contributions from only of parties. All arithmetic is performed in the finite field used for secret sharing.

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 degree polynomial :

The constant terms of these polynomials are each party's contribution towards the final secret .

Now each party calculates the evaluations:

Then privately sends to party (where ) and keeps (i.e ) to itself for the next step. Remember no party has the knowledge of another party's polynomial.

After each party has received evaluation from other party , the secret share of party is the sum of these evaluations including evaluation of its own:

It works because the eventual result is the same as performing the SSS ceremony with a polynomial that is the sum of all parties' randomly chosen polynomials:

The final secret is the constant term of this aggregate polynomial:

This is our distributed key generation scheme.