Resharing Shamir Secret Shares to Change the Threshold

In my last article on Shamir Secret Sharing, I outlined the basics of Shamir Secret Sharing (SSS) and described how polynomial interpolation works. Then I described an issuance protocol which adds new shareholders or recovers lost shares using multi-party computation practices. If you’re not already familiar with Shamir Secret Sharing, I highly recommend reading that article first.

This article will focus on a protocol called secret resharing, which I first heard about in this thesis by Mehrdad Nojoumian.

Resharing can be used to recompute new secret shares, optionally with a new threshold. In a Shamir secret sharing group with threshold , resharing allows a group of or more shareholders to cycle their shares in such a way that old shares from before the resharing event and new shares from after it are not compatible with one another. This might sound undesirable, but there are many cases where a group of shareholders may want to invalidate someone else’s share.

For example, what if one share is accidentally exposed? If one share is public, the group’s threshold has essentially decreased from to , beause that exposed share can now be assumed to be public knowledge. The bearer of the exposed share no longer has any weight in the group.

The group as a whole may wish to restore the security of their shares by revoke the exposed share. By regenerating their shares, the group ensures the exposed share cannot be be used, as long as the rest of the group securely erases their old shares as well.

Resharing also allows shareholders to change the threshold of their shares from to any new threshold . Shares created from the resharing protocol have the new threshold needed to recover the original shared secret.

As an added bonus, the set of participants can be changed during a resharing session: The set of shareholders before resharing can be different from the set of participants after resharing. Any number of old shareholders can be removed and any number of new shareholders can be added.

We want our protocol to work in an operating environment where some of our peers may be malicious. The protocol must be verifiable, so that adversarial shareholders cannot collude to corrupt the new shares, or learn anything about the group’s secret. This is called verifiable secret resharing, or VSR for short.

Mission

A set of or more shareholders may wish to change the threshold of their group’s shares from to some new threshold by regenerating their shares. Any set of or fewer shares from before the resharing execution must not reveal any information about the new shares produced by resharing.

If , then the resharing protocol should still work, but instead has the intended effect of simply rendering old shares unusable without changing the threshold.

The set of shareholders may also be changing. Some shareholder may be removed, and others introduced into the group.

Here follows a resharing protocol with verifiable commitments which enables a set of or more shareholders to compute updated shares. Shareholders who are offline at the time must be able to receive asynchronous messages, otherwise their old shares won’t be compatible with the new shares.

A detailed explanation of VSR is given in this paper by Wong, Wing, and Wang.

Parameters

Yippee! Let’s let all the things.

• Let be the total number of shareholders in the group.
• Let be the old threshold.
• Let be the desired new threshold.
• Let be the finite field of integers mod some prime number .
• Let be the old secret polynomial of degree , with coefficients in .
• Let be the new secret polynomial of degree , with coefficients in .
• Let be an additive group generator (e.g. an elliptic curve base point) of order .
• Let each be an index in representing a share.
• Let be the original evaluation of the secret share polynomial for share , such that .
• Let be the new evaluation of the secret share polynomial for share , such that .
• Let be the set of at least share indexes whose bearers are online and participating in the threshold change protocol.
• Let be an interpolation algorithm which takes in a set of points and outputs a unique polynomial which interpolates all points in .
• Let be the original public coefficients of the secret polynomial , such that

• Let be the Lagrange coefficients for a set of inputs , used to evaluate a polynomial at .

…such that for any polynomial of degree at most .

Strategy

Our goal is to construct a protocol which gives each shareholder the means to verifiably compute , where is a new randomly generated degree polynomial, which shares a constant term with the old joint share polynomial , such that . Once participants have shares generated by , the threshold is changed without changing the secret, because one needs only evaluations to interpolate the degree polynomial , and thus learn the original secret .

Let’s denote the new coefficients of this new polynomial . Since the evaluation must be the same as , we can easily conclude the constant terms are the same. What about the other coefficients?

