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 hold these truths to be self-evident:
That ostracism, both political and moral, has
Its place in the twentieth-century scheme of things....”
—John Ashbery (b. 1927)