1
$\begingroup$

In Shamir secret sharing scheme, we have a secret and then the shares are generated based on the secret. The question is can we generate the shares before knowing the 'secret' (which is uniformly random). Specifically, suppose $n$ users choose random numbers $r_1,r_2,\dots, r_n$, can we reconstruct a secret (random number) using $t$ of them with Shamir's technique?

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of Can I pre-define the points in Shamir's Secret Sharing algorithm $\endgroup$ – Ilmari Karonen Mar 17 at 15:32
  • $\begingroup$ @IlmariKaronen The accepted answer seems to take things a bit in a different direction, proposing two types of schemes. Could we somehow integrate the two questions while respecting both your answer (in the other question) and the accepted answer here? $\endgroup$ – Maarten Bodewes Mar 18 at 11:44
  • $\begingroup$ @Maarten Bodewes♦ I agree. $\endgroup$ – Jiangtao LI Mar 20 at 1:47
1
$\begingroup$

I know of 2 types of threshold secret sharing. I believe you are looking for the Type II threshold secret sharing. These are the basics behind them:

  1. Type I threshold secret sharing

As proposed originally by Shamir in 1979, in this threshold secret sharing a single owner owns a secret which he splits up into shares and divides these among $n$ shareholders. To reconstruct the secret, $t$ shareholders (for threshold $t$) are required to work together to reconstruct the original secret.

  1. Type II threshold secret sharing

This secret sharing scheme was proposed by Wang et al in 2003. This secret sharing scheme does not have an owner of a secret. A set of $n$ users create a random secret and after all users sharing partial information with everyone else, a master secret is created of which only $t$ or more users are able to construct this secret.

The computational details of both these secret sharing schemes can be found in: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8076576

$\endgroup$
2
$\begingroup$

No, if $n$ users have independently chosen secret random numbers $r_i$, and for any given $t\in[1,n)$, we can't use Shamir secret sharing to construct a secret dependent on $t$ out of $n$ of the $r_i$, and independent of which $r_i$ are picked. The critical issue is that what Shamir secret sharing assigns to a user is dependent on what the others get.

More generally, I think there is no function taking $t\in[1,n)$ pairs $(i,r_i)$ with distinct $i$ and producing something independent of the picks but dependent on each $r_i$. I'm trying to think of a proof, but nothing has happened yet.

$\endgroup$
  • $\begingroup$ Yes, I agree with you. But, can we do this with any other method. It's like agreeing an (unknown) secret which will be recovered only if some of them cooperate with each other. $\endgroup$ – Jiangtao LI May 23 '18 at 8:52
  • $\begingroup$ @Jiangtao LI: are you willing to let the $n$ users communicate in order to choose their $r_i$? That opens up a lot of avenues. If not, as stated in the answer's second paragraph, I strongly doubt there is a way (though I currently lack a proof). $\endgroup$ – fgrieu May 23 '18 at 9:11
  • $\begingroup$ For $t = n-1$ it seems that any set $r_1,\ldots,r_n$ defines a secret. $\endgroup$ – Daniel Mar 18 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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