How to Distribute the Shares using Secret Sharing for arbitrary Monotone Access Structures

Question

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?

Answer 1

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 \cal B} P_i$ or as a sum of 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 \cal B} P_i$ (or as a product of sums).

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.

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.

Answer 2

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}$$