Secret sharing

A $(t,n)$-secret sharing scheme allows a dealer to split a secret $s$ among $n$ parties such that any $t$ or more parties can reconstruct $s$ exactly, while any set of fewer than $t$ parties learns nothing about $s$. Introduced independently by Shamir and Blakley — Sha79, Bla79.

Syntax

A $(t,n)$-secret sharing scheme over a secret space $\mathcal{S}$ is a pair of efficient functions:

• $\mathsf{Share}(s)\to (s_1,\dots ,s_n),$ a randomized algorithm that distributes the secret $s\in \mathcal{S}$ into $n$ shares $s_i\in {\mathcal{S}}_i,$
• $\mathsf{Recon}(T,\{s_i{\}}_{i\in T})\to s\text{ or }\perp ,$ a deterministic reconstruction algorithm for any set $T\subseteq [n]$ with $|T|\ge t.$

Properties

Correctness

For any $s\in \mathcal{S}$, any set $T\subseteq [n]$ with $|T|\ge t$, and $(s_1,\dots ,s_n)\leftarrow \mathsf{Share}(s)$: $\mathrm{Pr}\left[\mathsf{Recon}(T,\{s_i{\}}_{i\in T})=s\right]=1.$

Privacy

For any set $T\subseteq [n]$ with $|T|<t$ and any two secrets $s,s^{\prime }\in \mathcal{S}$: $\left\{(s_i{)}_{i\in T}:(s_1,\dots ,s_n)\leftarrow \mathsf{Share}(s)\right\}=\left\{(s_i{)}_{i\in T}:(s_1,\dots ,s_n)\leftarrow \mathsf{Share}(s^{\prime })\right\}.$

This is perfect privacy: no information about $s$ leaks from any $t-1$ shares, even to computationally unbounded adversaries.

Variations

Shamir secret sharing

The canonical construction works over a prime field ${\mathbb{F}}_p$. The dealer samples a random polynomial $f\in {\mathbb{F}}_p[X]$ of degree $t-1$ with $f(0)=s$, and gives party $i$ the share $s_i=f(i)$. Reconstruction uses polynomial interpolation (e.g., Lagrange’s formula) on any $t$ points.

Blakley’s geometric construction

The dealer fixes a point $P\in {\mathbb{F}}_p^t$ whose first coordinate is the secret and whose other coordinates are uniform, and gives each party a hyperplane through $P$. The hyperplanes are chosen so that any $t$ of them meet only in $P$, and any $t-1$ of them meet in a line on which the first coordinate is not constant — Bla79.

Computational secret sharing

Relaxes perfect privacy to computational indistinguishability, which allows shares shorter than the secret; in a perfect scheme every share is at least as long as the secret — KGH83. Encrypting $s$ under a fresh key, sharing the key with a perfect scheme, and splitting the ciphertext with an information dispersal algorithm gives $(t,n)$ shares of length $|s|/t+O(\lambda )$ — Kra93.

Verifiable secret sharing (VSS)

A secret sharing scheme in which each party can check, even against a malicious dealer, that its share is consistent with a single secret, so that every $t$ parties holding accepted shares reconstruct the same value. Pedersen’s scheme achieves this non-interactively by broadcasting DLOG-based homomorphic commitments to the coefficients of the Shamir polynomial (DLOG ⇒ VSS) — Ped91. VSS is the sharing step of information-theoretic MPC — BGW88.

Linear secret sharing schemes (LSSS)

A secret sharing scheme is linear if the shares are linear functions of the secret and randomness. Equivalent to monotone span programs over $\mathbb{F}$.

Other results

• $(t,n)$-threshold secret sharing exists information-theoretically for all $1\le t\le n$ — Sha79, Bla79
• Secret sharing is information-theoretically achievable; no computational hardness assumption required
• Linear SS ⇒ IT-PIR
• Linear secret sharing schemes (LSSS) ⇔ MSP
• Monotone-span-program size lower bounds survive amortization: a lower bound proved for a program sharing one secret still applies, per secret, when the same program is reused to share several secrets at once — Kha26
• There exist access structures on $n$ parties for which every perfect multilinear scheme, over every finite field, requires shares of total size $2^{\Omega (n)}$ times the secret size — matching the known $2^{O(n)}$ upper bound and settling Question 10.4 of Bei25 — Kha26

Participates in

Builds on Secret sharing

• Linear secret sharing schemes (LSSS) ⇔ MSP (via Linear secret sharing schemes (LSSS))
• Linear SS ⇒ IT-PIR (via Linear secret sharing schemes (LSSS))

Produces Secret sharing

• DLOG ⇒ Verifiable secret sharing (VSS) (via Verifiable secret sharing (VSS))