A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A (t, n) secret sharing scheme distributes a secret s among n parties such that any t parties can reconstruct s, but any t-1 parties learn absolutely nothing about s. Shamir's scheme (1979) uses polynomial interpolation: encode s as the constant term of a random degree-(t-1) polynomial over a finite field, and give each party a point on the polynomial. Any t points determine the polynomial (Lagrange interpolation); fewer than t points leave s information-theoretically hidden. Secret sharing is foundational for threshold cryptography, secure MPC (BGW protocol), key management, and distributed systems requiring fault-tolerant access to secrets.
Secret sharing addresses a fundamental problem in distributed systems: how do you store a secret so that it remains available even if some participants fail, yet remains hidden even if some participants are compromised? The answer is to split the secret into pieces (shares) distributed among n participants, such that any threshold t of them can reconstruct the secret, but fewer than t learn absolutely nothing. This is a (t, n) threshold scheme, and it achieves the remarkable property of being simultaneously fault-tolerant (survives n-t failures) and secure (resists up to t-1 compromises).
Shamir's Secret Sharing (1979) is the most elegant construction, based on polynomial interpolation over a finite field. To share a secret s with threshold t among n parties, the dealer constructs a random polynomial p(x) of degree t-1 with p(0) = s (the secret is the constant term). The remaining t-1 coefficients are chosen uniformly at random. Each party i receives the share p(i). Any t parties can reconstruct p(x) using Lagrange interpolation (t points uniquely determine a degree-(t-1) polynomial) and recover s = p(0). Any t-1 parties learn nothing: for any hypothesized value of s, there exists a polynomial of degree t-1 consistent with their shares, so all values of s are equally likely. This is information-theoretic security — no computational assumption is needed.
The applications of secret sharing pervade modern cryptography and distributed systems. In threshold cryptography, a signing or decryption key is shared among n parties, and t must cooperate to sign or decrypt — preventing any single party from unilateral action. Cryptocurrency custody solutions use threshold signatures so that stealing funds requires compromising t of n key holders. In secure multi-party computation, the BGW protocol uses Shamir sharing as its core mechanism: each party shares their input, and the function is computed on shares. In key management, organizations use (t, n) sharing to protect master keys: the key can be reconstructed when needed (e.g., for disaster recovery) but is never stored in any single location.
Verifiable Secret Sharing (VSS) extends the basic scheme to handle a dishonest dealer. In standard Shamir sharing, the dealer could distribute inconsistent shares — points that don't lie on any single polynomial — causing reconstruction to fail or produce wrong results. VSS adds a verification mechanism: the dealer publishes commitments to the polynomial's coefficients, and each party can check that their share is consistent with these commitments without learning the secret. Feldman's VSS and Pedersen's VSS are the two main constructions. VSS is essential in settings where the dealer may be adversarial (as in MPC, where each party acts as dealer for their own input), transforming secret sharing from a tool that requires a trusted third party into one that works in the fully adversarial model.