Shamir's Scheme
In this scheme, any t out of n shares may be used to recover the secret. The system relies on the idea that you can fit a unique polynomial of degree (t-1) to any set of t points that lie on the polynomial. It takes two points to define a straight line, three points to fully define a quadratic, four points to define a cubic curve, and so on. That is it takes t points to define a polynomial of degree t-1. The method is to create a polynomial of degree t-1 with the secret as the first coefficient and the remaining coefficients picked at random. Next find n points on the curve and give one to each of the players. When at least t out of the n players reveal their points, there is sufficient information to fit a (t-1)th degree polynomial to them, the first coefficient being the secret.
Read more about this topic: Secret Sharing
Famous quotes containing the words shamir and/or scheme:
“Our image has undergone change from David fighting Goliath to being Goliath.”
—Yitzhak Shamir (b. 1915)
“We are all bound to the throne of the Supreme Being by a flexible chain which restrains without enslaving us. The most wonderful aspect of the universal scheme of things is the action of free beings under divine guidance.”
—Joseph De Maistre (17531821)