Undetectable cheater in Shamir's Secret Sharing scheme

Consider Shamir's Secret Sharing scheme with $n=5, t=3$ (i.e, there are 5 shares, and when we have 3 of them we can reconstruct our secret $s$). Let $f(x)$ be the dealing function, i.e the secret $s$ is defined as $s = f(0)$.

We assume that given 3 participants who gather together in order to reveal the secret, one of them wants to cheat in the manner of preventing the other 2 participants from revealing the secret. He doesn't care about the secret itself - he just want to sabotage the revealing of $s$.

I want to prove formally that neither of the 2 honest participants can detect who is the cheater.

My current lead is this: in the revealing process - using Lagrange's interpolation - each participant reveals his tuple $\left(x_i, f\left(x_i\right)\right)$ (where WLOG $\forall i : x_i \in \{1,2,3\}$), or perhaps just the unique function for that participant ($f_j(x) = y_j \cdot \prod_{1 \leq i \leq 3, i\neq j}\frac{x-x_i}{x_j - x_i}$ where eventually $\tilde{f}(x) = \sum_{j=1}^3 f_j(x)$ ) - but reconstructing this way only reveals a function $\tilde{f}(x)$ which they find out to be useless (when they try to use $\tilde{s}=\tilde{f}(0) \neq s$). It seems very intuitive that an honest participant cannot tell which $f_j(x)$ messed everything up, but I don't manage to write it formally. would appreciate some help... thanks.

2 Answers

The way to prove this is to follow the same proof that Shamir's secret sharing is perfectly secret. Specifically, given any two points all secrets are possible since there is a polynomial going through every possible secret and the two given points. Since the polynomial is random, all of these polynomials have the same probability. The same thing is happening here: given any set of three points, there is a polynomial going through those three points. Now, assume that you know exactly what the secret is. If you look at any subset of two of the three points, there is a polynomial going through those two points and the secret that you know. Thus, it is impossible to know which of the three parties is cheating, even if you actually know the secret you are supposed to get.

You are already on the right path. You can use the fact that having two of three shares does not reveal any information about the secret (polynomial). Also see the Wikipedia article [1] on Shamir's secret sharing: it provides you with a nice graphical answer to your question.

References

• thanks. though I'm not sure how it helps me - my goal is to prove that we cannot detect who's the cheater. Revealing the secret is not the issue. – noamgot Jan 7 '18 at 19:48
• I know, but you can use this fact to argue about why you can not detect the cheater. – dade Jan 7 '18 at 19:54
• Here's what I know so fat - the honest participants have only 2/3 valid shares, hence they cannot gain any information about the real secret. I understand intuitively that each of them cannot distinguish between the cheater and the other honest participant, but I can't put my finger on the reason why. I tried to go to probabilistic analysis (to show that the in the eyes of an honest participant the other 2 can cheat with equal probability), but I got stuck there too... – noamgot Jan 7 '18 at 20:15