Shamir’s secret sharing in Lean

4 Perfect secrecy

Fix \(k\) parties with points \(x_0, \dots , x_{k-1} \in F\).

Definition 4.1 Shares of \(k\) parties
✓
#

For a fixed secret \(s\), let \(\mathrm{sh}_s \colon F^k \to F^k\) send the random coefficients \(a\) to the shares \(\bigl(p_{s,a}(x_0), \dots , p_{s,a}(x_{k-1})\bigr)\).

Lemma 4.2
✓

If the points \(x_0, \dots , x_{k-1}\) are distinct and nonzero, then \(\mathrm{sh}_s\) is injective.

Proof ▶

Suppose that \(\mathrm{sh}_s(a) = \mathrm{sh}_s(b)\). Then \(p_{s,a}\) and \(p_{s,b}\) agree at the \(k\) points \(x_j\), and at \(0\), where both equal \(s\) (Lemma 2.3); since the \(x_j\) are nonzero, these are \(k + 1\) distinct points. The difference \(p_{s,a} - p_{s,b}\) has degree less than \(k + 1\) (Lemma 2.4) and \(k + 1\) roots, so it is zero. By Lemma 2.5, \(a_j\) and \(b_j\) are the coefficients of \(X^{j+1}\) in the same polynomial, so \(a = b\).

Theorem 4.3 Perfect secrecy, combinatorial form
✓
#

If \(F\) is finite and the points \(x_0, \dots , x_{k-1}\) are distinct and nonzero, then \(\mathrm{sh}_s\) is a bijection: every list of \(k\) shares comes from exactly one choice of random coefficients, whatever the secret.

Proof ▶

An injective map from a finite set to itself is bijective.

Theorem 4.4 Perfect secrecy, probabilistic form
✓
#

Under the same hypotheses, if the coefficients \(a\) are uniformly distributed on \(F^k\), then the shares \(\mathrm{sh}_s(a)\) are uniformly distributed on \(F^k\).

Proof ▶

A bijection of a finite set onto itself maps the uniform distribution to the uniform distribution: each \(v \in F^k\) has exactly one preimage, so it has probability \(|F|^{-k}\).

Corollary 4.5
✓
#

Under the same hypotheses, the distribution of the \(k\) shares is the same for any two secrets \(s\) and \(s'\).

Proof ▶

Both are the uniform distribution, by Theorem 4.4.

Remark 4.6
#

The hypothesis that the points are nonzero cannot be dropped: a party with the point \(0\) receives \(p_{s,a}(0) = s\) itself.