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

The set of integers mod 

Sampling 

A deterministic concatenation of 
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 positiveinteger exponentiation.
 Usually singlevariable polynomials denote the variable as
.
 Usually singlevariable polynomials denote the variable as
 The degree of a polynomial is the highest power of the variable used in the expression (with a nonzero 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!
 Sometimes the roots of a polynomial are complex, meaning they involve numbers which make use of the imaginary number
 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 (singlevariable) polynomials, where the variable is denoted .}
For example,
Polynomials aren’t only written in standard form though. They could be written in factored form, such as
By contrast, a function like
Almost everyone will have at least some experience handling polynomials, as most high school math classes deal extensively in linear (degree
Interpolation
The Fundamental Theorem of Algebra states:
Every nonzero, singlevariable, degree
polynomial with complex coefficients has exactly complex roots.
In other words: If a polynomial has degree
This theorem has a helpful consequence.
Say we have a set of
Uniqueness: Proof by contradiction
How do we know
Assume there exists two nonzero polynomial functions
Since
Consider the difference between the two polynomials
Since
Recall
This is a contradiction. On one hand,
This contradiction is proof that
The very special and helpful property of interpolating polynomials is: To interpolate a polynomial
Said differently, if we create
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
Any two points are sufficient to uniquely describe a line between them. Remember that a line on the Cartesian plane is just a degree1 (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
However, if we are given only one evaluation, say
This concept generalizes to higherdegree polynomials! Given the same two 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
 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
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 .
 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
 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.
 Usually
 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
* _{There are other schemes which allow mutually distrustful parties to generate shares of a common but yetunknown secret, but that is out of scope for today.}
The dealer samples
random values from . The dealer treats
as the coefficients of a degree polynomial function .
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. The dealer evaluates
at each of the different indexes.
 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
Let
Each of the shares in
* _{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.}
The recoverer is given a set of
or more shares . Shares must have unique indexes. The recoverer treats the shares as the evaluations produced by some degree
polynomial function over , such that for all . The recoverer uses a polynomial interpolation algorithm
to interpolate the polynomial . 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 nonconstant coefficients of
are totally random, otherwise the informationtheoretic 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 nonstandard.
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
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 JosephLouis Lagrange who made the method famous.
The Lagrange method takes a stepbystep approach to achieve a polynomial with all of our desired qualities. Given
 interpolates all
points ( )  has degree at most
Where to begin? We can make use of the Fundamental Theorem of Algebra once more: A degree
Since we are given
This is the simplest polynomial we could define with roots at
Seems weird to do this, but
Specifically, we can scale
Let’s define this operation as a new polynomial function
As a result,
We can expand
Imagine if we repeat this for all
More commonly, this is written in the mathematical literature in terms of a basis polynomial
Notice how
A common way that modern academic papers will represent the basis polynomials
Example
Here we explore three basis polynomials for the