Distributing shares in a particular monotone access structure

Question

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?

Answer 1

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.

Answer 2

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.