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.

$\endgroup$
  • 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 Jun 28 '17 at 17:53
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.

$\endgroup$
  • 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 Jun 28 '17 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 Jun 28 '17 at 18:59
  • 1
    $\begingroup$ @Leafar $\oplus$ means bit-wise XOR. $\endgroup$ – SEJPM Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 at 19:22

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.