Join Log in
Score:0
Hunger Learn avatar Crypto

How many combinotaion of all $n$ players are needed to reconstruct the secret in a $(k,n)$-treshold secret sharing scheme?

ua flag
Hunger Learn

In a $t+1$ out of $n$ secret sharing scheme where there is a network of $n$ players, in order to reconstruct the secret $t+1<n$ players are needed to share their parts $(x_i,f(x_i))$ so as the polynomial function of degree $t$ can be computed. However, all the $n$ want to have acces to this secret, but at least $t+1$ out of $n$ are needed for the computation. How many combinations are needed amond the $n$ players so as all of them can reconstruct the esecret. Of course some of them will become part of a $t+1$ group who reconstract the polynomial function more that once.

72
0 + 0
Morrolan avatar
ng flag
Morrolan
NB your title talks about a $(k, n)$ scheme, while your body works with a $(t+1, n)$ one. Might want to fix one or the other.
1
Reply
kelalaka avatar
in flag
kelalaka
$C(n,t-1) = \frac{n!}{(t-1)!(n-(t-1))!}$
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
@kelalaka yes you are right... take the $C(n,k)=\frac{n!}{k!(n-k)!}$, where $k=t-1$...so simple
0
Reply
Morrolan avatar
ng flag
Morrolan
That will give you the count of all possible subsets with $t-1$ elements, taken from a set with $n$ elements. I'm afraid you've lost me here. :D How is this either a lower or upper bound for the number of (distinct) sets of participants required to collaborate, such that every one of them will learn the secret? Or did I misunderstand your question?
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
@Morrolan I don't get your question either. Would you mind re-state it again?
0
Reply
Morrolan avatar
ng flag
Morrolan
@HungerLearn I do not understand the connection between the $C(n, t-1)$ comment and the way I understood your question. I have edited my answer below with how I understood your question - is that understanding correct?
0
Reply
Score:1
Morrolan avatar Crypto
ng flag
Morrolan

Clarification

The way I understood your question was:

  • Participants will collaborate in sets $(P_1, P_2, \ldots)$ of $t+1$ participants each, and reconstruct the secret.
  • They will keep doing this, until every participant has learned the secret (at least once)
  • The question then is to find bounds for the number of required distinct sets $P_i$. In words: "How many different groups of participants are required (at most/at least) such that every participant learns the secret"

Lower bound

There will be a total of at least $\lceil\frac{n}{t+1}\rceil$ sets of $t+1$ participants each, reconstructing the secret. At least two of these sets will have a non-empty intersection, unless $t+1$ divides $n$, in which case a pairwise disjoint split would be possible.

Upper bound

On the other hand, an upper bound for the number of distinct sets of $t+1$ participants each, such that every participant would learn the secret at least once, would be given by $n - (t + 1) + 1$.

Aside

Of course the premise is of questionable use. Naive reconstruction only works in a setting with no active adversaries, in which case you might just as well have the first group which reconstructed it broadcast the secret.

0 + 0
Hunger Learn avatar
ua flag
Hunger Learn
No your answer is right. This is what I wanted to know. "They will keep doing this, until every participant has learned the secret (at least once"...and yes you had the right understanding but I was confused when I saw your question....Everything is fine! DO not change your answer again! Thank you very much!
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.