# Reconstruction vector in Linear secret sharing schemes

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

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

• We have $\textbf{supp(g)} \subseteq \textbf{supp(V)}$. If we consider $\textbf{g}$ only for the minimally authorised sets , is it always the case that it turns out to be equal to $\textbf{V}$ ? Is there a counter example ? Consider working in $\mathbb{F_2}$ – chelsea Sep 29 '18 at 7:45
• In $\mathbb{F}_2$, $V$ should always be equal to $\mathbf{g}$ for minimally authorised sets since the only option is to add a vector (so the corresponding component of the recombination vector $\mathbf{g}$ is 1) or not (so it's 0). For this specific LSSS, you should always have $\mathbf{g} = V$ for minimally authorised sets because the construction essentially enforces this. In general, consider that the recombination vector in Shamir sharing is a vector encoding the Lagrange interpolation required, but the vector $V$ is merely an indicator vector encoding which parties are reconstructing. – TWood Sep 29 '18 at 9:10
• This will be true in any LSSS in $\mathbb{F_2}$ , if we consider only minimally authorised sets. – chelsea Sep 29 '18 at 9:23
• Yes, but for more complicated access structures this LSSS construction is less efficient than others since then some attributes must be assigned multiple rows (and hence shares), compared to LSSSs over larger fields where the total number of shares may be smaller. – TWood Sep 29 '18 at 9:38