6
$\begingroup$

I'm having trouble solving the Shamir's Secret Sharing scheme for the following problem that states:

Problem: A certain military office, which is in control of a powerful missile, consists of six generals, five colonels, and four desk clerks. Describe how they would set up a Shamir scheme so that any five generals or any set of four colonels and three desk clerks or any three generals and three desk clerks can launch the missile.

I was thinking that this looks like the Shamir's scheme definition where the secret S was divided among the three groups( $n=3$? ), and so I need to describe the process of obtaining the threshold scheme $(k, n)$, the $k$ shares from the given problem? Or am just confusing myself further. Any help of approaching this problem would be helpful.

Improve this question
$\endgroup$
5
  • $\begingroup$ First try: desk clerks get one share each, colonels get two, generals get three, and eleven shares are required to unlock the secret. That doesn't work; for example four generals can unlock the secret, while five should be required. Take it from there. $\endgroup$
    – fkraiem
    Commented Nov 26, 2017 at 2:01
  • $\begingroup$ Sorry for the late reply, but I am still trying to wrap my head around this, my book isn't helpful. So after looking at what you stated above, I tried: General: 2 shares, Colonels: 1 shares, and Desk clerks: 2 shares? Also where is the 11 shares coming from? $\endgroup$
    – KonoDDa
    Commented Nov 28, 2017 at 0:02
  • $\begingroup$ I chose eleven as a first try because that's what four colonels and three desk clerks have. $\endgroup$
    – fkraiem
    Commented Nov 28, 2017 at 0:08
  • $\begingroup$ Oh, then I think I was on to something, because I chose 10 shares, as in what I got after assigning my shares from above. Where four colonels and three desk clerks gives me 10. So then each of the desired groups, and no smaller groups, have the 10 shares needed to launch the missile. $\endgroup$
    – KonoDDa
    Commented Nov 28, 2017 at 0:16
  • $\begingroup$ What about one general plus four desk clerks? $\endgroup$
    – fkraiem
    Commented Nov 28, 2017 at 8:47

2 Answers 2

Reset to default
7
$\begingroup$

Each person might be allotted more than one share of the secret.

Let $G$, $C$ and $D$ denote the number of shares allotted to a General, a Colonel, and a Desk Clerk respectively, and let $T$ denote the Threshold of the secret sharing scheme. Then, we have that \begin{align} T &\leq 5G,\\ T &\leq 4C + 3D,\\ T &\leq 3G + 3D. \end{align} Can you find suitable values for $G,C,D$,and $T$? The total number of shares is $N = 6G + 5C + 4D$ and we have a $(T,N)$ secret sharing scheme.

$D=2, C=3, G=4, T=18$, and $N = 47$ seems to work. There are, of course, other combinations that would result in $18$ or more shares, e.g., $5C+2D$ or $4G+D$ but nothing in the problem statement says that this is not to be allowed. Note that the $5$ colonels (or the $4$ Desk Clerks for that matter) cannot stage a coup by themselves; the colonels have to have at least two Desk Clerks (or a General) as co-conspirators.

Addendum: in the spirit of @IlmariKaronen's answer,

  • Divide the secret $S$ into 6 shares in a $(5,6)$ secret-sharing scheme and give each of the six generals a share. Any 5 of them can reconstruct $S$.

  • Create a random binary vector $X$ as long as the secret $S$, and then make five shares of $S\oplus X$ in a $(4,5)$ secret-sharing scheme, giving one share to each colonel. Any four of them can reconstruct $S\oplus X$. Create $4$ shares of $X$ in a $(3,4)$ secret-sharing scheme and hand one share to each desk clerk. Any $3$ desk clerks can reconstruct $X$, and together with $S\oplus X$ from the $4$ colonels, $S$ can be reconstructed.

  • Create $6$ shares of $S\oplus X$ in a $(3,6)$ secret-sharing scheme and hand a share to each general. Any three generals can reconstruct $S\oplus X$, and together with $X$ from three desk clerks, can recreate $S$.

Note that this has have fewer secret-sharing schemes to implement than Ilmari's method, and the desk clerks and colonels have only one share to have and hold. Only the generals have two different shares and must remember to use the correct one in the two different cases when they are acting by themselves and when in conjunction with three desk clerks. Also, the desk clerks, by themselves, can only reconstruct $X$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ While this is a clever answer, the fact that, as you note, there are other groups that can reconstruct the secret besides the specified ones feels kind of unsatisfactory. True, the question doesn't explicitly forbid that, but if we're willing to be that literal, wouldn't it be easier to just straight up tell everyone the secret? After all, the question doesn't explicitly say that a single desk clerk shouldn't be able to launch the missile... $\endgroup$
    – Ilmari Karonen
    Commented Nov 29, 2017 at 15:50
  • $\begingroup$ @IlmariKaronen Yes, the question doesn't explicitly say that one desk clerk should not be able to launch the missile, but the implication is clearly that 4 generals should not be able to launch, or that if either fewer than 4 colonels or 3 desk clerks are present, etc., then the launch is impossible. As you say, your solution requires a lot of intelligence on the part of the generals and the desk clerks; they have to know which shares they have to submit depending on who else is in the room; the dumb-cluck colonels have only one kind of share and are spared any intellectual effort. $\endgroup$
    – Dilip Sarwate
    Commented Nov 29, 2017 at 15:59
4
$\begingroup$

It's not clear from the question whether we're allowed to use more than one instance of Shamir's scheme. If yes, this problem can be solved in a straightforward manner:

  1. Share the launch code using a 5-out-of-6 scheme; give one share to each general.
  2. Share the launch code using a 2-out-of-2 scheme.
    • Re-share the first of the two shares using a 4-out-of-5 scheme, and give one of the resulting subshares to each colonel.
    • Re-share the second of the two shares using a 3-out-of-4 scheme, and give one of the resulting subshares to each desk clerk.
  3. Again share the launch code using a 2-out-of-2 scheme.
    • Re-share the first of the two shares using a 3-out-of-6 scheme, and give one of the resulting subshares to each general.
    • Re-share the second of the two shares using a 3-out-of-4 scheme, and give one of the resulting subshares to each desk clerk.

As required, this hierarchical secret sharing scheme clearly allows any of the following groups to reconstruct the launch code:

  1. any five generals;
  2. any four colonels and any three desk clerks; or
  3. any three general and and three desk clerks.

It's also not hard to prove, using the information-theoretic security property of Shamir's secret sharing, that no other groups (that do not include any of the above as subgroups) can learn any information about the launch code from their shares.

Improve this answer
$\endgroup$

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.