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

For example, what if one share is accidentally exposed? If one share is public, the group’s threshold has essentially decreased from

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

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

If

Here follows a re-sharing protocol with verifiable commitments which enables a set of

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

# Strategy

Our goal is to construct a protocol which gives each shareholder

Let’s denote the new coefficients of this new polynomial

Naturally, no malicious subset of fewer than

One way to do this would be to get each shareholder

Consider the *coefficient polynomial*

We treat each

This seems a woefully roundabout way of constructing a random polynomial, but the reason why we approached

## Multi-Party Interpolation

We have a definition for

Recall how we defined

Individual shareholders don’t know

Remember that *That expression beside the Lagrange coefficient can also be thought of as a polynomial with parameter *

This expression for *distinct polynomials* on the same input

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

**Notice how shareholder **

A new share

Thus, for shareholder

Of course, this all hinges on the assumption that every *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

Every shareholder is assumed to have access to a consistent view of

## Resharing

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

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

This commitment, along with the original public polynomial coefficients

Each online shareholder

publishes their commitment to all other shareholders (including offline ones).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.Once a shareholder

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

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

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

- 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

We defined each coefficient