Threshold Secret Sharing and Why t of n Beats Two Copies

Splitting a key into two halves and storing them in two places is a common instinct and a poor construction. An attacker who obtains one half learns half the bits directly, and the search space for the other half shrinks accordingly; with a 256-bit key, one half reduces the problem to 128 bits, which is the security level of a much weaker system. A threshold scheme avoids this: any t of n shares determine the secret, and any t-1 shares determine nothing at all, not even a shortened search.

The polynomial that hides an integer

Shamir’s construction, published in 1979, works over a finite field. Take a prime p larger than the secret S, which is treated as an integer in [0, p). Choose t-1 random coefficients a₁ … a_{t-1} uniformly from the field, and define

$$f(x) = S + a_1 x + a_2 x^2 + \cdots + a_{t-1} x^{t-1} \pmod p.$$

The secret is f(0). Each share is a pair (xᵢ, f(xᵢ)) for a distinct nonzero xᵢ. Given t such pairs there is exactly one polynomial of degree at most t-1 through them, and it can be recovered by Lagrange interpolation; evaluating at zero gives S. Given t-1 pairs, every candidate value of S is consistent with some polynomial of degree at most t-1, because one free coefficient remains to satisfy the constraint. The information-theoretic statement is exact: t-1 shares leave the secret’s posterior distribution equal to its prior, with no computational assumption involved.

That last point is worth separating from what is usually called “encryption”. The hiding here does not rely on the difficulty of a problem; it is a counting argument. Ten shares cannot be combined by any amount of computation to recover a 256-bit secret from nine of them, because the missing information is not there.

The field matters. Working modulo a prime makes every nonzero element invertible, which is what Lagrange interpolation needs. Working modulo a power of two, or over the integers, produces a structure where division fails for some coefficients and shares can leak. The standard implementation uses a prime field, either a prime slightly larger than the secret’s bit length, in which case the secret is an integer, or GF(2^8) applied byte by byte, in which case each share byte is a field element and no padding is needed. The byte-wise variant is convenient because shares are the same length as the secret; the prime-field variant needs a prime above 2^256 for a 256-bit secret and produces shares slightly longer.

import secrets

# GF(256) with the AES polynomial x^8 + x^4 + x^3 + x + 1.
EXP, LOG = [0] * 512, [0] * 256
x = 1
for i in range(255):
    EXP[i] = x
    LOG[x] = i
    x ^= (x << 1) ^ (0x11B if x & 0x80 else 0)
EXP[255:510] = EXP[0:255]

def mul(a: int, b: int) -> int:
    return 0 if a == 0 or b == 0 else EXP[LOG[a] + LOG[b]]

def split(secret: bytes, t: int, n: int) -> list[bytes]:
    shares = [bytearray(len(secret)) for _ in range(n)]
    for i, s in enumerate(secret):
        coeffs = [s] + [secrets.randbelow(256) for _ in range(t - 1)]
        for j in range(n):
            xj, acc = j + 1, 0            # evaluate f(x_j) by Horner
            for c in reversed(coeffs):
                acc = mul(acc, xj) ^ c
            shares[j][i] = acc
    return [bytes(sh) for sh in shares]

Each byte of the secret is shared independently with its own random polynomial, so a 32-byte key produces 32 polynomials, and the shares are 32 bytes each regardless of t or n. The security holds byte by byte: any t-1 shares leave every byte’s value uniformly distributed.

Recombination is interpolation at zero

Recovery uses the Lagrange basis evaluated at x = 0. For a set of t shares at coordinates xᵢ, the interpolating polynomial’s value at zero is

$$S = \sum_{i} y_i \prod_{j \neq i} \frac{x_j}{x_j - x_i} \pmod p.$$

The coefficients depend only on the x coordinates, not on the y values, so they can be computed once and applied to each byte position. In a byte-wise field, the subtraction is XOR and the division is a multiplication by an inverse, which a logarithm table makes cheap. The result is a linear operation, which has a security consequence worth stating: shares are combined by a linear function, so an attacker who can influence one share can bias the recovered secret in a predictable way, but cannot learn the others from the result. Integrity has to come from elsewhere, typically from a hash of the secret stored with each share or from the fact that the reconstructed key fails to decrypt anything.

Verification of shares before reconstruction is the practical refinement. A dealer can include a commitment to the polynomial coefficients, and a holder can check a share against it without learning the secret. Without such a check, a single corrupted share produces a wrong secret with no indication of which share was at fault, and the failure appears as a decryption error far from its cause. Feldman and Pedersen schemes provide the commitments, at the cost of additional public values and, for Pedersen, a second polynomial.

What the threshold actually enforces

The scheme hides a secret. It does not, by itself, distribute trust over the use of the secret. Once t holders reconstruct, the secret exists in one place in one process, and any holder who participates can keep a copy. The threshold protects against storage compromise and against the loss of up to n-t shares; it does not protect against t colluding holders, and it does not prevent a single reconstruction from creating a new single point of exposure.

Threshold cryptography closes part of that gap. In a threshold signature scheme, the t parties each hold a share of the private key and jointly compute a signature without any of them learning the key; the signature verifies against a single public key. The computation is a protocol with several rounds and, for many constructions, a multiplication of secret shares that requires oblivious transfer or homomorphic commitments. The output is a signature, and the key never exists in one place. That property is what makes the technique interesting for a certificate authority whose signing key must not be reconstructible, and it comes with the cost of a protocol, its message complexity, and the availability requirement that t parties be online at signing time.

The distinction should drive the choice. For backup and disaster recovery, plain sharing is the right tool: the secret must be reconstructible by a small quorum, and the reconstruction is rare and controlled. For an online signing key, threshold cryptography is the right tool, because reconstruction per operation would reintroduce the very exposure the scheme is meant to remove.

Parameters and the ways they go wrong

The choice of t and n encodes a policy about collusion and availability. A 2-of-3 split tolerates one loss and requires two colluding holders; a 3-of-5 tolerates two losses and requires three. Increasing n lowers the risk of accidental loss and raises the number of places the shares live, which raises the chance of one being stolen. Increasing t raises the collusion requirement and lowers availability. The pair is a statement about which failure is worse.

Share identifiers are a classic failure. Each share must have a distinct, nonzero x coordinate, and it must travel with the share. Duplicated coordinates make interpolation singular: two shares at the same x give no more information than one and the system cannot reconstruct. Using small sequential coordinates is fine cryptographically, since the security does not depend on their secrecy, but it means a share’s identity must be stored alongside it rather than assumed.

Reuse of the polynomial across secrets is the second. A dealer that shares two secrets under the same coefficients leaks their difference to anyone holding t-1 shares of both. Every secret must get fresh random coefficients, which is exactly where the entropy source reappears: the coefficients are the only random input, and a biased generator produces polynomials whose coefficients are guessable and whose shares therefore leak.

A third is the social layer. Shares stored on the same filesystem, in the same backup, or in the same administrator’s password manager do not constitute n independent holders; they are n copies of one holder’s material, and a single compromise takes all of them. The scheme’s guarantee is about holders, and the mapping from holders to storage locations is where it is usually broken. Keeping shares under distinct administrative control, and the corresponding destruction discipline, is the subject of key destruction and cryptographic erasure.

Finally, shares have no versioning of their own. Rotating a shared secret means re-sharing and redistributing every share, and a holder who misses the redistribution holds a share of the old secret. Systems that rotate regularly therefore need to track which share generation each holder has, which is the same bookkeeping as the key versions in a wrapped-key hierarchy, applied to the parties rather than to the records.