Distributed Key Generation: Verifiable and dealerless

This post was first published on Medium.

Distributed Key Generation (DKG) is a cryptographic protocol that enables multiple parties to collaboratively generate a shared key without any single party ever learning the key in its entirety. It enhances security in various applications by distributing trust among multiple participants, reducing the risk of key compromise. We introduce a verifiable and dealerless DKG that is amenable for use in blockchains.

Shamir Secret Sharing (SSS)

Shamir’s Secret Sharing (SSS) is a cryptographic method that allows a secret to be divided into parts, with each participant holding a part of the secret, known as a share. The key feature of SSS is that the secret can only be reconstructed when a predefined number of shares, known as the threshold, are combined together. It is a threshold scheme, denoted as (t,n), where n is the total number of shares distributed and t is the minimum number of shares required to reconstruct the secret.

At the heart of the SSS scheme is the mathematical concept that points uniquely define polynomials. Specifically, it takes two points to define a line, three points to define a parabola, and so forth. Thus, a polynomial of degree (t-1) is uniquely determined by t points. In this scheme, a polynomial of degree (t-1) is constructed such that each of the n
participants is associated with one point on this polynomial, which encodes a secret. To recover the polynomial, and thus the secret, only t of these points are necessary. Any group of t participants, each holding their share, can reconstruct the original polynomial of degree (t-1). The secret is embedded within the polynomial as the y-intercept, meaning the value of the polynomial at x=0, which effectively makes it the constant term of the polynomial. Through this method, the secret can be securely and accurately retrieved.

Let us examine a (3, 4) secret sharing scheme. The entity responsible for dividing the secret, known as the dealer, constructs a polynomial of degree 2, i.e., (t-1):

f(x) = s + a₁x + a₂x²

s represents the secret value at y-intercept (i.e., f(0)), while a₁ and a₂ are random numbers.

SSS consists of two primary processes:

1. the distribution of secret shares: in the distribution phase, the dealer splits the secret into several parts, or shares, and distributes these among a set of n (i.e., 4) participants. Each participant Pᵢ receives a share sᵢ = f(I).
2. the reconstruction of the secret: the reconstruction process allows only t (i.e., 3) participants to combine their shares and recover the original secret, while any other group less than t shares cannot deduce anything significant about the secret. For example, the first 3 participants can form a set of points (1, s₁), (2, s₂), and (3, s₃) and reconstruct the unique polynomial f(x), typically using Lagrange interpolation method. The secret s is simply f(0).

Verifiable Secret Sharing (VSS)

In Shamir Secret Sharing, a participant does not know if the share she receives is consistent with the shares that other participants have received. For example, a malicious dealer gives P₁, P₂, and P₃ correct shares f(1), f(2), and f(3), but gives P₄ a wrong share, i.e., not f(4). If P₄ is chosen later, the secret value cannot be recovered correctly.

Verifiable Secret Sharing (VSS) is an extension of the Shamir’s Secret Sharing scheme that allows the shares of a secret to be verified for their correctness. This is done without revealing the shares themselves, otherwise everyone knows all shares and thus can recover the secret itself, defeating the whole purpose of secret sharing.

In VSS, the dealer sends each participant commitments to all polynomial coefficients, besides the share. One way to commit is to use a elliptic curve:

c₀ = sG

c₁ = a₁G

c₂ = a₂G

cᵢ commits to aᵢ. G is the generator point.

Pᵢ can independently verify the validity of her share by checking if the following equality holds:

f(i)G =? c₀ + c₁i + c₂i²

This is because

f(i)G = (s + a₁i + a₂i²)G = sG + a₁iG + a₂i²G = c₀ + c₁i + c₂i²

Note she knows all information needed in the equation. If the equation does not hold, she knows the dealer is dishonest and can simply terminate.

Distributed Key Generation

At this stage, we have mastered the technique of distributing our key so that all participants receive it and can verify it. However, we are faced with an issue—a dealer is aware of the original secret.

Distributed Key Generation (DKG) solves this issue by allowing each participate to contribute to the overall randomness of the key. Dealerless DKG basically conducts n independent runs of VSS. In the i-th run, Pᵢ acts as the dealer to distribute secret sᵢ. Each participant collects secret shares from other participants and the final share is the sum of shares in each run. The final secret is the sum of secrets in all runs.

To see why, let’s consider the following two polynomials, representing secret a and b:

f₁(x) = a + a₁x + a₂x² + …

f₂(x) = b + b₁x + b₂x² + …

These two polynomials can be summed up to form the final secret key polynomial:

f(x) = (a+b) + (a₁+b₁)x + (a₂+b₂)x² + …

f(x) encodes secret a+b, which is the sum of two individual secrets. Its shares are also sum of two individual shares of the original two polynomials.

Watch: sCrypt applications are proving how powerful Bitcoin is