We consider a $(2, 6)$ Shamir secret sharing scheme over $Z_{11}$. Four players $A,B,C,D$ cooperate to find the secret, but one of them is cheating (so the share he claims to have might not be an actual share). They claim that their shares are;

$$A:(1,2)\quad B:(2,5)\quad C:(3,10)\quad D:(4,3)$$ Who is cheating and what is the secret?

I am using 4 equations:

\begin{aligned} 2 &= s + a & (1)\\ 5 &= s + 2a &(2)\\ 10 &= s + 3a &(3)\\ 3 &= s + 4a &(4) \end{aligned}

And solving for $s$ and $a$.

I don't seem to know the exact approach? How do I go about solving this problem?

  • $\begingroup$ Hint: you need only two shares to recover the secret. What happens if you try the shares from AB, AC, AD? $\endgroup$ – fkraiem Apr 23 '19 at 6:41

You have four equations and two unknowns. Any two of those equations should therefore be solvable, and all pairs that don't include the cheater should yield the same solution.

(You don't actually need to solve all six possible pairs of equations if you know there's at most one cheater. It's sufficient to e.g. just solve equations 1 & 2, and check which of 3 & 4 fails to fit the solution. If both fail, solve 3 & 4 instead, and check which of 1 & 2 fails to fit.)

Also, remember that you will need to solve all those equations in $\mathbb Z_{11}$, i.e. using arithmetic modulo 11.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.