Linear secret sharing schemes (LSSS) ⇔ MSP

Equivalence · free reduction · standard model · KW93

Statement

A linear secret-sharing scheme over a finite field $\mathbb{F}$ — every share a linear function of the secret and the dealer’s randomness — is equivalent to a monotone span program over $\mathbb{F}$: an MSP of size $m$ computing an access structure $\Gamma$ yields an LSSS for $\Gamma$ with total share size $m$ field elements, and every LSSS for $\Gamma$ induces an MSP of the same size computing $\Gamma$ — KW93, Bei96. In particular, MSPs over $\mathbb{F}$ compute exactly the access structures realizable by LSSS over $\mathbb{F}$.

Sketch

Given an MSP $(M,\rho ,\mathbf{e})$ with rows labelled by parties, the dealer samples $\mathbf{r}$ uniformly subject to $⟨\mathbf{e},\mathbf{r}⟩=s$ and gives each party the inner products of its rows with $\mathbf{r}$; a qualified set has $\mathbf{e}$ in the span of its rows and recovers $s$ by that linear combination, and an unqualified set’s shares are independent of $s$. Conversely, the matrix of the linear map from $(s,\text{randomness})$ to shares, with target vector selecting $s$, is an MSP for the scheme’s access structure.