1
$\begingroup$

Consider 6 people, $A,B,C,D,E,F$ and a secret. Construct a scheme which enables the following subsets of people to retrieve the secret:

three players from the set $\{A,B,C,D\}$

two players from the set $\{A,E,F\}$

two players from the set $\{B,C,D\}$ together with at least one player from the set $\{A,E, F\}$.

I want to know how I can distribute $6$ shares amongst these people so that the secret can only be obtained when three shares come together i.e a threshold of three. I've tried so many options but there always seems to be one unauthorised subset that gains access to the secret that causes it not to work. For example if I label the shares $1,2,3,4,5,6$ and distribute them like the following:

$A - 1$

$B- 2$

$C - 3$

$D - 6$

$E - 2,5$

$F - 3,4$

Then the unauthorised set $\{D,F\}$ for example will have three shares and be able to recover the secret. Is there a way to distribute them so that only authorised subsets can gain access to the secret?

$\endgroup$
2
$\begingroup$

Well, the easiest way I can see to represent this access structure is:

  • Select three random values $r_1, r_2, r_3$

  • Generate a threshold-2 secret sharing scheme with the secret $S$ (where $S$ is the ultimate secret), and whose shares are $\alpha_1, \alpha_2, \alpha_3$

  • Generate an independent threshold-2 secret sharing scheme with the secret $r_3$, and whose shares are $\beta_1, \beta_2, \beta_3$.

Then,

  • $A$ gets $\alpha_1$, $r_3 \oplus S$

  • $B$ gets $r_1$, $\beta_1$

  • $C$ gets $r_2$, $\beta_2$

  • $D$ gets $r_1 \oplus r_2 \oplus S$, $\beta_3$

  • $E$ gets $\alpha_2$, $r_3 \oplus S$

  • $F$ gets $\alpha_3$, $r_3 \oplus S$

It's easy to see that any of the allowed subsets can recover $S$ (e.g. for the subset $A, B, C$, they jointly know $\beta_1$ and $\beta_2$, that allows them to recover $r_3$; and with $r_3 \oplus S$ gives them $S$). It should be fairly clear that any subset not within the access structure gets no information about $S$.

This doesn't give an answer to the precise question to raised; it does appear to solve the problem you were trying to address.

$\endgroup$
  • $\begingroup$ What is the purpose of distributing $r_1$ and $r_2$? and how is $r_1 \oplus r_2 \oplus S$ of use to player $D$? $\endgroup$ – harry55 Apr 27 '17 at 12:21
  • $\begingroup$ @harry55: one of the requirements is that the set of players $\{B, C, D\}$ could recover the secret (as those are 3 of the set $\{A, B, C, D\}$). $r_1, r_2, r_1 \oplus r_2 \oplus S$ allows that specific set to do so. $\endgroup$ – poncho Apr 27 '17 at 14:03
  • $\begingroup$ Yes Why do we use a scheme for the distribution of the $\alpha$s and $\beta$s but not the $r$'s? $\endgroup$ – harry55 Apr 28 '17 at 6:53
  • $\begingroup$ @harry55: because both $\alpha, \beta$ are part of a (2 out of 3) scheme; for $r$, it's really a (3 out of 3) scheme; while Shamir could do it, it's really overkill... $\endgroup$ – poncho Apr 28 '17 at 12:36
2
$\begingroup$

The trivial, mechanistic solution would be to:

  1. Create 4 shares of the secret, with reconstruction threshold 3, and give them to A, B, C and D.

  2. Separately, create 3 shares of the secret with threshold 2, and give them to A, E and F.

  3. Create 2 shares of the secret with threshold 2. Create 3 sub-shares of the first share, with threshold 2, and give them to B, C and D. Give the other share directly to A, E and F.

For constructing the shares, you can use any conventional threshold secret sharing scheme, such as Shamir's. (For the 2-out-of-2 scheme in step 3, simple XOR secret sharing would also work.)

Yes, this is the boring solution, and I'm sure you could think of ways to try and optimize it. But it does have the advantage of being obviously correct, and of being easily generalizable.


In particular, your access structure can be represented hierarchically as:

1-out-of(
    3-out-of(A, B, C, D),
    2-out-of(A, E, F),
    2-out-of(
        2-out-of(B, C, D),
        1-out-of(A, E, F)
    )
)

where the notation k-out-of(recipients) indicates that the secret is to be split (using any threshold secret sharing scheme, e.g. Shamir's) into n equivalent shares (where n is the given number of recipients), of which any k are required to reconstruct it, and the resulting shares are to be either given directly to the indicated recipients or, if the "recipient" is itself an access structure, in turn shared according to that access structure.

Simply mechanically implementing this nested sharing scheme (and noting that 1-out-of(...) sharing is trivial, as the shares can simply be equal to the secret) then yields the solution I gave above.

$\endgroup$
  • $\begingroup$ Would this method give a linear scheme? $\endgroup$ – harry55 Apr 26 '17 at 19:59
  • $\begingroup$ @harry55: I was not previously familiar with the concept, but as far as I can tell based on a quick Google search, yes, this scheme would be a LSSS if the underlying $k$-out-of-$n$ threshold scheme is. $\endgroup$ – Ilmari Karonen Apr 26 '17 at 21:00
  • $\begingroup$ When you say 'Give the other share directly to A, E and F' what do you mean exactly? Do you not have to give it to one player in particular? $\endgroup$ – harry55 Apr 27 '17 at 10:05
  • $\begingroup$ @harry55: Yes, just give the same share to all three of them. If you like, you can call it a 1-out-of-3 threshold secret sharing scheme. ;) $\endgroup$ – Ilmari Karonen Apr 27 '17 at 13:15
  • $\begingroup$ @harry55: note that Ilmari's and my solutions are essentially the same, except that Ilmari did a direct mechanical translation of the requirements, while I optimized them somewhat. $\endgroup$ – poncho Apr 27 '17 at 14:12

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.