What is Shamir's Secret Sharing Scheme?

Shamir's secret sharing scheme [Sha79] is an interpolating scheme based on polynomial interpolation. An (m - 1)-degree polynomial over the finite field GF(q)

F(x) = a₀ + a₁x + ... + a_m - 1 x^m-1

is constructed such that the coefficient a₀ is the secret and all other coefficients are random elements in the field. (The field is known to all participants.) Each of the n shares is a point (x_i, y_i) on the curve defined by the polynomial, where x_i not equal to 0. Given any m shares, the polynomial is uniquely determined and hence the secret a0 can be computed. However, given m - 1 or fewer shares, the secret can be any element in the field. Therefore, Shamir's scheme is a perfect secret sharing scheme (see Question 103).

A special case where m = 2 (i.e., two shares are required for retrieval of the secret) is given in Figure 9. The polynomial is a line and the secret is the point where the line intersects with the y-axis. Each share is a point on the line. Any two shares (two points) determine the line and hence the secret. With just a single share (point), the line can be any line that passes the point, and hence the secret can be any point on the y-axis.

| Question 105 |