Issuing New Shamir Secret Shares Using Multi-Party Computation

Shamir’s Secret Sharing (SSS) is a well known tool in the cryptography community. It is used in protocols like SLIP39 and FROST. SSS is popular because of its property of information-theoretic security (it is secure even against adversaries who have infinite computational power).

SSS is a powerful cryptographic tool, but it struggles in terms of flexibility. If a share is lost, it is not easy to issue new ones. Adding new shares is possible if enough shares are brought together to recover the original secret, but what if shareholders do not wish to reveal their shares to each other yet? What if they never want to reveal their secret shares, as would be the case with a threshold multisignature protocol such as FROST?

What if the shareholders distrust each other, or the dealer? How can they be sure their shares, or the shares of others, are valid?

In this article, I’ll cover the basics of how Shamir’s Secret Sharing works. I’ll demonstrate how to extend it with verifiable properties so that the dealer and shareholders need not trust one another. Finally I’ll describe a procedure which can be used to trustlessly issue new shares without recovering the full original secret. All the while, shareholders don’t need to trust each other or the dealer, and learn nothing about the new share they issued.

Notation

Just so we’re all on the same page:

Notation Meaning
is a member of set .
The set of integers mod .
Sampling randomly from the set .
A deterministic concatenation of and .

Polynomials

The basis of Shamir’s Secret Sharing lies in the fundamental theorem of algebra, specifically in the mechanics of polynomials, so we should do some review of this domain before we dive into SSS.

Review

  • A polynomial expression is any expression of variables* that involves only addition/subtraction, multiplication/division, and positive-integer exponentiation.
    • Usually single-variable polynomials denote the variable as .
  • The degree of a polynomial is the highest power of the variable used in the expression (with a non-zero coefficient).
  • The coefficients of a polynomial are the multipliers alongside each power of the variable when it is in standard form.
  • The roots of a polynomial expression are the values of which cause the expression to evaluate to zero.
    • Sometimes the roots of a polynomial are complex, meaning they involve numbers which make use of the imaginary number . Don’t worry, we won’t be dealing with complex numbers today!
  • A polynomial function is a function which can be computed by simply evaluating a polynomial on an input .

* Note that today I’ll be writing exclusively about univariate (single-variable) polynomials, where the variable is denoted .

For example, is a polynomial function with degree (AKA a cubic polynomial). Its coefficients are for the cubic () term, for the linear () term, and for the constant () term.

Polynomials aren’t only written in standard form though. They could be written in factored form, such as , or a mix of the two, like . As long as only the addition/subtraction multiplication/division and natural number exponentiation operations are used on the variable , it is still called a polynomial.

By contrast, a function like is not a polynomial because it takes the base to the power of . Such a function doesn’t behave according to the laws of polynomials.

Almost everyone will have at least some experience handling polynomials, as most high school math classes deal extensively in linear (degree ) polynomials such as , and quadratic (degree ) polynomials such as . Students are taught how to factor them, expand them, find their roots, graph them, and many other things, but only in university level mathematics would you be taught how powerful these tools are for cryptography.

Interpolation

The Fundamental Theorem of Algebra states:

Every non-zero, single-variable, degree polynomial with complex coefficients has exactly complex roots.

In other words: If a polynomial has degree , then there are exactly different values of which make it evaluate to zero (if we include complex numbers). If you think about the shapes that these functions take on the Cartesian Plane, this makes sense.

This theorem has a helpful consequence.

Say we have a set of points , where all values are distinct (i.e. ). Then there exists some unique polynomial function of degree at most which passes through all points, such that for each point from . A common way to phrase this is that interpolates the points .

Uniqueness: Proof by contradiction

How do we know is unique? We will assume it isn’t true. In exploring the consequences of that assumption, we will find a logical contradiction.

Assume there exists two non-zero polynomial functions and of degree at most which pass through those points, such that for at least one input (indicating the polynomials are different), but also that for all points.

Since and each have degree at most , each has at most roots.

Consider the difference between the two polynomials . Since we assumed , this implies .

Since at all , it follows that for all as well. This implies the polynomial has at least roots.

