Walking Through Distributed Key Generation (DKG)

This post is a follow-along to a talk on Distributed Key Generation at DevConnect, Amsterdam 2022 (slides here). It also functions as a stand-alone resource.

The post is intended to briefly introduce the motivation for threshold signatures, relating them to multisignatures, and clarify a Distributed Key Generation protocol introduced by cryptographer Torben Pedersen in 1991, and applied by Gennaro and Goldfeder in their threshold scheme, GG20, S3.1, p14.

Implementing the GG20 protocol has been a core component of my work at Entropy, the trustless decentralized asset custodian.

A mathematically complete description of the protocol begins in the latter half of the document; the first half remains technically high level, and should be accessible to non-technical readers.

Questions and corrections are invited via Twitter.

Knowledge Check!

It will be helpful to be familiar with several concepts:

• Langrange interpolation, on which Shamir Secret Sharing relies
• Shamir Secret Sharing Scheme
• Commitment Schemes, in particular Pedersen’s Commitment Scheme

(everything in cryptography is a scheme, except for programs which are invariably in Rust)

Each have reasonably good Wikipedia articles.

Pallier encryption, Schnorr’s zk proof of knowledge of exponent, and the Feldman modification to Shamir secret sharing, which are used in the signing protocol, will not be necessary here.

What Threshold Signature? And Briefly, What Multisignatures

A t-of-n secret sharing of some secret $u$ produces $n$ “shares” of $u$, of which any $t+1$ can reconstruct $u$. There is some notation confusion whether t-of-n should refer to a minimum of $t+1$ parties or $t$ parties; $t+1$ is the convention used by GG20, so we will use it here.

A similar construction to the threshold signature is the t-of-n multisignature:

• $n$ parties hold private keys
• Some trusted entity (eg. a smart contract) collects $t+1$ unique signatures on some message, (eg. a transaction), and then signs that message itself

In a t-of-n threshold signature:

• Key Generation: Some secret key $u$, secret to all parties, is constructed. At the end of a DKG, every party possesses some secret share from which $u$ may be reconstructed. No party knows another party’s share.
• Any $t+1$ parties can collaborate to sign a message, producing a single signature. No party learns of any other party’s share. The protocol effectively reconstructs the private key, $u$, in zero knowledge, and uses it to sign a message.

Relative Advantages of a multisignature

• Simplicity of implementation: the trusted party simply must store and verify $t+1$ signatures, before constructing its own
• No new cryptography
• Async: parties do not need to all be online at the same time

Relative Advantages of a threshold signature

• Space-efficiency, verifier-efficiency: Only a single signature need be stored and verified
• Modularity: The implementation logic of a threshold signature can be isolated from the environment that verifies the signature, allowing a threshold signature to be computed entirely off-chain

But what if we just…centralized it?

In this centralized setting, a trusted party, Alice, will construct all the shares, and simply send them to the $n$ parties. Alice may simply pick her favorite secret sharing scheme (eg. Shamir’s) to do so.

In the centralized setting, Alice is a back door to the threshold signature, as she may simply construct signatures using the private key. In the next section we will eliminate Alice as a trusted party for true DKG.

The centralized scheme has one “key” property: Alice can bring her own private key to the threshold signature, where the rest of the threshold signing protocol continues as if Alice were a normal player. That is to emphasize that, in the DKG model, an entirely new secret key is constructed that no player possesses.

Therefore, if Alice were to delete her private key, then the setting would be identical to the next section. Since it is impossible to verify whether Alice has kept a copy, we turn to cryptography to construct Distributed Key Generation.

Cryptography time!

This section follows S3.1 in GG20. In several places, I’ve added notation not in the original paper. These are explicitly labelled, noted to avoid creating confusion.

The DKG proceeds in 3 phases. Participants in the protocol will be called “players”.

A word of warning: there will be many moving parts here. Note-taking is encouraged.

Phase 1

Each player selects their private share, and broadcasts a commitment to it. The $:=$ notation is used here to denote a calculation done by a given player.

Each player, $P_i$ constructs:

• $u_i$, an initial private share, selected at random by the player
• $(KGD_i,KGC_i):=(g^{u_i}, Com(g^{u_i}))$, a commitment to the hiding of $u_i$ to send to each other player. Note that this is essentially a commitment to a commitment of a secret.

Each player receives:

