# How do you find a single 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 exactly 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 > 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.

In the scenario you describe, any of the non-cheating participants can contact each of the others and arrange to swap shares and reconstruct the secret. (Equivalently, all the participants can agree to publish their shares, at which point any of them can pair their share with each of the others.) If there's only one cheater, the participant who does this will obtain three reconstructed secrets, of which two will agree. The one that does not agree will be the one constructed using the cheater's share.

For a generalization of this method, see "Detection and identification of cheaters in $$(t, n)$$ secret sharing scheme" by Lein Harn and Changlu Lin (2009), Designs, Codes and Cryptography 52(1), pp. 15–24. (But see also this response by Hossein Ghodosi.)

The best answer is to use verifiable secret sharing (VSS), as I describe here: https://crypto.stackexchange.com/a/6618/351

VSS gives the best parameters and best solution to this problem. If you have a $k$-out-of-$n$ secret sharing scheme, VSS can detect any cheater and enable you to reconstruct the secret as long as you have at least $k$ good shares (even if they are mixed together with any number of bogus shares, even if you don't know which are which). This is a better, more effective solution than any of the other schemes proposed here.

Not enough information was provided in the question, so I'm going to assume something to fill in the hole. Let me know if this is not what you envisioned.

Assumption: The party trying to detect the cheater knows the original polynomial used to share the secret.

In the initialization phase, each party $p_i$ is given a pair $x_i, y_i$ where $y_i = f(x_i)$.

In the reconstruction phase, the cheating party (say $p_c$ would submit $x_c, y'_c$ (where $y'_c\neq y_c$).

The party trying to detect the cheater could easily compute $y_c=f(x_c)$, see that what was submitted ($y'_i$) is not equal to $y_i$.

Note: In the scenario you gave, two non-cheating parties could reconstruct the original polynomial and catch the cheater. Those two parties would have to either 1) be able to verify that they correctly reconstructed the secret (e.g., by producing a valid decryption of something), or 2) trust each other enough to believe that the other isn't cheating.

Edit: Given the additional information in the comments below, I chose to expand my answer. Let $R$ be a function which maps two pairs of input to an alleged secret using the reconstruction step. Since you have all 4 pairs $\{(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_c,y_c)\}$, you can compute the following:

• $S_{1,2}=R(x_1,y_1,x_2,y_2)$
• $S_{1,3}=R(x_1,y_1,x_3,y_3)$
• $S_{1,c}=R(x_1,y_1,x_c,y_c)$
• $S_{2,3}=R(x_2,y_2,x_3,y_3)$
• $S_{2,c}=R(x_2,y_2,x_c,y_c)$
• $S_{3,c}=R(x_3,y_3,x_c,y_c)$

Comparing these values you would notice three important things:

1. $S_{1,2}=S_{1,3}=S_{2,3}$
2. $S_{1,c}\neq S_{2,c}\neq S_{3,c}$
3. $S_{i,c}$ is not equal to the value in (1)

Since when $c$ participates, the output changes depending on the other party, clearly $c$ is the cheater.

• No, only the x and f(x) values are given. I was going to use a Lagrange expansion to solve the polynomial, but then I realized I did not know how to catch the cheater. Dec 16, 2011 at 2:37
• Is that x and f(x) of only 2 parties, or more? Dec 16, 2011 at 2:50
• All four parties. But only two should be needed to figure out the secret. Dec 16, 2011 at 2:52
• Can you guarantee that only 1 party will cheat? Dec 16, 2011 at 3:00
• Yes, there is only one cheater. Dec 16, 2011 at 3:01