Shamir’s secret sharing in Lean

2 The dealer’s polynomial

Throughout, \(F\) is a field and \(k\) a natural number.

Definition 2.1 Dealer’s polynomial
✓
#

For \(s \in F\) and \(a = (a_0, \dots , a_{k-1}) \in F^k\), let

\[ p_{s,a}(X) = s + \sum _{i=0}^{k-1} a_i X^{i+1} \in F[X]. \]
Definition 2.2 Share
✓
#

The share of the party with public point \(x \in F\) is \(p_{s,a}(x)\).

Lemma 2.3
✓
#

The secret is the value at zero: \(p_{s,a}(0) = s\).

Proof ▶

Every term of the sum vanishes at \(0\).

Lemma 2.4
✓
#

The polynomial \(p_{s,a}\) has degree less than \(k + 1\).

Proof ▶

The constant term has degree at most \(0\), and each term \(a_i X^{i+1}\) has degree at most \(i + 1 \le k\).

Lemma 2.5
✓
#

The random coefficients can be read back from the polynomial: the coefficient of \(X^{j+1}\) in \(p_{s,a}\) is \(a_j\), for \(0 \le j {\lt} k\).

Proof ▶

Only the term \(i = j\) of the sum contributes to the coefficient of \(X^{j+1}\).