8
$\begingroup$

I need to find a secret sharing scheme with these properties:

  • The scheme is set up by all participants, ie no single entity called the dealer

  • The parameters of secret sharing need to be modifiable, eg enrollment, disenrollment, change of access structure, ...

  • Need to be verifiable, ie participants could check whether their shares are consistent with others.

Is this scheme could be available at all !?

A brief description is helpful.

$\endgroup$
5
  • $\begingroup$ Hello and welcome to Crypto.SE. The Dining Cryptographers problem doesn't exactly fit your needs but comes close. Apart from that, what have you tried? (the question as it stands shows lack of research so that last bit is important). $\endgroup$
    – rath
    Jan 28 '14 at 13:34
  • $\begingroup$ This sounds a lot like the Joint-Uncond-Secure-RSS scheme of link.springer.com/chapter/10.1007%2F3-540-68339-9_31. The trick is to let each participant be a dealer, or, put differently, build the scheme around participants who generate their shares randomly. $\endgroup$ Jan 28 '14 at 16:43
  • $\begingroup$ If robustness isn't a requirement, also look at Pedersen's original scheme link.springer.com/chapter/10.1007%2F3-540-46416-6_47 $\endgroup$ Jan 28 '14 at 17:04
  • $\begingroup$ Thanks all friends :) I'm going to check and use these articles specially the last one ;) $\endgroup$ Jan 28 '14 at 21:26
  • $\begingroup$ How is the secret to be determined in the first place? $\;$ $\endgroup$
    – user991
    Jan 29 '14 at 23:14
1
+50
$\begingroup$

The "simple" answer to your question is that all of the above can be achieved using secure multiparty computation (see this review article on Secure Multiparty Computation for a more detailed overview). The best way to abstract this is to define an "ideal functionality" $F$ which is run by a trusted third party, receiving inputs from the parties and providing outputs. The theory of MPC then tells us that any such functionality can be securely computed by the parties interacting. (There are details of early abort, fairness, etc. However, I believe that this is orthogonal to what is in the question.)

According to the above, we can define each of the required features as an ideal functionality:

  • For setting up the sharing without a dealer, one has to assume that they are generating a sharing of some random value (otherwise what are they sharing). Assuming that they wish to share a random $s\in\mathbb{F}$ according to some access structure $\cal Q$, the ideal functionality can be defined to receive the description of the field and the access structure from all parties. Then, assuming they are all the same, it samples a random $s\leftarrow\mathbb{F}$, locally computes the secret sharing according to $\cal Q$, and sends each party its share.
  • The parameters can all be changed by defining an ideal functionality that receives the shares from all parties (or at least a quorum) and the new parameters. The trusted party then reconstructs the secret $s$, generates a new secret sharing according to the new parameters, and sends each party its new share.
  • Verifiability follows automatically from the fact that if the MPC protocol is secure against malicious adversaries, then it is guaranteed that all outputs are correct.

Having said this, one issue that may arise is that parties may send incorrect shares to the trusted party for the second item. This can be solved by either assuming that the threshold is strictly less than the number of parties participating. This suffices since if the secret sharing is Shamir, for example, then all shares must lie on the same polynomial, and any incorrect value is detected. However, if you wish to prevent an abort, then you need enough redundancy (e.g., if $t<n/3$ then you will always have enough honest shares to "correct" any corrupt ones). Another, more general, way of ensuring that nothing is changed is to have all parties hold commitments of all shares, or the like, and the trusted party verifies that all inputs used are unchanged.

Having said all of the above, what one often wants is something more complex. First, not all parties may participate in all phases. Second, you want to find an efficient MPC protocol that deals with the above. In general, this is all possible. However, exactly specifying how to do it is beyond the scope of this answer, and depends very much on exactly what setting you are in. The best source to understand more specifically about this would be the book Secure Multiparty Computation and Secret Sharing. However, there are many techniques that are relevant that can be found in the MPC literature.

$\endgroup$
0

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.