# Understanding a variant of Shamir's cryptosystem with authorization levels

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.

• Hint: the original scheme can be implemented by having a group A in 2-out-of-NA mode, comprising a pseudo-user A0 (in addition of the two stated users from A) which share is shared in 2-out-of-2 mode (implementable as XOR), with one of these two shares shared among group B in 3-out-of-NB mode, and the other shared among group C in 5-out-of-NC mode. If I get it correctly, the task is to guess how X is shared among the users of B and C.
– fgrieu
Feb 6 '20 at 14:15

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.

• what i tried to do using the constraints is trying to create a (t,n) secret sharing,$t \leq 2A$ or $t \leq A +4B + C$, so if A=6,B=1,C=2 i get that $t \leq 12$ or $t \leq 6+4+2=12$(the same), and $n=1+3+5=8$. i don't understand how to recover it using the way you wrote and it's very important to me and i really want to understand it. could you please show me how to recover the secret in the method you specified? i think it involves constructing a random binary vector and having $S\oplus X$ but i don't understand it, could you please show so i can learn and apply it to similar problems? Feb 7 '20 at 9:18
• @Crypto123: simple example on this sort of composite scheme: suppose you have requirements that 2 members of A and 2 members of B will be able to recover the secret X. You create a (2,2) scheme for X, coming up with the intermediate secrets $R$ and $R \oplus X$ (for some random R); then you secret share $R$ with the members of A, and secret share $R \oplus X$ with the members of B. 2 members of A can recover $R$, 2 members of B can recover $R \oplus X$, and with those two intermediate secrets, they can recover X. Feb 7 '20 at 15:33