0

Suppose that I want to break up a secret into shares such that any set of k people can recover the secret, but I’m also worried that some people might be dishonest and may lie about the secrets they have (in order to prevent the other people from recovering the correct secret). Show that in the ordinary secret sharing scheme based on polynomials, any group of k+2 people can recover the secret even if one of them is dishonest.

*I am confused about how to approach this proof. Maybe proof by induction? But I don't know what to write for the inductive step thereafter.

Daniel Synn
  • 1
  • This should be moved to crypto.SE. The short answer is that this problem is discussed and solved in the paper R. J. McEliece and D. V. Sarwate, "On sharing secrets and Reed-Solomon codes," Communications of the ACM, vol. 24, no. 9, pp. 583-584, September 1981. – Dilip Sarwate Oct 07 '13 at 13:35
  • This is more or less a repeat of another question by the same user. Why did you post it new? Why didn't you edit the other one? That's how things are done here! – Jyrki Lahtonen Oct 07 '13 at 19:22
  • Anyway, this is the better version, as you discuss it a bit, so I am voting to close the earlier one as a duplicate. I also repeat my suggestion: think how it goes, when $k=1$ or $k=2$. That will give you the idea. In general this is an example of using a Reed-Solomon code of minimum distance 3 (hence capable of correcting a single error). – Jyrki Lahtonen Oct 07 '13 at 19:24

1 Answers1

1

Just a hint:

The shared secret is a polynomial with order k, so you need just k distinct points on it find the answer. With k+2 people, how many sets of k people can you make? Of those sets, what shared secret does each set compute?

Eyal
  • 141