Score:0

Secure multi-party computation made simple - questions

ua flag

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:}$

  1. Share the secret $s$ using the scheme of $k$-out-of-$k$ secret-sharing as in the Lemma.
  2. 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.
  3. 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:}$

  1. All players send all their shares (bilaterally) to all other players. No broadcast is required.
  2. 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

  1. 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?
  2. 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?
  3. 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?
  4. Could this scheme be used in a $t$-out-of-$k$ secret sharing scheme?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.