Secret Sharing - Shamir's Scheme

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)