Shamir's secret sharing after a change

Question

I cannot understand what and why would happen after a change occurs in Shamir's secret sharing. I will try to explain my problem with an example and would appreciate if you could explain and demonstrate mathematically so I can learn and understand better.

Assume, for simplicity sake, we have three leveling groups: A,B,C, and that in order to recover a secret S there's a need of:

• 2 users from A

OR

• 1 user from A and 3 from B and 5 from C

Now, assume that A consists of just 2 participants, and one of them left. his part of the secret, name it X, he shares with the rest of the participants EXCEPT for the other user in A, so that in order to recover X we need 4 participants from B and one participant from C.

Is it even possible to know what each participant hold and how to recover S?

I would really appreciate a mathematical explanation so I can better understand this complicated change, what happens afterwards, what each participant hold and if it is possible to recover S, how to do so?

Thank you very much for helping me and guiding me in my first steps in learning cryptography. It can be really complicated for beginners.

Answer 1

I think that you are mistaken about Shamir's secret sharing. It splits a secret into an arbitrary number of shares such that a required amount of shares are needed to recover it. But it does not allow, "as is", several leveling groups with distinct thresholds.

In your case, what you need is to:

1. Use a Shamir secret sharing to generate shares $s_1, s_2, \dots$ such that any two yield the secret.

2. give one share to each member of $A$. This allows two arbitrary members of $A$ to recover the secret.

3. Now, generate one more share $s$, and use again a Shamir Secret sharing to split it in two shares $s_B, s_C$ such that both $s_B$ and $s_C$ are required to rebuild $s$.

4. Use again a Shamir secret sharing to split $s_B$ amongst the members of $B$ (such that any 3 of them can rebuild $s_B$)

5. Use again a Shamir secret sharing to split $s_C$ amongst the members of $C$ (such that any 5 of them can rebuild $S_C$).

Now, 5 members of C can rebuild $S_C$ ; 3 members of $B$ can rebuild $s_B$ ; together they can rebuild $s$; with any member of $A$ they can rebuild the original secret.