= Perfect secrecy of Shamir's threshold scheme
{c}
In <Shamir's secret sharing>, observing any $t<r$ shares leaves the secret's prior distribution unchanged. In particular, the posterior distribution is uniform if the prior distribution was uniform; uniformity of the secret is not required for <perfect secrecy>.
To prove this, fix $t$ distinct nonzero evaluation points and a candidate secret $S=u$. The $t$ evaluations impose $t$ independent <linear equations> on the $r-1$ random coefficients. The evaluation <matrix> has <rank> $t$: its first $t$ columns form a <Vandermonde matrix> multiplied by a nonsingular <diagonal matrix> of nonzero evaluation points. Every observed share tuple therefore has exactly $q^{r-1-t}$ compatible coefficient tuples. Since the coefficients were independently uniform, its conditional <probability> is
$$
\Pr(\text{these shares}\mid S=u)=q^{r-1-t}/q^{r-1}=q^{-t},
$$
independent of $u$. Thus the shares and the secret are <independent random variables>, which proves <perfect secrecy>.<How to Share a Secret by Adi Shamir>[Pages 612–613: interpolation argument for fewer than the threshold number of shares]{ref}
Back to article page