5
$\begingroup$

In Shamir's secret sharing scheme, any combination of shares (that pass the threshold) will result in the secret being revealed. Is it possible to have a system where some combinations are invalid?

For example, imagine a company's trade secret is split into 10 shares with a threshold of 3. You give 3 to the CEO, 2 to each executive (of which there are 2), and the remaining 3 shares go out to 3 secretaries. This has this effect.

CEO(3)                      = 3 -> Secret recovered
Exec(2) + Exec(2)           = 4 -> Secret recovered
Exec(2)                     = 2 -> Secret NOT recovered
Secr(1) + Secr(1)           = 2 -> Secret NOT recovered
Secr(1) + Secr(1) + Secr(1) = 3 -> Secret recovered

It also allows for this case.

Exec(2) + Secr(1) = 3 -> Secret recovered

In this case, an executive needs only to consult a secretary before unlocking the trade secret.

Is it possible to have a scheme where an executive's shares and a secretary's share cannot be combined?

I can think of ways to extend Shamir's scheme to have this behavior in this example. For instance, using two instances of the Shamir scheme to make the executives' shares and the secretarys' shares be incompatible. This has the problem that you need to maintain two copies of the same secret. I'm looking for a better solution.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Secret sharing with more complex access structures is an active area of research (whose results I do not feel confident to summarise, see for example the book of Cramer, Damgård, and Nielsen). $\endgroup$
    – fkraiem
    Jun 30 '17 at 5:13
  • 1
    $\begingroup$ crypto.stackexchange.com/questions/48700/… seems related, I liked that answer. For much more complicated scenarios you can just have a second copy of the secret, then you can also watermark the data or hide fake data to clamp down on any turncoats. $\endgroup$
    – daniel
    Jun 30 '17 at 8:25
8
$\begingroup$

Yes. It is possible to construct secret sharing schemes for general (monotone) access structures. You can read about the first construction in the paper called Secret Sharing Scheme Realizing General Access Structure. I also suggest reading this survey by Amos Beimel.

Improve this answer
$\endgroup$

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.