= Solution
Use <Shamir's secret sharing> over the <finite field> $\mathbb F_p$. The Chair independently chooses $a_1,\ldots,a_{r-1}$ from the <uniform distribution on a finite set> $\mathbb F_p$ and forms the random <polynomial>
$$
f(X)=N+a_1X+\cdots+a_{r-1}X^{r-1}\in\mathbb F_p[X].
$$
Choose distinct nonzero $x_1,\ldots,x_s\in\mathbb F_p$, with $s$ equal to the number of discs to be issued, and inscribe $(x_i,f(x_i))$ on disc $i$.
Any $r$ discs give $r$ distinct values of a polynomial of degree at most $r-1$. Their <Vandermonde determinant> is nonzero, so <polynomial interpolation> recovers $f$ uniquely and hence recovers the secret as $N=f(0)$.
Conversely, fix any $r-1$ observed discs and any candidate secret $n\in\mathbb F_p$. Interpolating through those $r-1$ points and $(0,n)$ gives exactly one polynomial of degree at most $r-1$. Thus every candidate $n$ is compatible with the observed discs in exactly the same number of ways. Because the coefficients were chosen <uniform distribution on a finite set>[uniformly], the <conditional distribution> of the secret is unchanged after seeing any $r-1$ discs. This proves the <Perfect secrecy of Shamir's threshold scheme>.
Back to article page
