Threshold Cryptography I: Distributed Key Generation

Traditional cryptographic systems rely on a single party for cryptographic operations, introducing a single point of failure that compromises the entire system if breached. Threshold cryptography mitigates this risk by distributing trust among multiple parties, requiring only a subset (threshold) to collaboratively perform cryptographic operations.

This series of posts focuses on widely adopted threshold signature schemes, their implementations, and security considerations relevant to blockchain. It aims to bridge the gap between developers, cryptography enthusiasts, and academic literature by presenting technically dense content in an accessible format.

This first post introduces Distributed Key Generation (DKG), which allows multiple participants to jointly generate a secret key without ever reconstructing the full secret key, enhancing security and fault tolerance. It is fundamental to decentralized consensus, secure multiparty computation, and threshold signatures.

We will begin with the well-known Shamir’s Secret Sharing.

Secret Sharing Scheme

Shamir’s Secret Sharing

Shamir’s Secret Sharing (SSS) [1] is a threshold key generation scheme for dividing a secret $s$ into $n$ shares to $n$ participants such that any $t+1$ of them or more can reconstruct the secret, but a group of $<t+1$ participants reveal no information about the secret key. The scheme leverages the Lagrange polynomial interpolation over a large finite field $\mathbb{Z}_q$ .

To create the share $s$ , a dealer selects a random polynomial $f(x)=s+a_1 \cdot x + \cdots + a_t \cdot x^t$ of degree $t$ over the finite field $\mathbb{Z}_q$ (i.e., all coefficients are in $\mathbb{Z}_q$), then $f(0)=s$ is the secret. Each share is computed as point $(i,f(i))$ for $i=1, 2, \cdots, n$ , and distributed to the $n$ participants.

When $t+1$ or more shares are collected from the n participants, Lagrange interpolation is used to reconstruct the polynomial $f(x) = \sum_{i=1}^{t+1} s_i \cdot (\prod_{1 \leq j \leq t+1, i \neq j} \frac{x-j}{i-j})$ (for simplicity, the formula is given for the first $t+1$ shares), thereby recovering the secret s at $x=0$ . The security of SSS relies on the mathematical fact that a degree-$t$ polynomial is fully determined only when $t+1$ or more distinct points on the graph of the polynomial are known.

For example, a 3 out of 5 configuration (an instance of $t+1$ out of $n$) produces a degree-2 polynomial illustrated in the following diagram. The share coordinates are $x=1,2,3,4,5$ and its corresponding values $f(i)$ are the secret shares, then any 3 points are sufficient to reconstruct the degree-2 polynomial passing through the points, while 2 points are insufficient. In the diagram, the 3 points are located at 1, 2, and 4, and the y-axis shows the secret at $x=0$ .

Note that the share coordinates are chosen as integers, $1, 2, \cdots, n$ for convenience, and any sequence from $\mathbb{Z}_q$ (except for 0) can be utilized. Successful execution of SSS requires all share coordinates mod $q$ to be unique and non-zero, as a zero coordinate would directly expose the secret.

Chart 1

A limitation of Shamir’s Secret Sharing is the lack of share verifiability, which means the participant cannot verify whether its received share is correct. Feldman’s Verifiable Secret Sharing (VSS) [2] addresses this by enabling public verification of shares to detect invalid shares.

Feldman’s Verifiable Secret Sharing

Feldman’s VSS scheme operates over a large finite field $\mathbb{Z}_q$ with a generator $g$ of prime order $q$ on an elliptic curve. The dealer constructs a random degree-$t$ polynomial $f(x) = s + a_1 \cdot x + \cdots + a_t \cdot x^t$ , where the secret is $s = f(0)$ . Each participant $P_i$ ($i=1,2,\cdots,n$) receives a share $s_i = f(i)$ as in Shamir’s Secret Sharing.

To enable share verification, the dealer also publishes commitments to the polynomial coefficients $a_j$ with $C_j = a_j \bullet g$ for $j = 0, \cdots, t$ , where $\bullet$ denotes the scalar multiplication. In particular, $C_0 = s \bullet g$ is the public key corresponding to the secret key $s$ .

Participant $P_i$ can verify its share $s_i$ by checking whether $s_i \bullet g = \sum_{j=0}^{j=t} i^j \bullet C_j$ , which is basically the scalar multiplication with generator $g$ on both sides of $f(i) = s + a_1 \cdot i+ \cdot + a_t \cdot i^t$ , thereby allowing any participant $P_i$ to detect if its received share $s_i$ is invalid without revealing the secret.

To prevent a dealer from sending inconsistent commitments, participants could broadcast their received commitments and verify that all views are identical.

Distributed Key Generation

Leveraging Shamir's Secret Sharing and Feldman's Verifiable Secret Sharing, we will now introduce key distribution with a trusted dealer and distributed key generation.

Key Distribution with A Trusted Dealer

