3
$\begingroup$

Consider the Shamir Secret Sharing scheme based on polynomial interpolation.

In this scheme, every part has the same right: one piece of information of same value as the other ones.

The idea is to adapt this scheme in following way:

Suppose that we want to share a secret among politicians and generals. The secret can only be retrieved if 3 elements are united and if in that group at least one is a politician and at least one is a general.

How can we do that? It is not clear to me what to do. Thanks in advance.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Hint: first consider this easier problem: suppose that you want them to retrieve the secret only If at least one politician and one general agree; how would you do that? $\endgroup$
    – poncho
    Commented Jun 28, 2017 at 17:53

1 Answer 1

Reset to default
6
$\begingroup$

Let's say your secret is $S$. Split $S$ into 3 parts (say $S_1,S_2,S_3$) such that $S=S_1\oplus S_2\oplus S_3$.

Give each politician a copy of $S_1$, each general a copy of $S_2$, then split $S_3$ using 3-out-of-n Shamir Secret sharing.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Note that you could pick $S_1,S_2$ uniformly at random of the correct size and compute $S_3=S_1\oplus S_2\oplus S$ as an instantiation of the "Split $S$" operation. $\endgroup$
    – SEJPM
    Commented Jun 28, 2017 at 18:58
  • 1
    $\begingroup$ What do you mean by $\oplus$? Is it $S=(S_1,S_2,S_3)$? E.g. if $S_1=123$, $S_2=456$ and $S_3=789$, then $S=123456789$? $\endgroup$
    – Leafar
    Commented Jun 28, 2017 at 18:59
  • 1
    $\begingroup$ @Leafar $\oplus$ means bit-wise XOR. $\endgroup$
    – SEJPM
    Commented Jun 28, 2017 at 18:59
  • 2
    $\begingroup$ Yes, that was the doubt, however, it seems that it works as I stated, but of course each politician/general will know 1/3 of the secret. With the XOR each politician/general knows nothing about the secret, which is better $\endgroup$
    – Leafar
    Commented Jun 28, 2017 at 19:05
  • 2
    $\begingroup$ @Leafar, yeah, letting a politician know a 1/3 of a secret is probably worse than letting them know a whole secret as they will fill in the gaps with whatever makes them look best ;) $\endgroup$
    – mikeazo
    Commented Jun 28, 2017 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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