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