Understanding a variant of Shamir's cryptosystem with authorization levels

Question

I am having problems understanding this implementation of Shamir's secret sharing with confidentially levels (in this case 3).

I will give the context and then my problem to make it more clear.

Context:

in some security system, to share a secret S, they use Shamir's secret sharing. the users in the system are divided to 3 levels of authorization: A, B, and C. To recover S, we need:

A) two users from A

OR

B) one user from A in addition to three users from B and 5 users from C

Problem:

Assuming that in level A there are only 2 users, and one of them decided to resign. His part of the secret, X, he shares with all of the participants, except the other user from level A, so to recover X we need 4 participants from B and one participant from C. Describe the new secret sharing cryptosystem. What does each participants hold and how to recover S?

Questions:

I am having a real hard time understanding this cryptosystem variant of Shamir's secret sharing. There are a lot of variants here.

I really don't understand what each participant hold and how to recover the secret S in this complicated scenario.

Could you please elaborate on it to help me understand it better? I feel totally lost.

Answer 1

I really don't understand what each participant hold and how to recover the secret s in this complicated scenario.

Part of the issue you're running into is that the method to implement the original scheme is not uniquely defined, and so what the various parties hold (and how they would recover the secret) would vary based on things not specified in the question.

The most straight-forward way you would do this is to share the secret two ways:

• Once with a $(2,2)$ scheme (and which you would give a share to each of the A parties)
• Once with a $(3, 3)$ scheme

For the three shares generated by the latter scheme, you would give them out as:

• One would go to each of the A parties (and so both parties would get the exact same share).
• One you would secret share with a $(3, n)$ scheme (and each of the B parties would get a share)
• One you would secret share with a $(5, n)$ scheme (and each of the C parties would get a share).

In this method, each of the A parties get a "share" which consists of two separate lower level Shamir shares, while each of the B, C parties get a single Shamir share.

If we assume that this is the method used, then it should be straightforward to write out what everyone would hold if the A party leaving were to reveal his share, and how that would allow 3 B parties and 5 C parties to recover the secret.

Note: with these requirements, it is possible to design an alternate scheme where every party holds a single Shamir share; you might find it educational if you were to find that yourself.