Shamir's (m,n) secret sharing scheme has a secret $s_0$ which is represented as an element of a finite field $\mathbb F_q$ of $q$ elements. There are also $m-1$ other "randomly chosen" elements $s_1, s_2, \ldots, s_{m-1}$ that the designer uses. The scheme creates a
polynomial
$$S(x) = s_0 + s_1x + \cdots + s_{m-1}x^{m-1}$$ and evaluates $S(x)$ at $n$
distinct nonzero
elements $\alpha_1, \alpha_2, \ldots, \alpha_n$. Note that $n$ must be at least
as large as $m$ and cannot be larger than
$q-1$. The $n$ pieces of the secret that are handed out to those sharing in the
secret are just these polynomial values $S(\alpha_1), S(\alpha_2), \ldots, S(\alpha_n)$.
Given $m$ of the $n$ shares, the Lagrange interpolation formula gives the unique
polynomial $T(x)$ of degree $m-1$ or less that interpolates through these $m$ points,
that is, for each share $[\alpha_j, S(\alpha_j)]$ that is available to the reconstructor,
$T(\alpha_j)$ equals the share value $S(\alpha_j)$. Therefore, $T(x)-S(x)$ is a
polynomial of degree $m-1$ or less that has $m$ roots in the field, and by the
Fundamental Theorem of Algebra, must be zero. Thus, $T(0) = s_0$ is the secret.
If $m$ shares are available, the secret can be recovered.
If more than $m$ shares are available, any $m$ of them can be used
to reconstruct the secret. Shamir also showed that if fewer than
$m$ shares are available, then
the secret cannot be recovered; in fact, all possible $q$ values of
the secret are equally likely to be obtained if one interpolates through
fewer than $m$ shares.
The McEliece-Sarwate generalization of this scheme via Reed-Solomon
codes has two aspects.
First, by using the error-correcting properties
of Reed-Solomon codes, it is possible to recover the secret even if
some of the shares are in error. Here, error means that the
shareholder submits a share value that is different from the value
given to him/her. Such errors could be due to malice, or could occur
because of accident (e.g. a flash drive holding the
share is forgotten in a pocket and gets washed in a clothes-washer).
In the standard Shamir reconstruction, damaged shares are no different
from valid shares and Lagrange interpolation will almost always
reconstruct a "secret" that is different from the original. Unless
there is error control built into the secret (e.g. a CRC checksum),
there is no way of knowing that the recovered "secret" is different
from the original. On the other hand, the properties of Reed-Solomon
codes say that if $m+t$ shares are available of which at most
$\lfloor t/2\rfloor$ are in error, then by using a Reed-Solomon
decoding algorithm, the secret can be successfully recovered. The
reconstructor does not need to know which shares are in error (if
this were known, the damaged shares could just be ignored!). The
decoding algorithm also indicates which shares, if any, of the
$m+t$ submitted shares are in error, that is, cheaters (or launderers!)
can be identified, and of course the correct share values can be
computed and given to the innocent share holders on new flash drives.
It is also true that if more than $\lfloor t/2\rfloor$
shares are in error, the Reed-Solomon decoding algorithm will quite likely
refuse to reconstruct a secret, and will reconstruct a "secret"
different from the original only in rare circumstances. Note that
a failure to reconstruct a secret is not fatal (unless $m+t = n$)
since one can always await the submission of more valid shares so
that the effect of the invalid ones can be overcome. In this form,
there is no difference between the security of the Shamir scheme and
the Reed-Solomon coding scheme.
The second aspect of Reed-Solomon coding schemes considered
in the McEliece-Sarwate paper is that it is not necessary to
fill up $S(x)$ with $m-1$ randomly chosen symbols. In fact,
the secret can be all $m$ symbols $s_0,\ldots,s_{m-1}$ instead
of just $s_0$ being the secret. One advantage is that we can
use a smaller finite field. If the secret is $1000$ bits, say,
and $m=10$, Shamir's scheme would operate over $\mathbb F_{2^{1000}}$
and each share of the secret would also be $1000$ bits long.
$10$ kilobits ($10$ one-kilobit shares) would be needed to
recover the secret. On the other hand, a Reed-Solomon coding
scheme could divide the secret into $10$ $100$-bit symbols and
operate over $\mathbb F_{2^{100}}$. Also each share would
be $100$ bits long, and, as before, only ten such short shares
would be needed to recover the secret. This reduction in the
field size does come at some cost in security. If only $9$
shares are available to a cabal and they guess at possible
values of the tenth needed share, they can come up with a
"short list" of only $2^{100}$ values that the $1000$-bit secret might
have. Shamir's scheme in a similar predicament would have
a list of $2^{1000}$ possible values of the secret, thus
providing perfect security. The trade-off between reduction
in security and ease of implementation as well as storage of
each share of the secret is something that needs to be evaluated
for each application. The most secure scheme has shares that
are as long as the secret while the Reed-Solomon scheme can
be used to reduce the share size at the cost of reduced
security.
Edit Another version of secret-sharing gives the $i$-th share
holder the value of $\alpha_i$ as well as the share $S(\alpha_i)$
(this requires twice as much storage). Thus, $m$ share holders
can reconstruct the secret if they know Lagrange interpolation
and have access to a computer that does the needed finite-field
arithmetic without anyone else knowing about it. In the standard
scenario, the $i$-th
share holder only has $S(\alpha_i)$ without any knowledge of
$\alpha_i$, and only an official reconstructor knows that Joe
Blow is the $i$-th share holder and looks up $\alpha_i$ when
Joe submits his share for reconstruction purposes.
In this case, secret re-construction
can only be done by the official re-constructor; a cabal
of $m$ rebellious share holders cannot reconstruct the secret
in private and use it to overthrow the Evil Empire.
When share holders actually have $[\alpha_i,S(\alpha_i)]$,
a cheater could alter either quantity or both, and an innocent
error might do likewise. The solution to this problem is more
difficult. For what can be done in such
cases, see, for example, here.
