Reconstruction vector in Linear secret sharing schemes

Question

Suppose we have a policy $A \wedge ( D \vee (B \wedge C))$ with attributes ${\{A,B,C,D}\}$. The set of subsets of attributes which satisfy this policy is ${\{{\{A,D}\},{\{A,B,C}\},{\{A,B,D}\},{\{A,C,D}\}}\}$ of which ${\{{\{A,D}\},{\{A,B,C}\}}\}$ is the set of minimal subsets.

We convert the above boolean formula into a LSSS matrix $L = {\{{\{1,1,0}\},{\{0,-1,1}\},{\{0,0,-1}\},{\{0,-1,0}\}}\}$ according to this(Pg. No 30).

We usually find a vector $g$ such that $g^T \cdot L = (1,0,0)$ for all such authorized subsets such that $\forall i \in [4], (g_i = 0) \vee (g \in Attr)$.

If I understand it correctly, suppose a user has attributes $Attr ={\{A,D}\}$. That means his input vector in this case will be $V = (1,0,0,1)$. Since he does not have $B,C$ those $g_i$s (false attributes) will be assigned $0$ and then we solve the equation of unknowns $g = (x_1,0,0,x_2)$ to get $x_1 = 1$ and $x_2 = 1$. So in this case, it turns out that $g = V$. Is this the right way to calculate $g$?

Assuming above way of calculating $g$ is correct, if he has $Attr ={\{A,B,D}\}$, then if we proceed with the same procedure as above ( the equation of unknowns will be $(x_1,x_2,0,x_3)$), how do we proceed to calculate $g$ as we then have two cases?. I know that ${\{A,B,D}\} \supset {\{A,D}\}$ as is the case for monotone policies.

Another way is that each subset of the rows of this matrix includes $\mathcal{e} = (1,0,0)$ in its span if and only if the corresponding attributes satisfy the formula. We take the rows corresponding to ${\{A,D}\}$ and find the coefficients $(1,1)$ so that $e$ is in the span. Then why do $\{A,B,D\}$ and $\{A,C,D\}$ have the same coefficients i.e (1,0,1)? I have a vague intuition but not sure.

What is the correct way to calculate $g$?

Answer 1

Notation in this answer is as in the answer to a question on the same LSSS construction.

Is this the right way to calculate g?

You are correct that you solve for $g$ by setting attributes $B$ and $C$ to zero. What you are actually doing is computing a solution vector, which I will denote by $\mathbf{g}_{\{A,D\}} \in \mathbb{F}^2$, to $\mathbf{g}_{\{A,D\}} \cdot M_{\{A,D\}} = (1,0,0)$ where

$M_{\{A,D\}} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & -1 & 0 \end{pmatrix}, $

and then lifting to a solution by padding with $0$s to get a full vector $\mathbf{g}$. So here you find that $\mathbf{g}_{\{A,D\}}=(1,1)$ (and happens to be unique in this case), and then we pad with $0$s in the corresponding components of the vector $V$ to get $(1,0,0,1)$. This final solution (after padding) is called a recombination vector for this set.

The vector $V$ is just a way of saying which rows it is permissible to combine in order to try to obtain the target vector $(1,0,0)$. If you like you can think of finding $\mathbf{g}$ as finding a solution to the equation

$ \mathbf{g} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot M = (1,0,0) $

where the middle matrix is a square zero-matrix replacing the leading diagonal with the entries of $V$. It is essentially irrelevant that $V=\mathbf{g}$ in this case: the point is that the support (here meaning the indexing set of non-zero components) of the vector $\mathbf{g}$, denoted by $supp(\mathbf{g})=\{1,4\}$, is contained in $supp(V)=\{1,4\}$.

How do we proceed to calculate g as we then have two cases?

If a vector $\mathbf{g}$ works for the smaller set $\{A,D\}$, then it will also work for the larger set $\{A,B,D\}$, since the target vector already lies in the linear span of rows indexed by attributes $\{A,D\}$. In other words, the same solution works because $supp(\mathbf{g}) = \{1,4\} \subseteq supp((1,0,0,1)) = \{1,4\} \subseteq supp((1,1,0,1)) = \{1,2,4\}$.

Indeed, it is easy to check that your solution $\mathbf{g}=(1,0,0,1)$ also solves

$\mathbf{g} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} \cdot M = (1,0,0).$

Thus in general it suffices to compute recombination vectors $\mathbf{g}$ for only the minimally authorised sets: then for any authorised set $A$ we can take any $\mathbf{g}$ for any minimally authorised set which contains the set $A$ and it will also work for $A$.

Then why do {A,B,D} and {A,C,D} have the same coefficients i.e (1,0,1)?

In this example there is only one vector, namely $\mathbf{g}=(1,0,0,1)$ for all three sets $\{A,D\}$ $\{A,B,D\}$ and $\{A,C,D\}$, which means you get $\mathbf{g}_{\{A,B,D\}} = \mathbf{g}_{\{A,C,D\}} = (1,0,1)$. This is because to combine the vectors $\{ (1,1,0), (0,-1,1), (0,-1,0)\}$ owned by $\{A,B,D\}$, we must have zero contribution from $(0,-1,1)$; similarly, to combine the vectors $\{ (1,1,0), (0,0,-1), (0,-1,0)\}$ owned by $\{A,B,D\}$, we must have zero contribution from $(0,0,-1)$, otherwise the third component will not be $0$ as it must be for constructing the target vector $(1,0,0)$.