Naturally, no malicious subset of fewer than shareholders must be able to learn or influence anything about these new coefficients. Thus, the new coefficients must be jointly constructed. Every shareholder in must contribute a random value to every coefficient. This ensures a cabal of malicious shareholders cannot bias unfairly - As long as at least one party contributes honest random values, the new coefficients will also be random.

One way to do this would be to get each shareholder to generate random values (one for each of the new coefficients). We treat each as a set of points . Note how each shareholder in contributes one point to each set - one for every coefficient in .

Consider the coefficient polynomial of degree at most which interpolates all points in . The constant term will be uniformly random. Any attacker who knows or fewer evaluations of (i.e. who knows values of ) will be unable to interpolate .

We treat each as the -th coefficient of for . This defines as a degree polynomial with jointly-chosen random coefficients.

This seems a woefully roundabout way of constructing a random polynomial, but the reason why we approached this way will make sense once each shareholder tries to compute her new share.

Multi-Party Interpolation

We have a definition for which gives us a polynomial with our desired properties, but how can we ensure each shareholder can compute their own trustlessly? It is not immediately clear how to do this.

Recall how we defined above. We’ll take that definition and expand it, playing some algebraic trickery to find how shareholders can compute their new share without learning or using any secret information which should belong to other shareholders.

Individual shareholders don’t know , so we should try to substitute something else in its place. We can use a Lagrange interpolation polynomial, interpolating the shares , in place of . This allows us to factor out the sum and Lagrange coefficients.

Remember that is an interpolating Lagrange coefficient, so that for any polynomial with degree at most . That expression beside the Lagrange coefficient can also be thought of as a polynomial with parameter and input variable .

This expression for shows us a surprising (but mind-warping) fact: Any new share can be thought of as the constant term of a hypothetical degree polynomial, which is itself constructed by interpolating evaluations of a set of distinct polynomials on the same input .

Let’s clean up this definition and denote those resharing polynomials as .

Notice how shareholder has access to all the information needed to evaluate on any input .

A new share can be computed by interpolating these polynomials’ evaluations at input .

Thus, for shareholder to learn her updated share, she needs to receive , i.e. one evaluation of from every other shareholder .

Of course, this all hinges on the assumption that every is a polynomial at which , which is not guaranteed if we do not trust shareholders to submit honest evaluations. Thus, we must also require each shareholder to commit to their resharing polynomial by submitting the public coefficients of . This commitment can be compared by other shareholders to make sure everyone is behaving consistently, and then used to verify evaluations by computing .

We’ll see further down how these commitments are used. I think I’ve spent enough paragraphs on motivation at this point, so let’s dive into the specific protocol.

The Protocol

In this section, I’ll simply describe the resharing protocol step-by-step.

Assume every online shareholder can positively identify each other and can communicate with one-another over secure and authenticated channels.

Any offline shareholders not in must be able to receive messages asynchronously from the shareholders in , such as through encrypted email or message queues. If an offline shareholder misses any messages, they may be unable to verify or construct their new share. Alternatively, one might assume all shareholders to be online and available.

Every shareholder is assumed to have access to a consistent view of representing the public coefficients of , which can be used to compute any .

Resharing

1. Each shareholder generates random coefficients . These coefficients define a degree polynomial , whose constant term is the existing share .

2. Each online shareholder computes a commitment to the coefficients of .

This commitment, along with the original public polynomial coefficients , allows a bearer to compute for any value of , but not its discrete log .

3. Each online shareholder publishes their commitment to all other shareholders (including offline ones).

4. All online shareholders should ensure they hold the same set of commitments before continuing. Some shareholders may attempt denial-of-service attacks by submitting inconsistent commitments. This would cause the resharing protocol to fail unattributably, although without exposing any private data.

5. Once a shareholder receives all commitments , he evaluates for every other shareholder (including offline shareholders), and sends the evaluation to shareholder .

6. Once shareholder receives the evaluation from another shareholder , he can verify the evaluation using and the original public coefficients .

7. Once shareholder receives all , a new share can then be computed.

8. The shareholder can now compute new public coefficients for the joint polynomial.

• remains unchanged, because the secret itself remains unchanged.
• If , we can let where , because will be undefined.

