Devise a scheme so that a message M can be shared among X, Y and Z in such a say that the only way of recovering the message is when X is present with either Y or Z. When X isn't present or each is alone, they will not be able to recover the shared secret.

Additionally, generalize the above to devise a scheme so that a M can be shared among 5 entities such that the only way of recovering the secret is when either X and Y are both present or when C, D, E are all present together.

I have no idea how to create a hierarchy such as what is being proposed. Any ideas?

  • $\begingroup$ Is this homework? $\endgroup$ – poncho Apr 9 '14 at 1:28
  • $\begingroup$ No, or at least not that I am aware of. This was a question that was told to me by a friend when discussing secret sharing. I had no idea where to even begin, so I figured someone here might have some idea. $\endgroup$ – user2266603 Apr 9 '14 at 1:36

This is actually a fairly trivial case of secret sharing:

In the first case, we select a random value $R$, we give $X$ the value $R \oplus M$, and we give both Y and Z the value $R$. Obviously, $X$ alone, nor $Y$ and $Z$ together cannot reconstruct $R$.

In the second case, we select random values $R_1$, $R_2$ and $R_3$, we give:

  • $R_1 \oplus M$ to $X$

  • $R_1$ to $Y$

  • $R_2 \oplus R_3 \oplus M$ to $C$

  • $R_2$ to $D$

  • $R_3$ to $E$

Shamir Secret Sharing is a neat trick; however sometimes problems can be solved by simpler methods.

  • 1
    $\begingroup$ Thank you! It was one of those things where I was overthinking how difficult the question was. Now that you've stated this, the logic behind it is quite obvious. I think I was also thinking that each entity would have to have a distinct value. Thanks again! $\endgroup$ – user2266603 Apr 9 '14 at 10:57

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.