Recall was defined as , so can’t have a higher degree than either or , which we assumed have degree at most . Adding and subtracting polynomials merely adds or subtracts their coefficients without introducing higher-degree terms. Thus must have at most degree .

This is a contradiction. On one hand, must have roots. On the other hand, it must have degree at most , which - due to the Fundamental Theorem of Algebra - means it must have roots.

This contradiction is proof that must be equal to the zero polynomial (i.e. ). This is the only logically consistent way for to have roots while also having degree at most .

The very special and helpful property of interpolating polynomials is: To interpolate a polynomial of degree , we need at least evaluations of (i.e. points that passes through).

Said differently, if we create evaluations of , such as , then only of those evaluations are needed to reconstitute and thus evaluate it at any input. With any fewer than evaluations, we would gain no new information about itself, because there exists an infinite number of degree polynomials which pass through those same or fewer points.

Perhaps by now you might be starting to see why polynomial interpolation is at the heart of Shamir’s Secret Sharing.

Demonstration

This concept is easier to understand visually with linear polynomials. Picture two points and on the Cartesian plane.

Any two points are sufficient to uniquely describe a line between them. Remember that a line on the Cartesian plane is just a degree-1 (AKA linear) polynomial. Only one unique line (polynomial) passes through (interpolates) the two points.

In this case, the polynomial happens to be .

If we are given additional points and located along the same line, this doesn’t change the polynomial function which interpolates all four points.

However, if we are given only one evaluation, say where , we gain no information about because there are infinite other linear polynomials (lines) which pass through the same point.

This concept generalizes to higher-degree polynomials! Given the same two points and , there are infinite degree-2 (AKA quadratic) polynomials which pass through those points.

But add a third point and suddenly we can find only one quadratic polynomial which interpolates them.

but how would we actually do the interpolation?

There are many ways to skin this cat. Given data points, the polynomial we interpolate from them would be the same. As long as our method works and works quickly, the mechanics aren’t crucial to know at this point. Many interpolation methods exist:

  • Lagrange Interpolation (the most commonly known)
  • Newton Interpolation
  • Inverting the Vandermonde Matrix (uses linear algebra)

For the time being, assume we have some black box interpolation algorithm which takes in some set of points called , and spits out a polynomial which has degree at most . I’ll discuss how works a bit later. By now you’re probably dying to know how this all applies to Shamir’s Secret Sharing.

Shamir’s Scheme

This wouldn’t be a math article if we don’t start by defining some parameters.

  • Let be a Finite Field containing elements, where is some large prime number.
    • If you’re not familiar with Finite Fields, just consider it as a special group of numbers, such that addition, subtraction, multiplication, and division all work normally as they do within the real numbers, except there are a finite quantity of possible discrete numbers that can be used.
    • Usually, this is the set of integers modulo a prime number , AKA .
  • Let be a secret such that . Our goal is to break into shares so we can distribute them.
    • Usually is just some large random number randomly sampled from , such as a private key.
  • Let be the total number of shares we want to issue.
  • Let be the minimum number of shares required to reconstruct , such that .

Distribution

Shamir’s Secret Sharing scheme starts with a trusted* dealer who knows and wants to distribute it evenly as shares, such that any subset of at least shares can be recombined to recover . For example, the trusted dealer might be backing up a signing key or encryption key across physically distributed locations, or with trusted representatives such as staff, attorneys, family, and close friends.

* There are other schemes which allow mutually distrustful parties to generate shares of a common but yet-unknown secret, but that is out of scope for today.

  1. The dealer samples random values from .

  2. The dealer treats as the coefficients of a degree polynomial function .

  1. The dealer assigns each share a unique index , labeling each share . They could be randomly selected, but usually indexes are just the ascending natural numbers, so we’d have . The indexes must not be zero and must not have repetitions.

  2. The dealer evaluates at each of the different indexes.

  1. The dealer distributes shares as tuples of . is the private data within each share which must be kept secret.

Recovery

At recovery time, the original secret is assumed to no longer be available - Perhaps it was lost in a boating accident, or left encrypted with an unknown password. Perhaps the original dealer was hit by a bus and her representatives are now charged with handling her affairs. Perhaps the dealer is no longer willing to cooperate. Regardless, the shareholders must recover independently, using only their shares.

