Shamir’s secret sharing in Lean

3 Correctness

Lemma 3.1 Lagrange interpolation
✓
#

Let \(x_0, \dots , x_k \in F\) be distinct. A polynomial of degree less than \(k + 1\) equals the Lagrange interpolation of its values at \(x_0, \dots , x_k\).

Theorem 3.2 Correctness
✓

Let \(x_0, \dots , x_k \in F\) be distinct, and let \(L\) be the Lagrange interpolation of the shares \(p_{s,a}(x_0), \dots , p_{s,a}(x_k)\). Then \(L(0) = s\). So any \(k + 1\) parties recover the secret.

Proof ▶

By Lemma 2.4, \(p_{s,a}\) has degree less than \(k + 1\), so \(L = p_{s,a}\) by Lemma 3.1. Hence \(L(0) = p_{s,a}(0) = s\) by Lemma 2.3.

Remark 3.3
#

The points must be distinct; with a repeated point, \(k + 1\) shares carry the information of at most \(k\) of them.