Linear secret-sharing scheme for four players

Question

I got stuck on this question during my exam revision.

Consider the linear secret-sharing scheme for four players $P_1, P_2, P_3$ and $P_4$ based on the matrix $$ M= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 2 & 3 & 3 \\ 0 & 1 & 5 & 5 \\ 1 & 4 & 3 & 6 \\ 0 & 5 & 2 & 4 \\ \end{bmatrix}$$ whose entries are elements of $GF(7)$. The dealer shares a secret $s \in GF(7)$ using random elements $r_1, r_2, r_3 \in GF(7)$ by computing $M(s,r_1,r_2,r_3)^T$ and letting the share of player $P_i$ be the $(i+1)^{th}$ coordinate of the resulting 5-tuple.

How do I show that $\{P_1,P_2\}$ and $\{P_3,P_4\}$ are the only pairs of players who can recover the secret?

How do I show that any set of three players can recover the secret?

Answer 1

First, calculate the parity-check matrix $H$, whose rows generate the null space of $M^T$. $H$ is a generator matrix for the dual code $C^\bot$ of the linear code $C := \{ x \, M^T \}$ associated to your secret-sharing scheme. The access structure of your scheme is given by the minimal codewords $\mathbf x = (x_0, x_1, x_2, x_3, x_4)$ of $C^\bot$ that have $x_0 = 1$; specifically, $\{P_i : x_i \neq 0\}$ is a minimal reconstructing set if and only if there is a minimal codeword $\mathbf x$ in $C^\bot$ with $x_0 = 1$ (Massey, 1993).