1 Introduction
This blueprint describes the mathematics formalized in the Lean library shamir-lean: Shamir’s secret sharing scheme [ Sha79 ] and its two properties, correctness and perfect secrecy. Every definition and theorem below names its Lean counterpart, and the web version has a dependency graph that shows how the results build on each other. All the statements are proved in Lean, with no sorry, and depend only on the standard axioms of Lean.
The scheme
Fix a field \(F\) (in practice a finite field) and a natural number \(k\); the threshold is \(k + 1\). To share a secret \(s \in F\), the dealer picks \(k\) random coefficients \(a_0, \dots , a_{k-1} \in F\) and forms the polynomial
of degree at most \(k\), with \(p(0) = s\). Each party receives a distinct nonzero public point \(x \in F\) and the share \(p(x)\). Shamir’s two claims are:
Correctness: any \(k + 1\) parties can recover \(s\) (Theorem 3.2).
Perfect secrecy: any \(k\) parties learn nothing about \(s\): whatever the secret, their shares are uniformly distributed (Theorem 4.4 and Corollary 4.5).
The idea in one picture
For threshold \(2\), so \(k = 1\), the polynomial is a line \(p(X) = s + a_0 X\) that meets the vertical axis at the secret. Two points determine a line, so two parties recover \(s\). Through a single point \((x, p(x))\) with \(x \neq 0\) passes exactly one line for each possible value at \(0\), so one share says nothing about \(s\). In general, \(k + 1\) points determine a polynomial of degree at most \(k\), but \(k\) points leave its value at \(0\) free.