Let be the set of or more share indexes which are participating in the recovery. We assume that at least shares are available. Some shareholders might not be online or might also have been hit by aforementioned bus. Some shares may have been physically destroyed, such as in house fires or boating accidents. As long as shares are still available, and can be reconstructed.

Each of the shares in is given to some trusted* recoverer whose duty is to reconstitute the original secret given or more shares. The recoverer might be one of the shareholders, or an independent entity.

* Care is needed here. If the recoverer is malicious, they might use themselves for some nefarious purpose. SSS doesn’t specify what to do once is recovered - It is quite limited in that capacity. Canonically, SSS is solely a secret backup and recovery tool. What comes after is up to the implementation.

  1. The recoverer is given a set of or more shares . Shares must have unique indexes.

  2. The recoverer treats the shares as the evaluations produced by some degree polynomial function over , such that for all .

  3. The recoverer uses a polynomial interpolation algorithm to interpolate the polynomial .

  4. The recoverer evaluates . This outputs , because:

Gotchas

SSS seems simple, but it is an easy protocol to screw up in practice.

  • It is very important that the non-constant coefficients of are totally random, otherwise the information-theoretic security of SSS is lost.
  • When distributing shares, it is crucial that the dealer does not distribute a share evaluated at index zero, because since , they would be giving away the secret .
  • Shareholders must be trusted not to use phony shares when recovering. If one shareholder submits a phony or faulty share, they could change the secret which is recovered to something unusable, and nobody would be able to tell which shareholder screwed up.
  • There must be a trusted recoverer machine and a trusted dealer machine who will both know . If either is compromised, will naturally be exposed.
  • The dealer and the recoverer must use the same finite field , which could result in incompatibilities if this field is non-standard.

But still, the power of SSS is undeniable, especially as a primitive when combined with other tools.

Before we demonstrate how shareholders can trustlessly issue new shares, I want to take a moment to learn about how can be interpolated. If you’re already familiar with polynomial interpolation, click here to skip ahead.

Interpolation

In my opinion, the most intuitive interpolation method is Lagrange Interpolation. First discovered in 1779 by Edward Waring, this method is named after the scientist Joseph-Louis Lagrange who made the method famous.

The Lagrange method takes a step-by-step approach to achieve a polynomial with all of our desired qualities. Given points with distinct -coordinates, we should be able to find a polynomial function which:

  1. interpolates all points ()
  2. has degree at most

Where to begin? We can make use of the Fundamental Theorem of Algebra once more: A degree polynomial will have roots - i.e. it outputs zero at different inputs.

Since we are given points, we can define a degree polynomial which outputs zero at all inputs , specifically excluding the input where it outputs… something which is not zero.

This is the simplest polynomial we could define with roots at . If we plug in any , then .

Seems weird to do this, but now has a handy property: Out of all the -coordinates we care about, it only has a non-zero output specifically at . That output can be predicted in advance and scaled however we’d like it.

Specifically, we can scale by multiplying by and dividing by . This scales the output to when we input .

Let’s define this operation as a new polynomial function .

As a result, outputs our desired value at input , or it outputs zero at all other .


We can expand and regroup factors to make everything more readable.

Imagine if we repeat this for all , and we find . Since each passes through the point but outputs zero at all , then the sum of all would be a new polynomial which interpolates all the points .


More commonly, this is written in the mathematical literature in terms of a basis polynomial which outputs at and zero at . Then the output of is scaled by a factor of . The textbook definition of a Lagrange Interpolation Polynomial is usually written as


Notice how only needs in order to be evaluated - its definition doesn’t require any of the -coordinate values, so can be computed on any input by anyone who knows , whether or not they know the corresponding evaluation outputs .

A common way that modern academic papers will represent the basis polynomials is by calling them Lagrange Coefficients defined for some constant . They will usually be given some greek symbol such as (lambda), with the subscript representing the value in the point which is being interpolated by that specific basis polynomial.


Example

Here we explore three basis polynomials for the -coordinates .