# Question regarding reconstruction vector in LSSS

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).

I have a question regarding the yellow marked line taken from this(Page No. 7).

$\textbf{Is the resulting 0 a vector in$w \cdot M_i$? Is the first entry of the vector$w$-1? }$ $\textbf{How do one go on to calculate this$w$?}$. It will be helpful if anyone can explain using the above LSSS matrix above and the unauthorized subset ${\{A,B}\}$.

For the tl;dr see the last few paragraphs.

LSSS Background

The construction of linear secret sharing you are referring to is based on the model of computation known as Monotone Span Programs. Other papers go into more detail and should help with further questions.

The paper that has given rise to your question is a proposed method to construct an LSSS from a given Boolean formula (equivalently, from an access structure). For now, we will assume their method is correct and the derivation of the LSSS matrix is as they describe:

$$\begin{array}{c} A \\ B \\ C \\ D \end{array} \begin{pmatrix} 1 & 1 & 0 \\ 0 & -1 & 1 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix}$$

We will denote this matrix by $$M$$ and assume we are working in a field $$\mathbb{F}$$. For a dealer to share a secret $$s \in \mathbb{F}$$ in this scheme, he does the following:

1. Select any vector $$\mathbf{x}\in \mathbb{F}^3$$ such that $$\langle \mathbf{x}, (1,0,0) \rangle = s$$ (i.e. the inner product with the target vector is the secret);
2. Compute $$\mathbf{y} := M\cdot \mathbf{x}$$;
3. Give $$\mathbf{y}[i]$$ (the $$i^{\text{th}}$$ component of $$\mathbf{y}$$) to the party assigned the corresponding row of the matrix $$M$$. So in this case, e.g. party $$C$$ will receive the third component of $$\mathbf{y}$$.

Now assuming the construction of the LSSS matrix is correct, then any set of qualified parties should be able to combine their shares to obtain the secret. This is because the construction of the LSSS requires that the span of all of the rows held by any set of qualified parties must contain the target vector in their linear span.

In this example, $$\{A,D\}$$ is supposed to be qualified, and indeed adding one times the first row to one times the fourth row, i.e. computing $$1 \cdot (1, 1, 0) + 1 \cdot (0, -1, 0) = (1, 0, 0)$$, gives them the target vector.

This is useful because by linearity, parties $$A$$ and $$D$$ can use their shares to compute the secret using the same linear combination: i.e. $$1 \cdot \mathbf{y}[1] + 1 \cdot \mathbf{y}[4] = s$$.

The required linear combination is encoded in a vector: in the running example $$\{A,D\}$$, the recombination vector is $$\mathbf{r}=(1,0,0,1)$$, since we were required to add the first row to the fourth row.

Again assuming the construction of the LSSS is correct, we will also require that unauthorised sets of parties have no information on the secret. This is true if and only if the target vector does not lie in the linear span of the rows held by those parties.

Let us denote by $$M_U$$ the submatrix of $$M$$ where we have selected only those rows owned by some unauthorised set of parties $$U$$. So we have, e.g.

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

To see that the colluding parties $$\{A,B\}$$ learn no information, observe that if $$(1,0,0)^\top \not \in \text{im}(M_{\{A,B\}}^\top)$$ then by the fundamental theorem of linear algebra, $$(1,0,0)^\top \not \in \text{ker}(M_{\{A,B\}})^\perp$$ and so there must exist some vector $$\mathbf{w} \in \mathbb{F}^3$$ such that $$M_{\{A,B\}} \cdot \mathbf{w} = 0$$ and $$\langle \mathbf{w} ,(1,0,0)^\top\rangle \ne 0$$. (In other words, $$\mathbf{w}$$ must exist because otherwise every vector in $$\text{ker}(M_{\{A,B\}})$$ is perpendicular to $$(1,0,0)^\top$$, contradicting $$(1,0,0)^\top \not \in \text{im}(M_{\{A,B\}}^\top)=\text{ker}(M_{\{A,B\}})^\perp$$.)

In particular, we can find any $$\mathbf{v}$$ such that $$\langle \mathbf{v} ,(1,0,0)\rangle \ne 0$$ and $$M_{\{A,B\}}^\top \cdot \mathbf{v} = 0$$ and then set $$\mathbf{w} = \frac{\mathbf{v}}{-\|\mathbf{v}\|_2}$$ so that $$\langle \mathbf{w} ,(1,0,0)\rangle = -1$$ and $$M_{\{A,B\}} \cdot \mathbf{w} = M_{\{A,B\}} \cdot \frac{\mathbf{v}}{-\|\mathbf{v}\|_2} = \mathbf{0}$$. This is the claim you highlighted.

The fact that we have found $$\mathbf{w}$$ already shows that union of the shares held by the unauthorised parties provides no information on the secret, since adding the vector $$k \cdot \mathbf{w}$$ to the vector $$\mathbf{x}$$ that was used above to generate the shares encoded in the vector $$\mathbf{y}$$, where $$k\in \mathbb{F}$$ is any field element, provides the same set of shares for the unauthorised parties in question, since we have shares $$M \cdot (\mathbf{x} + k\mathbf{w}) = M \cdot \mathbf{x} + M \cdot k\mathbf{w} = \mathbf{y} + k M \cdot \mathbf{w}$$ corresponding to secret $$\langle \mathbf{x} + k \mathbf{w} , (1,0,0) \rangle = s + k \cdot -1$$ and since $$M_U \mathbf{w} = \mathbf{0}$$, the shares held by $$U$$ can equally be shares for any secret, which we obtain by changing $$k$$ arbitrarily. Consequently, the shares held by these parties cannot provide them with any information about what the secret is.

Computing $$\mathbf{w}$$

There is at least one $$\mathbf{w}$$ for each unauthorised set (assuming the LSSS has been constructed correctly). Note that you only need to find one $$\mathbf{w}$$ for each maximally unauthorised set (since this $$\mathbf{w}$$ will work for any subset too).

Computing the actual $$\mathbf{w}$$ as descibed in your reference involves finding any vector in $$(M_{\{A,B\}})^\perp$$ (which is called the cokernel or left kernel of $$M_{\{A,B\}}$$) which is non-zero in the first component, and scaling. In the case of $$\{A,B\}$$, it is easy to find a $$\mathbf{w}$$ with the required properties by inspection: we can see that the vector $$\mathbf{w} = (-1, 1, 1)^\top$$ satisfies $$M_{\{A,B\}}^\top \cdot \mathbf{w} = \mathbf{0}$$, and it holds that $$\langle (-1,1,1),(1,0,0)\rangle = -1$$, which was what we needed (after transposing).

For larger matrices in this scheme, you just need a method for computing the cokernel of a given submatrix, and from there you take any vector $$\mathbf{w}$$ in that space satisfying $$\langle \mathbf{w},(1,0,\ldots,0)\rangle = -1$$, i.e. where the first component is $$-1$$.