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 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.

All the above should be possible without any opportunity for adversarial shareholders to collude and corrupt the new shares, or learn anything about the secret.

Disclaimer

Don’t implement this in a production environment!

I have only just recently learned about secret resharing. Although I have taken the time to explore it and understand it myself, I still need to do more reading of the cryptographic literature before I can confidently say I understand it 100%. Please take this article with a grain of salt. Always consult an expert before rolling your own crypto.

I would much appreciate extra review on this concept and feedback about whether its security reduces to other proven schemes. If you have any input, please feel free to send me an email, or submit a PR on Github to fix this article.

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.

Here follows a re-sharing protocol with verifiable commitments which enables a set of 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.

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 .

  1. 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 .

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

  2. 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.

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

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

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

  1. 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 .