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)
“I have no scheme about it,—no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?—and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
—Henry David Thoreau (1817–1862)