Shamir's Secret-sharing Scheme
The essential idea of Adi Shamir's threshold scheme is that 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve and so forth. That is, it takes points to define a polynomial of degree .
Suppose we want to use a threshold scheme to share our secret, without loss of generality assumed to be an element in a finite field of size where is a prime number.
Choose at random coefficients in, and let . Build the polynomial . Let us construct any points out of it, for instance set to retrieve . Every participant is given a point (a pair of input to the polynomial and output). Given any subset of of these pairs, we can find the coefficients of the polynomial using interpolation and the secret is the constant term .
Read more about this topic: Shamir's Secret Sharing
Famous quotes containing the words shamir and/or scheme:
“Should there be maniacs who raise the idea, they will encounter an iron fist which will leave no trace of such attempts.”
—Yitzhak Shamir (b. 1915)
“We doubt not the destiny of our country—that she is to accomplish great things for human nature, and be the mother of a nobler race than the world has yet known. But she has been so false to the scheme made out at her nativity, that it is now hard to say which way that destiny points.”
—Margaret Fuller (1810–1850)