Join Log in
Score:0
Hunger Learn avatar Crypto

Is the Secret sharing scheme thresholds of variable of interest shared related with the entropy of the variable?

ua flag
Hunger Learn
  1. Is the $t$ out of $n$, namely $(t,n)$, threshold in the secret sharing scheme related to the entropy of the random variable that is shared according to the scheme?
  2. What changes in the secret sharing scheme if $t=n$?
40
0 + 0
Score:2
poncho avatar Crypto
my flag
poncho
  1. Is the $t$ out of $n$, namely $(t,n)$, threshold in the secret sharing scheme related to the entropy of the random variable that is shared according to the scheme?

No. You can use a $(t,n)$ sharing scheme (for any $t>0$) to share a value that has one bit of entropy - e.g. everyone knows that it is either a 0 or a 1. And, even in that case, with $t-1$ shares and that public information, you still don't have any information to determine which it is.

  1. What changes in the secret sharing scheme if $t=n$?

Nothing changes.

What does change is that you could use a simpler scheme; instead of using something like Shamir's (which involves complicated operations such as inversion or modular division), you can use a simple xor-based scheme; where the first $n-1$ shares are just random values, and the last share is the xor of all the other shares and the secret. However, that's just an implementation detail.

0 + 0
Hunger Learn avatar
ua flag
Hunger Learn
you say that "you can use a simple xor-based scheme; where the first n−1 shares are just random values, and the last share is the xor of all the other shares and the secret." Could you give an example of such a multiparty scheme or where to search for this? If there is already an example in the forum you could also mention it. Thank you in advance
0
Reply
Morrolan avatar
ng flag
Morrolan
Let $x \in X$ be the secret in some domain $X$, which we'll assume to be byte strings of equal length. Let $s_0, \ldots s_{n-1}$ be the shares. Define $s_i \leftarrow X, 0 \leq i \leq n - 2$ to be random elements of the domain for the first $n - 1$ shares. Define $s_{n-1} = s_0 \oplus s_1 \ldots \oplus s_{n-2} \oplus x$ to be the last share. Reconstruction is then trivially the XOR of all shares $s_i$.
1
Reply
Hunger Learn avatar
ua flag
Hunger Learn
@Morrolan please check this $k$-out-of-$k$ secret-sharing: Select $k-1$ shares, say $s_1,s_2,\cdots,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.
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
$\textbf{Lemma:}$ The above scheme is a k-out-of-k secret-sharing scheme.
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
$\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.
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
@Morrolan so in other words does the above lemma means that if you miss one share from the $k$ parts of the shares that are distributed you can not elicit $s$?
0
Reply
Morrolan avatar
ng flag
Morrolan
@HungerLearn yes, this scheme looks as if it has information-theoretic security.
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
@morrolan i have made a new post where I ask some questions. If you want take a look. And thanks!
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
This is the link https://crypto.stackexchange.com/questions/98066/secure-multi-party-computation-made-simple-questions
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.