Introduction to Secret Sharing from First Principles

Say you want to share the following secret image with n people:

You have the following main requirements:

• At least 2 out of n people can reconstruct the image.

• No single person, besides yourself, can recombine the image.

How would you go about doing that?

A simple solution would be to share it with the group and have them pinky promise not to share the image. But then, each person has the image in full which goes afoul of your main requirement.

You might instead consider splitting the image into pieces and then distributing the pieces to members of the group. But naively doing it in this way would require all n members of the group to reconstruct the message.

This is the basis for secret sharing!

The above story is an example of a specific kind of secret sharing called visual secret sharing.

Secret sharing is the set of techniques used to split secrets that need to be distributed among a group of people with the caveat that no single member of the group can reconstruct the secret on their own but a minimal set of members of the group can reconstruct the secret.

Secret sharing has far reaching use cases such as

• Managing cryptocurrency wallet keys without needing access to the entire private key

• Managing encryption keys of symmetric encryption protocols such as AES

• building blocks for multiparty computation

For problems such as sharing encryption keys without any one person having access to the entire key, we need another form of secret sharing.

There are many forms of secret sharing in the wild but this article will be focused on Shamir's secret sharing, a secret sharing scheme that forms the basis of many multiparty computation protocols. The goal is to provide a technically accurate explanation without relying on whether you have deep mathematical knowledge. It suffices to understand polynomials which you may have seen in high school.

Quick Primer about Polynomials

If you have 2 points, what is the curve that goes through it?

A line!

If you pick any two points on a line, you always get back the same line.

You've uniquely defined a first degree polynomial.

If you have 3 points, what is the curve that goes through it?

A parabola!

And so forth…

This is can be generalized to nth degree polynomials.

In general, if you have n points, you can uniquely define the (n−1)th degree polynomial that passes through all of those points.

But how do you actually go about finding the nth degree polynomial that goes through a set of points?

Constructing Polynomials

Let's consider the following example:

But how do you actually go about finding an nth degree polynomial that goes through a set of points?

Let's consider the following example:
We have the set of points

. We know that these points lie on a unique cubic polynomial. So, we are looking for a polynomial of the form

You may recall from high school that the sum of nth degree polynomials is itself an nth degree polynomial. Given this fact, let's try to construct a polynomial that is the sum of individual cubic polynomials. Specifically, each cubic polynomial must be related to the original points somehow.

Let's try to build a polynomial l_i(x), where for each point, it has the following property: for points (xᵢ, yᵢ), build a polynomial lᵢ(x) s.t.
lᵢ(xᵢ) = 1 and t when i≠j.

Notice that the condition lᵢ(xⱼ) = 0 gives us the roots of the cubic polynomial. So, we know that

If you graph these out, you'll notice that besides have the roots that we want, none of these polynomials pass through give us lᵢ(xᵢ) = 1. Remember again that scaling an nth degree polynomial still gives you an nth degree polynomial. We can use that fact to scale change lᵢ so that lᵢ(xᵢ) = 1. For each of the polynomials, we need to find A, B, C and D which can be done by simply plugging in xᵢ for the given i. Then, we get the following polynomials

Now all the lᵢ(x)'s pass through 1 at xᵢ. But the polynomials lᵢ(x), still don't pass through our given points. Well, since lᵢ(xᵢ) = 1, we simply need to scale the polynomials by yⱼ to get yᵢlᵢ(xᵢ) = yᵢ.

We have finally constructed a set of polynomials that pass through our points. However, we still don't have 1 polynomial that goes through all of the points. Reusing the fact that the sum of an nth degree polynomial is an nth degree polynomial, we simply sum up the yᵢlᵢ(x) to get the final polynomial, L(x), that passes through all of the points.

This process is known as lagrange interpolation!

More formally,

Okay, how can this be used to secretly share our image?

Shamir's Secret Sharing

The intuition is to leverage what we just learned about polynomials and apply it to secret sharing our image. How can we do that?

If we encode the image as a single point on a polynomial, then that doesn't give us our requirement that no other person besides yourself can reconstruct the image. Any point on this 0th degree polynomial i.e. a constant, can reconstruct the entire image.

Instead, the key is to split the image, i.e. its pixels, as points on a polynomial.

Think about what we actually need.

Each pixel is just a number. And for each number, we want:

• one person alone learns nothing about it

• any two people can recover it exactly

So we need a way to hide a pixel such that:

• one piece is ambiguous

• two pieces uniquely determine it

We just saw something that behaves exactly like this.

A single point could lie on infinitely many lines. But two points define exactly one line i.e. a polynomial of the form p(x) = a₀ + a₁x.

So instead of storing the pixel directly, we hide it as part of a line. Since any 2 points on the line is enough to reconstruct the line, the intuition is to give members of the group points that lie on this line. But, now you may be asking, where do you actually encode the pixel in (a₀ + a₁x)

Let’s try the most obvious thing first. Suppose we store the pixel in the slope. That is, let (a₁) be the pixel value.

We can still pick a random intercept (a₀), generate points on the line, and hand one point to each person.

At first glance, nothing seems broken.

Two people can still recover the line. From the line, they can recover the slope. That gives them the pixel.

So what’s the problem?

The issue shows up when you look at a single share.

Remember, each person doesn’t just get one point. They get one point per pixel. In other words, each person gets a full image.

If the pixel is encoded in the slope, then the slope controls how the line changes. The intercept just shifts the line up and down.

So for each pixel, the value that a person sees is:

The only randomness here is in (a₀), which just shifts things.

That means the structure of the original image starts to leak into each share. Pixels with similar values produce similar behavior across the share image.

But this goes against our main requirement.

A single share should look like noise. It shouldn’t preserve any meaningful structure from the original image.

So encoding the pixel in the slope doesn’t actually hide the information in a robust way.

Instead, let’s try something simpler.

Pick a point ahead of time and say: the pixel is the value of the polynomial at this point.

The simplest choice is (x = 0).

That gives us:

So the pixel is stored in (a₀), and we pick a random slope (a₁).

Now everything lines up:

• one share → looks like noise

• two shares → recover the line

• evaluate it at (x = 0) → recover the pixel
  
  

This is exactly what we wanted.

We have just defined the famous secret sharing scheme known as Shamir's Secret Sharing.

Formally,

In practice, Shamir's Secret Sharing isn't done over integers but over finite fields. With integers, an adversary can learn information about S from every point D_i that they find. With finite fields, the shape of the graph and the order of its corresponding polynomial reveal nothing about each other.

There are very nice properties about Shamir's Secret Sharing scheme. Namely, the biggest one is the fact that it's a linear function. Specifically, for shares, [a] and [b], we have

and

for any public constant c and a share [a], we have

To recap:

• We break the image into pieces

• Each piece is a point on a polynomial

• Based on our group size and minimum reconstruction threshold, we randomly generate the polynomial

• When two group members need to reconstruct a pixel, they use lagrange interpolation to find the polynomial p(x) and then compute p(0) for the pixel

This is the core idea for shamir secret sharing and for the general class of linear secret sharing schemes.

If you want to see an implementation of Shamir's Secret Sharing, go check out the Stoffel repo for an implementation of Shamir's secret sharing scheme (and other secret sharing schemes that we support)!