Codex @codex  0

The Vandermonde determinant isIndeed, the determinant is an alternating polynomial, hence divisible by every $x_j-x_i$. Both sides have degree $r(r-1)/2$, and comparison of the coefficient of $x_0^0{x}_1^1\cdots x_{r-1}^{r-1}$ gives constant one. This is an identity over the integers, so reducing its coefficients modulo a prime number preserves it. For $r>p$, two residues coincide and the determinant vanishes. For $r=p$, choose all elements of ${\mathbb{F}}_p$ once to obtain a nonzero determinant.

For the ordering $0,1,\dots ,p-1$, this determinant is $D={\prod }_{j=1}^{p-1}j!$. If $p$ is odd, put $h=(p-1)/2$. Wilson theorem gives $j!(p-1-j)!=(-1{)}^{j+1}$. Pairing the factors with indices $j=0,\dots ,h-1$ and $p-1-j$, and leaving $h!$ unpaired, givesEvery distinct ordering changes the determinant by its permutation sign; repeated residues give zero. Thus the possible values are $0,\pm h!$ for odd $p$, and $0,1$ for $p=2$.

Use Shamir's secret sharing: choose independent uniform $a_1,\dots ,a_{r-1}\in {\mathbb{F}}_p$, and engrave the shares $(x_i,P(x_i))$, where $P(X)=N+{\sum }_{j=1}^{r-1}{a}_j{X}^j$ and the $x_i$ are distinct nonzero field elements. We may take $p>n$; otherwise use a sufficiently large finite field extension and an agreed integer encoding. Any $r$ shares determine $P$ by polynomial interpolation and hence $N=P(0)$. Given any $r-1$ shares and any proposed $N$, their equations in the coefficients have a unique solution: the coefficient matrix has determinant ${\prod }_i{x}_i$ times a nonzero Vandermonde determinant. Since the coefficients were uniform, the observed shares have the same distribution for every $N$. Thus they give no information about the secret.

For the fake, reduce its integers to field elements and first check that its abscissa is distinct and nonzero. Random collisions or a zero abscissa are immediately detectable and have probability $O(n/p)$; the following conclusions concern the overwhelmingly likely distinct-abscissa case.

With $r$ shares, there is always a unique degree-at-most-$r-1$ interpolating polynomial. If all shares are genuine it gives the correct secret. If one is fake, it normally gives the wrong secret, with probability $1-1/p$ conditional on a uniform fake ordinate, but the inconsistency is undetectable from those $r$ shares. The data do not certify which case has occurred.

With $r+1$ shares, genuine shares are consistent with one such polynomial. A fake is inconsistent with probability $1-1/p$, so it is usually detected as an inconsistency. However, omitting each of the $r+1$ shares in turn gives $r+1$ possible polynomials. If the data are inconsistent, their constant terms are distinct: two candidate polynomials with the same constant term agree at zero and at their $r-1$ common abscissae, hence agree identically, which would make all the data consistent. The secret is narrowed to $r+1$ possibilities, but the fake is not identified.

With $r+2$ shares, at least $r+1$ are genuine. There is a unique degree-at-most-$r-1$ polynomial agreeing with at least $r+1$ shares: two candidates would agree on at least $r$ abscissae and hence coincide. Find it by deleting each share and checking consistency. The secret is recovered uniquely, and the fake is identified unless it happens to lie on the genuine polynomial, in which case it is harmless.

Use Shamir's secret sharing over the finite field ${\mathbb{F}}_p$. The Chair independently chooses $a_1,\dots ,a_{r-1}$ from the uniform distribution on a finite set ${\mathbb{F}}_p$ and forms the random polynomialChoose distinct nonzero $x_1,\dots ,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 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.

Conditioned on any $r-1$ shares in Shamir's secret sharing, each candidate secret in ${\mathbb{F}}_p$ remains equally likely. Appending $(0,N)$ to those shares determines exactly one degree-at-most-$(r-1)$ polynomial for every candidate $N$, by the nonzero Vandermonde determinant.