0
$\begingroup$

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.

$\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$
    – Morrolan
    Jan 16, 2022 at 16:14
  • $\begingroup$ $C(n,t-1) = \frac{n!}{(t-1)!(n-(t-1))!}$ $\endgroup$
    – kelalaka
    Jan 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$ Jan 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$
    – Morrolan
    Jan 16, 2022 at 18:58
  • $\begingroup$ @Morrolan I don't get your question either. Would you mind re-state it again? $\endgroup$ Jan 16, 2022 at 22:11

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.