1

I have this problem of sharing a secret code $n\in\mathbb{Z}$ such that $0\le n\le250$ among five people.

There are 5 people, each one of whom receives a secret number $s_i$, $1\le i\le 5$ such that $0\le s_i \le 250$.

What is a good scheme that allows any 3 people to come together and recover the code, but any 2 people will have absolutely no idea of what the code is?

Any help will be greatly appreciated.

user12488
  • 425

1 Answers1

1

The problem you mention is called Secret Sharing. In general, Secret sharing is the problem of finding a set of keys to give to $n$ persons such that only sets containing $m$ people or more are able to decipher the thing. See the link for details (including possible algorithms such as Shamir's Secret Sharing).

Irvan
  • 2,208
  • Thank you Irvan. I attempted Shamir's secret sharing. Assuming that the secret is 42. I construct a polynomial P(x) = 42 + 5x + 7x^2 (where 5 and 7 are arbitrary), and give each of the five people a pair (1, P(1)), (2, P(2)), ..., (5, P(5)). This works, except that the P(i)s do not necessarily satisfy 0 <= P(i) <= 250. – user12488 Oct 30 '14 at 10:25
  • I understand that I have to work around with Shamir's Secret Sharing Scheme in mod 251, but currently have no idea of where to begin. – user12488 Oct 30 '14 at 10:26