Shamir Secret Sharing and Keys That Never Meet

Most of what gets called MPC custody rests on one old idea: split a secret so that no single holder knows it, but enough holders together can use it. Here are the pieces, with the actual formulas.

Splitting a secret with a polynomial

Work in a prime field of order q, which for secp256k1 is the group order of the curve. To share a secret d so that any t of n parties can recover it, pick a random polynomial of degree t-1 whose constant term is the secret:

f(x) = d + a_1 x + a_2 x^2 + \cdots + a_{t-1} x^{t-1} \pmod q

The coefficients a_1 ... a_{t-1} are uniformly random. Party i receives the share:

s_i = f(i)

A polynomial of degree t-1 is determined by t points, so any t shares pin it down. With only t-1 shares, every possible value of d is equally consistent with what you hold, so they carry no information about the secret. This is information-theoretic security, not a computational assumption.

Reconstruction with Lagrange interpolation

Given a set S of t parties, the secret is f(0), and Lagrange interpolation evaluates that directly:

d = \sum_{i \in S} \lambda_i s_i \pmod q, \qquad \lambda_i = \prod_{j \in S,\, j \ne i} \frac{j}{j - i} \pmod q

The coefficient λ_i depends only on which parties are in S, not on the secret. That detail matters in the next section.

Never reconstructing the key

Reconstruction brings the key back into one place, which defeats the purpose. The trick is that the formula above is linear in the shares, so each party can apply its coefficient locally and keep working with additive pieces:

x_i = \lambda_i s_i \ \text{(party } i \text{, locally)}, \qquad d = x_1 + x_2 + \cdots + x_t \ \text{(never computed)}

The public key can be computed without the secret as well. Each party publishes x_i·G, and anyone can add them:

Q = dG = \sum_i x_i G

Generating the key without a dealer

Shamir's original scheme assumes a trusted dealer who knows d. A distributed key generation (DKG) removes that role. Every party j picks its own secret d_j and its own polynomial f_j, then sends f_j(i) to party i. Each party sums what it received:

s_i = \sum_j f_j(i), \qquad d = \sum_j d_j

The sum of random polynomials is itself a random polynomial of degree t-1, with constant term d.

Catching a cheating dealer

A malicious party could send inconsistent shares. Feldman's verifiable secret sharing adds public commitments to the coefficients:

C_k = a_k G \quad \text{for } k = 0, \ldots, t-1

Party i checks its share against them:

s_i G \stackrel{?}{=} \sum_{k=0}^{t-1} i^k C_k

If the equation holds, the share lies on the committed polynomial. The commitments reveal d·G, which is the public key anyway, but not d.

Signing is where it gets interesting

For Schnorr-style signatures, linearity is enough. Each party picks a nonce k_i, publishes R_i = k_i·G, and the group computes:

\begin{aligned} R &= \sum_i R_i \\ e &= H(R \parallel Q \parallel m) \\ z_i &= k_i + e\, x_i \\ z &= \sum_i z_i = k + e d \end{aligned}

and z·G = R + e·Q verifies like a normal signature. This is the idea behind FROST, which also adds protections against nonce attacks that I'm glossing over.

ECDSA is not that friendly, because its signing equation needs the inverse of the nonce, and inverses are not linear. That is the subject of the next note, How Threshold ECDSA Signs.

What to keep in mind

Shamir sharing gives secrecy of the key at rest, and the additive form of the shares lets the key be used without being assembled.
The threshold t is a property of the polynomial degree, set at generation time. Changing it means resharing.
Shares can be refreshed by adding a random polynomial with zero constant term, which changes every share but not d. An attacker who stole shares over a long period has to steal t of them within one refresh epoch.