Threshold Scheme

Let with . An -threshold scheme is a method of sharing a message among a set of participants such that any subset of participants can reconstruct but no subset of smaller size can.

Shamir’s method

Let be the secret which can be chosen at random by the Leader. The Leader chooses a prime . The Leader chooses independent random coefficients with where , and distinct integers with Define:

The member receives a shadow pair

Now suppose members are together. They have the data where and and can solve:

because the Vandermonde matrix has nonzero determinant

Then so

However, if only members are present then:

Which can be solved for any so we have no idea which one is correct.