What is Shamir Secret Sharing, and how does it relate to Multi-Party Computation?

Shamir Secret Sharing (1979) splits a secret s into n shares such that any k shares can reconstruct s, but fewer than k shares reveal nothing. It's the foundational primitive that many MPC protocols use to distribute computation safely.

How it works (informally):

1. To share a secret s with threshold k, pick a random polynomial of degree k−1 whose constant term is s: f(x) = s + a₁·x + a₂·x² + … + a_{k-1}·x^{k-1} (all arithmetic mod a large prime)
2. Each shareholder i receives the share (i, f(i)).
3. To recover s, any k shareholders interpolate the polynomial at x=0 (Lagrange interpolation) and read off the constant term.

Properties:

• Information-theoretically secure: with k−1 shares, the secret is literally uniformly distributed — no computational assumption.
• Linear: adding two shared secrets, or multiplying by a constant, can be done locally on each share. Multiplying two shared secrets requires more work — and that's where MPC protocols start to get clever.

Where it shows up:

• HashiCorp Vault, AWS KMS, Google Cloud HSM: master keys are stored as Shamir shares across hardware modules and operators.
• MPC wallets (Fireblocks, ZenGo): the private key never exists in one place — it's permanently held as shares.
• The Zettelchen-voting protocol (paper-slip MPC voting) is essentially Shamir-style additive secret sharing with threshold = all participants.

Tip: Shamir's "any k-of-n" property is the most-cited use of polynomial interpolation in cryptography. The same math underlies Reed-Solomon error correction (every CD and QR code uses it).