The scheme that I refer to is from this paper.
A secret $s\in D$ is obtained by splitting s into a random sum. We have (actually linear) for any $k$ this $k$-out-of-$k$ secret-sharing scheme: Select $k−1$ shares, say $s_1,s_2,⋯,s_{K−1}$ from $D$ and let $s_k=s−\sum_{i=1}^{k−1}s_i$ where $s_i$ denotes the $i$-th share.
$\textbf{Lemma:}$ The above scheme is a $k$-out-of-$k$ secret-sharing scheme.
$\textbf{Proof:}$ All shares together obviously determine the secret, hence the set of all $k$ players is qualified. Any set of $k-1$ players, with say $p_i$ missing is ignorant because these $k-1$ shares $(s_1,s_2,\cdots,s_{i-1},s_{i+1},\cdots,s_{k})$ are independent and uniformly random, independent of $s$. This follows from the fact that for any fixed $s$ and any fixed missing share $s_i$, the mapping from $(s_1,s_2,\cdots,s_{k-1})$ to $(s_1,s_2,\cdots,s_{i-1},s_{i+1},\cdots,s_{k})$ is one-to-one. The shares can be simulated by generating a set of uniform and independent shares.
Let $k$ be the number of maximal sets in the secrecy structure $\Sigma$, namely $\Sigma=\{T_1,T_2,\cdots,T_k\}$ and let $T_i^c=P-\{T_i\}$, is the complement of $T_i$ and $P$ the whole set of agents. So we can achieve the simple following verifiable secret sharing scheme that has two dimension, the share dimension and the reconstruction.
$\textbf{Share dimension:}$
- Share the secret $s$ using the scheme of $k$-out-of-$k$ secret-sharing as in the Lemma.
- For each share $s_i$: Each pair of players in $P-\{T_i^c\}$ check (over a secure channel) whether their received values for $s_i$ agree. If any inconsistency is detected, the players complain, using (possibly simulated) broadcast.
- The dealer broadcasts all shares for which complaints were raised, and the players accept these shares. If the dealer refuses any of these broadcasts, the protocol is aborted.
$\textbf{Reconstruct dimension:}$
- All players send all their shares (bilaterally) to all other players. No broadcast is required.
- Each player reconstructs (locally) each of the k shares $s_1,...,s_k$ and adds them up to obtain the secret $s = s_1 \oplus s_2\oplus\cdots\oplus s_k$.
Reconstruction of share $s_i$ (same for each player): Let $v_j$ for $j \in T_i^c$ be the value (for $s_i$ ) sent by player $p_j$ . Take the unique value $v$ such that there exists $A\in\Delta$ with $v_j=v$ for all $j\in T_i^c - A$.
I have the following questions
- The above lemma means that if you miss one share from the $k$ parts of the shares that are distributed you can not learn s?
- The Lemma says that: "The shares can be simulated by generating a set of uniform and independent shares." Is this proposition based to some know result from linear algebra?
- Could anyone explain a little more the bullet $2$ form the share dimension of the protocol and the reconstruction of share $s_i$ from the reconstruction dimension of the protocol?
- Could this scheme be used in a $t$-out-of-$k$ secret sharing scheme?