Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Consider 4 people, $A$,$B$,$C$,$D$, & a secret $s\in\{0,1\}^k$. Construct a scheme which enables the following subsets of people to retrieve the secret $\{A,B\}$, $\{A,C\}$, $\{B,C,D\}$.

I know that we can use Shamir's secret sharing scheme to do so, and A should be allocated more shares than the others. But how do we do the allocation when given an arbitrary monotone access structure?

share|improve this question
    
With Shamir's secret sharing you cannot realize secret sharing for any (monotone) access structure. Do you mean given an access structure to decide how to distribute the shares? You may take a look here –  DrLecter Oct 31 '13 at 10:39
    
Yes, thanks! @DrLecter –  freak_warrior Oct 31 '13 at 11:01
    
@freak-warrior: I edited your question to the general case. Maybe someone has the time to write-up a nice answer to this more general question :) –  DrLecter Oct 31 '13 at 13:34
    
Can you explain how the Monotone Span Program works? @DrLecter –  freak_warrior Oct 31 '13 at 14:58
    
you may look here –  DrLecter Oct 31 '13 at 21:37

2 Answers 2

up vote 3 down vote accepted

I will make a start by observing that not every monotone access structure can be realized by means of $(t,n)$ threshold secret sharing (here we require $t$ out of the $n$ shares need to be available for reconstruction).

First let us define a monotone access structure. Let $P$ be a set of participants. An access structure $\Gamma$ is a collection of nonempty subsets of the power set $2^P$. This structure is called monotone, if $X\in \Gamma$ implies $Y\in \Gamma$ for all supersets $Y\supseteq X$.

Note that defining monotone access structures perfectly makes sense in context of secret sharing, since every set in the access structure can reconstruct the secret, so every superset containing this set can trivially do so.

Shamir does not provide a general solution

Let us construct a counterexample for threshold secret sharing:

Consider the set of participants $P=\{A,B,C,D\}$ and a monotone access structure $\Gamma=\{\{A,B\},\{C,D\}\}$. We assume we use a $(t,4)$ threshold scheme to share a secret $k$ among the participants $A,B,C,D$ and $k$ can only be reconstructed by subsets which are elements of $\Gamma$.

Now let $a,b,c$ and $d$ be the weights of the shares that are assigned to the users of $P$. Then it must hold that $a+b\geq t$ and $c+d \geq t$, where $t$ is the threshold.

WLOG let $a\geq b$ and $c \geq d$. Since

  • $a+b\geq t$ and $a\geq b$ we have $a+a\geq a+b \geq t$ which gives that $a\geq t/2$.
  • Furthermore, since $c+d\geq t$ and $c\geq d$ it follows that $c\geq t/2$.

This implies that $a+c \geq t$ and thus $A$ and $C$ are able to reconstruct $k$, but $\{A,C\}\notin \Gamma$.

Towards secret sharing for monotone access structures

Ok, now we go on to realize secret sharing for general monotone access structure. Let $P=\{P_1,\ldots,P_n\}$ be the set of participants. We need some definitions first:

Minimal authorized subset: Let $\Gamma$ be an access structure then ${\cal C}\in \Gamma$ is a minimal authorized subset if $H \notin \Gamma$ whenever $H\subset {\cal C}$ (i.e., whenever we remove a participant, then the set will no longer be authorized).

Now we call the set of minimal authorized subsets associated to $\Gamma$ a basis and denote it by $\Gamma_0$. And it is sufficient to work with the basis henceforth (as $\Gamma$ can be obtained by taking the closure, i.e., by monotonicity).

If we look at a $(t,n)$ threshold scheme, then we have $\Gamma = \{G \subseteq P : |G|\geq k\}$ and $\Gamma_0 = \{G \subseteq P : |G| = k\}$.

Maximal unauthorized subset: Let $\Gamma$ be an access structure and call $M=\{{\cal B}_1,\ldots,{\cal B}_m\}$ the set of maximal unauthorized subsets if for every ${\cal B}_i$ holds: ${\cal B}_i\notin \Gamma$ and ${\cal B}_i\cup P_j\in \Gamma$ for each $P_j\notin {\cal B}_i$ (i.e., whenever we take a participant that is not yet included we will obtain an authorized set)

Now we can define a dual representation of an access structure $\Gamma$ denoted as $\Gamma^*$.

We can write an access structure $\Gamma = \bigvee_{{\cal B}\in \Gamma} \bigwedge_{P_i\in B} P_i$ or as a sum or products (replacing conjunctions by $\cdot$ and disjunction by $+$).

Then the dual access structure is obtained by exchanging the operators, i.e., $\Gamma^* = \bigwedge_{{\cal B}\in \Gamma} \bigvee_{P_i\in B} P_i$ (or again as a sum of products).

We have the following: Let $\Gamma$ be an access structure on $P$ and $M=\{{\cal B}_1,\ldots,{\cal B}_m\}$ the set of maximal unauthorized subsets, then $\Gamma_0^*=\{{\cal A}_1,\ldots,{\cal A}_m\}$ such that ${\cal B}_i=P\setminus {\cal A}_i$ is the set of minimal authorized subsets in the dual form.

Ok, let us take additive perfect secret sharing over a prime field $Z_p$, i.e., the secret $k$ is represented $k=\sum_{i=1}^m s_i \pmod p$ for random $s_i$.

Then we can come up with the following matrix, where we have $b_{i,j}=1$ if $P_i\in {\cal A_j}$ and $b_{i,j}=0$ otherwise. enter image description here

Now, we can distribute the shares $s_1,\ldots,s_m$ in the following way. Every user $P_i$ obtains the set of shares $S_i=\{s_j: b_{i,j}=1\}$ (i.e., a participant obtains a share if he shows up in the respective set of the dual basis or equivalently, obtains no share if he shows up in the respective set of the maximal unauthorized subsets).

I will not come up with an explicit example anymore today. But this secret sharing enables every authorized subset in $\Gamma$ to reconstruct the secret $k$ and any non-authorized set will not be able to do so.

share|improve this answer

This answer attempts to solve the original question, which gave a specific example - it certainly won't solve the generalised case now given!


Create a threshold sharing scheme with $4$ shares (call them $1,2,3,4$) and a threshold of $3$ required for secret retrieval. Then, issue shares such that: $$\begin{array}{cl} A & 1,4 \\ B & 2 \\ C & 3 \\ D & 4 \end{array}$$

share|improve this answer
    
Thats correct, but I guess that @freak_warrior has figured out how it works in this example. I think his question is how you make the allocation given any monotone access structure. –  DrLecter Oct 31 '13 at 13:30
    
@DrLecter: I assumed so as well, but thought I should answer the direct question just in case. I see you've put a comment on the original question saying you've submitted a generalizing edit (to a much more sensible question). Assuming that gets accepted will deal with this answer. –  figlesquidge Oct 31 '13 at 15:17
2  
I assumed that as well. Yes, I think secret sharing for general access structures is a nice topic and could receive nice answers ;) –  DrLecter Oct 31 '13 at 15:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.