Secret Sharing

Secret sharing splits a secret s into n shares such that any t of them reconstruct s and any fewer than t learn nothing. The two famous schemes are Shamir's (polynomial-based, t-of-n) and additive (each share is s_i such that Σ s_i = s, requires all parties).

In Shamir's scheme, the dealer picks a random polynomial p(x) = s + r₁x + ... + r_{t-1}x^{t-1} and hands share i the value p(i). Lagrange interpolation over any t shares recovers p(0) = s. The randomness in higher-order coefficients is what hides s from any subset smaller than t.

The property that makes this useful for secure-multiparty-computation is linearity:

• [x] + [y] = [x + y] — share-wise addition is free
• [x] + a = [x + a] for known constant a
• a · [x] = [a·x] for known constant a

So linear combinations of secret-shared values are computable with no interaction. The hard part is multiplication of two shared values, where naïve term-by-term multiplication doubles the polynomial degree of the result — the reconstruction threshold goes from t to 2t-1. beaver-triples is the standard fix in the precompute-then-online model.

The pattern reaches deep: HE schemes are basically secret sharing where the "shares" are encryptions; FHE bootstrapping is morally a re-randomization of the share polynomial; the Bitcoin community uses Shamir-like splits for cold-storage (though Pedersen-VSS and Feldman-VSS add commitments to defend against malicious dealers).

Cross-references: mpc-beaver-triples, beaver-triples, secure-multiparty-computation.