How do you find a cheater in Shamir Secret Sharing? If there are 4 people involved, and every two of them should be able to know the secret (the polynomial is just a line) and you are given $f(x)$ and $x$ for each of those people, and you know one of them is a cheater, how do you find the cheater?
Shamir's secret-sharing scheme has $n$ shares of a secret.  The shares are of the form $(x_0,f(x_0)), (x_1,f(x_1)), \ldots , (x_{n-1},f(x_{n-1}))$ where the $x_i$ are $n$
distinct nonzero elements of a finite field $\mathbb F$, and $f(x)$ is a polynomial of
degree $k-1$ with coefficients in $\mathbb F$. One coefficient, say $f_0$, of 
$f(x)$ is the secret being shared and the remaining $k-1$ coefficients are chosen at random.  Note that the while the $i$-th share is constructed as $(x_i,f(x_i))$, 
what the owner of the $i$-th share  sees is just a pair $(x_i,y_i)$ of
elements of $\mathbb F$, that is, while the owner knows that $y_i = f(x_i)$, 
the owner has no other knowledge about $f$.  

Given any set of $k$ shares $\{(x_{i_j},y_{i_j}) \colon 1 \leq j \leq k\}$,
there is a unique polynomial $g(x)$ of at most degree $k-1$ that interpolates through these $k$ points, that is, enjoys the property $g(x_{i_j}) = y_{i_j}$
for $1 \leq j \leq k$, and
this polynomial can be found, for example, through Lagrange interpolation.
Since $f(x)$ is of degree $k-1$ (or less if the random choice of $f_{k-1}$
resulted in $f_{k-1}=0$) and also has the property that $f(x_{i_j}) = y_{i_j}$
for $1 \leq j \leq k$, it follows that the $g(x)$ that has been interpolated
is the same as $f(x)$, and thus $g_0$ is the secret.  If fewer than $k$ shares 
are available, the $g(x)$ that is recovered is not the same as $f(x)$.

If $m &gt; k$ shares are available, we can interpolate through any $k$
of them and recover the secret.  For the application on hand, if it 
is known that there is one (or at most one) cheater, and the 
cheater's share  may have the wrong value for $x_i$ or $y_i$
or both, proceed as follows.


If two shares are identical, one of the two shares belongs
to the cheater but it is not possible to
determine who is the cheater. Fortunately, the secret is 
recoverable if at least $k+1$ shares are available (that is,
$k$ distinct correct shares are available).  Of course, in
a different scenario, the reconstructor may know the identity
of each share owner, and so know that the $j$-th owner should
not be "turning in" a share in which the first symbol is $x_i$,
and thereby identify the cheater right away.
If there are two shares $(x_i,y_i)$ and $(x_i,y_j)$, then
one of them belongs to the cheater.  If $m \geq k+2$, interpolate 
through a set of $k$ shares excluding these two to recover $f(x)$.
Calculate $f(x_i)$ and check which of the two possible cheater
shares matches $(x_i,f(x_i))$: the other belongs to the cheater.
Again, in the different scenario,  $(x_i,y_j)$ could be identified
right away as the cheater's share since the $j$-th owner should not
be turning in a share with $x_i$.
If all $m \geq k+2$ shares have different (and correct)
$x_i$ values, interpolate 
through the $\binom{m}{k}$ different subsets of $k$ shares.
$\binom{m-1}{k}$ of these subsets will not contain the cheater's
share and all these interpolations will recover the same $g(x) = f(x)$. 
The other interpolations will be through the cheater's share and
will give different interpolating polynomials.  It can be shown
that fewer than $\binom{m-1}{k}$ of these interpolations can 
result in the same (but incorrect) $\hat{g}(x)$, that is,
in the $\binom{m}{k}$ interpolating polynomials resulting from
the $\binom{m}{k}$ different subsets, the correct polynomial
$f(x)$ will occur most often (win by a plurality but not
necessarily a majority).  Having found $f(x)$, simply reconstruct
the $m$ shares $(x_i,f(x_i))$ and compare to the ones "turned in"
to identify the cheater.  Alternatively, the union of the
$\binom{m-1}{k}$ subsets of shares that gave $g(x) = f(x)$
is the set of $m-1$ correct shares, and the complement is the
unique cheater's share.


More generally, if there can be as many as $t$ cheaters
it can be shown that the secret can be recovered and
the cheaters identified if $k+2t$ shares are available for
reconstruction.  Note that as many as $t$ of these $k+2t$
shares might be cheaters' shares.  Put another way, if
there can be as many as $t$ cheaters, we need at least
$k+t$ honest shares available (in addition to the $t$
possible cheaters) to be able to recover the secret and
identify the cheaters.

The proofs of assertions about plurality can be found
in the paper I.S. Reed and G. Solomon, "Polynomial 
codes over certain finite fields,"  SIAM J. Appl. Math.,
v. 8, pp.300-304, 1960.  The original application of 
Reed-Solomon codes to secret sharing (and suggestions
for more efficient recovery than multiple Lagrange interpolations)
can be found in R.J. McEliece and D.V. Sarwate, On sharing 
secrets and Reed-Solomon codes, Communications of the ACM, 
v. 24, Issue 9, Sep 1981.