Why can we compute the new joint public coefficients this way?

Recall we defined as a degree polynomial with coefficients .

We defined each coefficient as the constant term of a polynomial , which passes through the points .

The public version of these coefficients can be computed as .

9. Every shareholder can overwrite their old share with their new share , and discard .

In doing this, we have swapped out our old degree polynomial for a completely new degree polynomial . The only feature in common between the two polynomials is their constant term .

The new shares are evaluations of , and thus have a recovery threshold of instead of , yet still recover the same secret.

Recovery

At recovery time, the shareholders now need a subset of at least shares to recover the master secret .

Gotchas

The resharing procedure has its problems.

• Shares generated by resharing are not forwards or backwards compatible. After a resharing, shareholders in a group may become fragmented if some shareholders did not attend the resharing, or missed their asynchronous messages from the resharing.
  • Implementations which allow asynchronous resharing need to plan for this contingency, giving shareholders a way to prove their old share is valid but needs to be updated. They should support a share issuance protocol so that shareholders can regroup by issuing valid updated shares for the fragmented shareholders who missed the memo.
• There is no way to verify a shareholder deleted their old shares after a resharing event. Selfish shareholders can freely cache old shares. If a threshold increase occurs, it is impossible to know for sure whether all shareholders updated their shares. If some subset of shareholders maintain their old shares, the threshold has not really increased.
  • As a corollary, we can see that decreasing the threshold is easier than increasing it, as decreasing the threshold does not run into any incentive traps. It is natural for a selfish shareholder to prefer a share which carries more weight among the group.

Use Cases

Replacing shareholders

Perhaps a shareholder in the group is longer behaving. Perhaps they have stopped responding, and the whereabouts of their share is unknown. Perhaps the group no longer trusts this shareholder. The group can reshare the secret and exclude the misbehaving shareholder, perhaps reconfiguring the arrangement of the shares and sending some resharing evaluations to a replacement shareholder.

Revoking exposed shares

If one shareholder has accidentally exposed their share, resharing could be useful to revoke it by generating a new set of shares that are not backwards compatible with the exposed share.

Changing the threshold

As discussed, resharing is a relatively straightforward way to change the recovery threshold of a shared secret, and it is highly flexible. Unlike other methods, resharing allows choosing an arbitrary new threshold , whereas some threshold-modification protocols only work when or vice-versa.

Defending against mobile adversaries

Since shares are not backwards or forwards compatible through resharing events, we can view resharing as a sort of share-cycling procedure.

Hacking people is hard work. Consider an attacker who can steal some shares from one shareholder at a time, but must do so over a protracted duration, say weeks or months, breaking into each target one-by-one and stealing their share, until they have or more shares and can recover the secret .

If shareholders proactively reshare their secret with new polynomials once every day, or once a week, it dramatically reduces the window of opportunity for this attacker. The attacker must now break into at least shareholders’ machines on the same day, or within the same week.

Reasoning

Consider the set of resharing polynomials each of degree .

If each of the shareholders in distribute an evaluation of their resharing polynomials to every other shareholder in the group, then only a subset of of those evaluations are needed to completely reconstruct every polynomial . This would allow one to reconstruct all . The resulting set of shares can then be used to reconstruct .

However, this would be inefficient if shareholders had to store those evaluations as their new share. We want shareholders to be able to update their shares from to some new share of the same size, without storing extra redundant data for every threshold change, in such a way that their shares are still fully valid under canonical Shamir secret sharing protocols.

Instead, we want a simple share representable as , so that all a shareholder must do to update their share is overwrite their old share with a new share . We also want to be able to concisely update the joint public polynomial’s coefficients , so that we can easily verify shares (and resharing polynomial evaluations) in the future. This is where most of the complexity in the resharing protocol lives.

Conclusion

Having only recently discovered the wealth of mathematical literature on threshold secret sharing, I feel rather overwhelmed at the incredible scope of designs that clever people have concocted. Prior, having only known the basic Shamir Secret Sharing scheme, I had no idea it was possible to change shareholders, thresholds, or secrets so easily. Can’t wait to see what comes next.