Shamir's secret sharing (source code)

= Shamir's secret sharing
{c}
{title2=$f(X)=S+\sum_{j=1}^{r-1}a_jX^j$}
{wiki}

<Shamir's secret sharing> distributes a secret $S$ in a <finite field> $\mathbb F_q$ so that any $r$ of $s$ shares recover it, while fewer than $r$ shares reveal no information about it. Choose $1\le r\le s\le q-1$, distinct nonzero field elements $x_1,\ldots,x_s$, and independent uniformly distributed coefficients $a_1,\ldots,a_{r-1}$, independent of $S$. Set
$$
f(X)=S+a_1X+\cdots+a_{r-1}X^{r-1}
$$
and give participant $i$ the pair $(x_i,f(x_i))$. Any $r$ shares determine $f$ by <polynomial interpolation>, hence determine $S=f(0)$. Fewer than $r$ shares have a distribution independent of $S$; this is <Perfect secrecy of Shamir's threshold scheme>.<How to Share a Secret by Adi Shamir>[Pages 612–613: polynomial construction and threshold property]{ref}

For example, over the <finite field> $\mathbb F_7$, a two-share threshold with secret $3$ and coefficient $a_1=2$ gives $f(X)=3+2X$. The shares $(1,5)$ and $(2,0)$ recover $a_1=2$ and $S=3$. Either share alone is compatible with every secret, and the uniform choice of $a_1$ makes its distribution independent of that secret.