### Question 104. 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*_{0} + *a*_{1}*x* + ... + *a*_{m} -
1 *x*^{m}^{-1}

is constructed such that the coefficient *a*_{0} 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 *a*0 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).

Figure 9. Shamir's secret sharing scheme

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.