4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ The last question is trivial if you are to assume that the previous is true. $\endgroup$ – SEJPM May 7 '17 at 19:37
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.