Threshold Cryptography

Core Idea

Threshold cryptography distributes a cryptographic key among n parties so that t must cooperate to perform operations (signing, decryption) but no t-1 colluding parties learn anything about the key. Unlike basic secret sharing (which reconstructs the key before use), threshold schemes compute directly on shares — the full key is never assembled in any single location. Distributed Key Generation (DKG) eliminates even the trusted dealer. Applications include cryptocurrency custody (multi-sig wallets), CA key protection, and organizational policy enforcement. Threshold ECDSA and threshold Schnorr are deployed in production systems.

Explainer

Threshold cryptography takes the idea of secret sharing and extends it from secure storage to secure computation. In basic secret sharing, the key must be reconstructed before use — creating a window of vulnerability when the full key exists in a single location. Threshold cryptography eliminates this window: parties compute directly on their shares, producing partial results that combine into a valid cryptographic operation (signature, decryption) without the full key ever existing anywhere. The key is born distributed, lives distributed, and operates distributed.

A (t, n) threshold signature scheme works as follows. During setup (via DKG or a trusted dealer), the signing key sk is shared among n parties, each holding a share sk_i. To sign a message, at least t parties compute partial signatures using their individual shares. These partial signatures are combined (typically via Lagrange coefficients) to produce a standard signature verifiable by anyone with the public key. No individual party ever sees the full signing key. For Schnorr signatures, this is elegant: the signing equation s = k + ex is linear in the secret key x, so partial signatures s_i = k_i + e * x_i (computed on shares k_i and x_i) sum to the correct full signature. For ECDSA, the multiplicative inverse in s = k^-1(H(m) + rx) makes distributed computation harder, requiring multi-party multiplication protocols.

Distributed Key Generation (DKG) eliminates the trusted dealer, the last centralized trust point. Each party acts as a dealer: party i generates a random secret s_i and distributes shares of s_i to all parties using verifiable secret sharing. The aggregate secret s = sum(s_i) is the signing key. No party knows s because no party knows all the s_i values — each knows only their own contribution and the shares they received from others. Their share of s is the sum of all shares they received. This construction is secure as long as fewer than t parties collude, and it handles malicious parties through the verification mechanisms of VSS.

Proactive security addresses the realistic threat of a mobile adversary — an attacker who compromises different parties over time. Without countermeasures, an adversary who compromises party 1 in January and party 2 in March has accumulated 2 shares, regardless of whether party 1 has since been patched. Proactive secret sharing divides time into epochs and refreshes shares at each epoch boundary. Each party distributes shares of zero (a random degree-(t-1) polynomial with constant term 0) and everyone adds the received shares to their existing share. The result is a new set of shares for the same secret, but algebraically incompatible with shares from the previous epoch. The adversary must compromise t parties within a single epoch — their accumulated shares from different epochs are useless. This is deployed in production systems for cryptocurrency custody (Fireblocks, Coinbase), certificate authority key protection, and organizational signing infrastructure where keys must remain secure for years.