12
$\begingroup$

Let's say $k$ users have shares to a $(k,n)$ secret sharing scheme, and they want to issue new shares. How can they do this without collecting the shares together?

In particular, no set of $k-1$ users (including the new users) should be able to learn the shared secret during or after the share generating process. There is also no trusted third party.

One way to do this is by doing a secure multiparty computation. Is there a way to accomplish the task without a general multiparty computation scheme?

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ What adversary model (semi-honest or malicious)? Can up to k-1 parties be corrupt? Can you bound k as a fraction of n? $\endgroup$
    – mikeazo
    Sep 4, 2016 at 23:39
  • 1
    $\begingroup$ When you say "issue new shares" do you mean new shares for everyone involved (which may include additional users), or do you mean the existing users keep the same shares they currently have and new users get fresh shares that could work with existing shares to reconstruct the original secret? $\endgroup$
    – mikeazo
    Sep 7, 2016 at 12:29
  • 1
    $\begingroup$ @mikeazo new users get new shares $\endgroup$
    – PyRulez
    Sep 7, 2016 at 12:30
  • 1
    $\begingroup$ I'm assuming another requirement would be that none of the existing users learn the shares of the new users. I'm assuming given your requirements that a general MPC protocol is the best you will get. If you allow for everyone to get new shares, that would likely make things easier. $\endgroup$
    – mikeazo
    Sep 7, 2016 at 12:37
  • 1
    $\begingroup$ @mikeazo if old users see new shares, they can learn the secret with less than k of them. $\endgroup$
    – PyRulez
    Sep 7, 2016 at 12:38

2 Answers 2

Reset to default
4
$\begingroup$

Here is the setup I am assuming, in the beginning you have a dealer who distributes $k$ shares from a $k$ out of $n$ secret sharing (e.g., Shamir) to the $k$ parties currently present.

What you would like is that if at some point in the future the $k$ parties want to add an additional party, they can do so, without requiring the dealer to cooperate at that moment in time.

As you mention, one way to do this would be with a general MPC. Another way to do this, would be, if the dealer agrees at the start that some additional shares should be available so that if the $k$ parties want to let another person in, they can, the dealer can generate a few additional shares right off the bat (say $k+t$ instead of just $k$ shares). Distribute $k$ shares to the $k$ parties, then secret share the remaining $t$ shares with the $k$ parties. That way, each of the $k$ parties has their own share, and shares of the remaining $t$ shares. If they want to give someone else a share, they send them a share of one of the $t$ shares. That party reconstructs to get a share of the original secret.

This allows the $k$ original parties to keep their original shares, while giving a new share to a new party. The dealer can also set thresholds on how many of the $k$ parties need to come together to pass out additional shares (it doesn't have to be all $k$).

As I mentioned in my comment, if you remove the requirement that the original $k$ parties can keep their original shares, i.e., you allow them to get a fresh share at the same time that you are generating a new share for the incoming party, Desmedt and Jadjodia's paper on redistributing secret shares is the way to go (malicious model variants have been proposed if necessary).

Improve this answer
$\endgroup$
2
  • $\begingroup$ If we use genric MPC wouldn't the existing participants learn the new share? $\endgroup$
    – Meir Maor
    Jul 2, 2018 at 5:11
  • $\begingroup$ @MeirMaor, no. This one is kind of old, but what I think I was referring to was that they could compute on their existing shares to do an MPC computation to generate a new share. Since they are using MPC, each participant would learn a share of the new share (which they would pass to the new party). But they would definitely not learn the new share. $\endgroup$
    – mikeazo
    Jul 2, 2018 at 12:55
1
$\begingroup$

A proactive and dealer free protocol is described in this paper.

"Novel Adaptive Proactive Secret Sharing without a Trusted Party" - Xiuqunn Wang

This is ideal for the initiation of an smpc protocol.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is ideal for the initiation of an smpc protocol seems to miss the fact the question asks Is there a way to accomplish the task without a general multiparty computation scheme? Since OP abviously wants to avoid smpc all together, that last line of the 3-line answer is somewhere between "superfluous" and "missing the point". Maybe you could edit your answer to clarify how the fact that it may be ideal to initialize a smpc protocol helps the asker, who wants to specifically avoid taking the smpc path? $\endgroup$
    – e-sushi
    Jul 8, 2018 at 1:42

Your Answer

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

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