Key distribution with a trusted dealer is a common setup in threshold cryptographic schemes where a dealer is responsible for generating and distributing secret key shares among $n$ participants. This is particularly useful to import a preexisting secret key and distribute it among $n$ participants.

Broadcast Shares and Commitments

The dealer begins with a secret key $s$ (preexisting or newly generated) and constructs a random degree- $t$ polynomial $f(x) = s + a_1 \cdot x+ \cdots +a_t \cdot x^t$ with $s=f(0)$ . Using Shamir’s Secret Sharing, the dealer computes $s_i = f(i)$ for $i = 1, \cdots, n$ and privately sends the $i$-th share $s_i$ to participant $P_i$ .

To enable public key reconstruction, the dealer publishes the public key $pk =s \bullet g$ and optionally uses Feldman’s VSS to provide commitments $C_j = a_j \bullet g$ with $j = 0, \cdots, t$ , for verifiability of the distributed shares. Similarly, to prevent a dealer from sending inconsistent commitments, participants broadcast their received commitments and verify that all views are identical.

Verify Shares with Commitments

Upon receiving the share $s_i$ , each participant $P_i$ verifies it by checking $s_i \bullet g = \sum_{j=0}^{j=t} i^j \bullet C_j$ .

If the public key is available, then it can be verified with $pk = C_0$ . This ensures that any subset of at least $t+1$ participants can jointly reconstruct the secret or perform threshold cryptographic operations, while fewer than $t+1$ participants gains no information about the secret $s$ except that its public key $pk = C_0$ is revealed.

Pedersen’s Distributed Key Generation

Centralized key generation with a trusted dealer poses a security risk, even if the key is later deleted. For generation of fresh secrets, this is mitigated using Pedersen’s Distributed Key Generation (DKG) [3].

Pedersen’s DKG is effectively a parallel execution of Feldman’s VSS, where each participant independently acts as a dealer for a random secret. The final secret key is the sum of all shared secrets, ensuring no single party learns the full secret key.

The protocol executes in 2 rounds among $n$ participants, incorporating additional security measures.

Chart 2

Round 1

Each participant $P_i$ samples a random degree-$t $polynomial $f_i(x) = a_{i,0} + a_{i, 1} \cdot x+ \cdots + a_{i, t} \cdot x^t$ over a large prime field $\mathbb{Z}_q$ , where $q$ is the order of a generator $g$ on the underlying elliptic curve.
$P_i$ computes the commitment $C_i = (A_{i,0}, A_{i,1}, \cdots, A_{i,t})$ where $A_{i,j} = a_{i,j} \bullet g$ for $0 \leq j \leq t$ .
To prove the knowledge of its secret $a_{i,0}$ , $P_i$ creates a Schnorr proof $(R_i, b_i)$ where $R_i = r_i \bullet g$ with $r_i$ uniformly generated from $\mathbb{Z}_q$ and $b_i = r_i + c_i \cdot a_{i,0}$ , such that $c_i = H(i, R_i, A_{i,0})$ is the challenge, possibly including some contexts to prevent replay attacks.
Each participant $P_i$ then broadcasts the Schnorr proof $(R_i, b_i)$ and commitment $C_i$ to other participants $P_j$ .

Round 2

Upon receiving the Schnorr proof $(R_k, b_k)$ and commitment $C_k$ from another participant $P_k$ , each participant $P_i$ verifies the Schnorr proof with $R_k = b_k \bullet g - c_k \bullet A_{k,0}$ , where $c_k = H(k, R_k, A_{k,0})$ . If the verification fails, then $P_i$ aborts immediately.
Each $P_i$ sends the secret share $(j, f_i(j))$ to another participant $P_j$ via p2p, then deletes $f_i$ and all sent shares, retaining only $f_i(i)$ .
Each $P_i$ verifies all the received shares from other $P_k$ via the check $f_k(i) \bullet g = \sum_{j=0}^{t} i^j \bullet A_{k,j}$ for $1 \leq k \leq n$ , $k \neq i$ .
Finally, $P_i$ aggregates all received secret shares $f_k(i)$ to obtain its final share $s_i = \sum_{k=1}^{n} f_k(i)$ .

The protocol is fully symmetric across all $n$ participants; any participant aborts immediately upon verification failure.

Conclusion

This post reviewed common distributed key generation techniques, including Shamir’s Secret Sharing, Feldman’s Verifiable Secret Sharing, and Pedersen’s Distributed Key Generation.

The pros and cons of key distribution with a trusted dealer versus distributed key generation are summarized below, with respect to centralization, protocol complexity, and secret key usage.

Methods	Centralization	Complexity	Secret Key Usage
Key distribution with a trusted dealer	Yes	1-round communication	Distribute a preexisting secret key or generate a new one
Pedersen’s Distributed key generation	No	2-round communication	Generate a new secret key