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)
“Television programming for children need not be saccharine or insipid in order to give to violence its proper balance in the scheme of things.... But as an endless diet for the sake of excitement and sensation in stories whose plots are vehicles for killing and torture and little more, it is not healthy for young children. Unfamiliar as yet with the full story of human response, they are being misled when they are offered perversion before they have fully learned what is sound.”
—Dorothy H. Cohen (20th century)