• $KGC_j\space \forall j$, the commitment broadcast by all other players
• $E_j\space \forall j$, the (Pallier) public key, broadcast by all players. This will be used to encrypt messages sent to player $P_j$, and to perform the signing protocol. That it is a Pallier cryptosystem public key is irrelevant for the scope of this post.

Phase 2

Players first decommit their public keys (broadcasting $g^{u_i}$), then perform a secret sharing and determine the group secret sharing.

Denote the $(t,n)$-secret sharing scheme of the secret $u_i$ (my notation): $$SS_{t,n}(u_i:\text{secret},z:\text{evaluation index})=u_i+a_{i,1}z+…+a_{i,t}z^t$$ and the the jth evaluation of the polynomial, $$s_{i,j} =SS_{t,n}(u_i,j)=u_i+a_{i,1}j+..+a_{i,t}j^t=u_i+\sum_k a_{j,k}j^k$$ Where the coefficients $a_{i,k}$ are selected at random by $P_i$. The reader should verify that $P_i$ can compute $s_{i,j}$ for all $j$.

Each player, $P_i$:

• assigns $y_j=KGD_j\space \forall j<t$, the hiding of the of each other player’s secret. Henceforth, the symbol $\forall$ denotes for all players.
• computes $y:=\prod y_i=g^{\sum u_i}$, the “public key” of the group; the group’s “secret key” will be the sum of shares, $\sum u_i$.
• selects random coefficients to construct $SS_{t,n}(u_i,z)$, the temporary secret sharing polynomial for their own secret.
• computes shares $s_{i,j}\space \forall j$ to privately send to each other player. Player $P_i$ receives $s_{j,i}$ from each other player $P_j$.
• computes $x_i:=\sum_j s_{j,i}$
• computes the hiding of $x_i$, $X_i=g^{x_i}$

Denote the group secret $x=\sum u_i$.

We will now show that Player $P_i$ has computed a $(t,n)$ secret share of $x$: $$x_i:=\sum_j s_{j,i} = \sum_j SS_{t,n}(u_j,i)$$ $$=(\sum_j u_j)+(\sum_j a_{j,1})i+…+(\sum_j a_{j,t})i^t$$ $$=SS_{t,n}(\sum_j u_j: \text{group secret}, i: \text{player index})$$ Note that coefficients of this polynomial are shared by all players, but not known to any player. Therefore, each player $P_i$ now posseses in $x_i$ a $(t,n)$-secret-sharing of $x$.

Phase 3: Verifiability

Suppose Player $P_i$ were able to lie to player $P_j$ about the value of $X_i$, the hiding of their secret key share. This would allow player $P_i$ to volunteer to participate in the signing protocol, but prevent the creation of a valid signature, without anyone knowing!

By adopting the Feldman VSS, which extends the Shamir SS, Player $P_i$ gains the ability to calculate each other player $P_j$’s commitment $X_j$. This step prevents any player from cheating in the signature protocol.

In the Feldman VSS, each party also publishes the hiding of each coefficient of their polynomial, $g^{a_{i,k}}\space \forall k$. For convenience, denote the coefficients of our final polynomial: $$b_k=\sum_j a_{j,k} \quad \text{and} \quad b_0 = \sum u_j$$

Then player $P_i$’s share can be expressed: $$SS_{t,n}(\sum_j u_j,i)=\sum_j b_ji^j$$

By exploiting commitments from Feldman’s, any player $P_i$ may calculate $g^{b_k}\space \forall k$: $$g^{b_k}=g^{\sum_j a_{j,k}}=\prod_j g^{a_{j,k}}$$

Where each player broadcast the hiding of their coefficients $g^{a_{i,k}}$ as part of the Feldman protocol. Player $P_i$ exploits the above lemma to compute $g^{b_k}$, and may thereby compute $X_j$: $$X_j=g^{x_j}=g^{\sum_k b_kj^k}=\prod_k {(g^{b_k})}^{j^k}$$

There are several checks from Phase 3 that are elided. They are straightforward, but would require introducing Pallier encryption, Schnorr’s zk proof-of-knowledge-of-exponent, and a square-free proof, which I feel would bloat the scope of this post.

Wrap up

Yay, you made it here! Things you may have learned:

• An application of repeated secret key sharing to construct a distributed secret
• What threshold signatures are, and how they compare to multisignatures
• Taking good notes is hard!