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

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

• 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. Jan 16, 2022 at 16:14
• $C(n,t-1) = \frac{n!}{(t-1)!(n-(t-1))!}$ Jan 16, 2022 at 17:53
• @kelalaka yes you are right... take the $C(n,k)=\frac{n!}{k!(n-k)!}$, where $k=t-1$...so simple Jan 16, 2022 at 17:54
• 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? Jan 16, 2022 at 18:58
• @Morrolan I don't get your question either. Would you mind re-state it again? Jan 16, 2022 at 22:11

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

• 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! Jan 17, 2022 at 8:54