## Introduction

Multi-Party Computation (MPC) heaivly relies on the primitive of Shamir’s secret sharing (SSS) for various use cases.
In this secret-sharing scheme a set of $n$ parties would like to hold a secret in a distributed manner.
The secret, which will be denoted $s$ for the rest of this post, is an element of a field $\mathbb{Z}_p$.
It is important to mention that *“distributed manner”* means that party each party $P_i$ will hold a piece of information $p_i$ such that pieces of information can be later used to reconstruct the original share $s$.
Typically secret-sharing schemes are associated with a *threshold* through which the security of the scheme is defined.
A secret-sharing scheme with security threshold $t$ should satisfy the following security guarantees:

- Each set of $t+1$ parties they will be able to retrieve, or make a certain MPC-driven computation on $s$.
- Each set of up to $t$ parties who choose to collude can learn nothing about $s$.

The parameters $t$ and $n$ are known prior to the sharing of the secret.
With all that being said, it is still unclear how is such a scheme being bootsrapped?
How are the shares $p_i$ being created and sent to each party $P_i$?
To simply things we assume for now that there is a *trusted-dealer* who sends to each party $i$ its corresponding $p_i$.
Later we will see how we can get rid of this trusted dealer.
So what is this $p_i$, and how does it look like?

### Shamir’s Secret Sharing

**DISCLAIMER**: I may not be 100% algebraically accurate for the sake of both brevity clarity.

**REMINDER**: A polynomial $P(x)$ is a function which can be expressed algebraically in the following form: $P(x) = \sum_{i=0}^k a_ix^i$ for some number $k$.
The $a_i$ are called **“coefficients”** and the largest number $i$ such that $a_i \neq 0$ is the **“degree”** of the polynomial.
Note that in the case that all coefficients are zero, we consider the degree to be $\infty$.

Shamir’s secret sharing utlizes one key algebraic property about polynomials known as the *“unique interpolation theorem”* which states that:

Given a set $S={(x_0,y_0),…,(x_t,y_t)}$ of $t+1$ pairs of field elements, such that at least one $y_i \neq 0$, there exists a unique polynomial $P_S(x)$ of degree at most $t$ such that $P_S(x_i)=y_i$ for all $0\leq i\leq t$.

Therefore, given two distinct polynomials $P_1(x), P_2(x)$ of degree at most $t$ and a set of $t+1$ sample points $x_0,…,x_t$ then for at least one $i$ between $0$ and $t$ it must hold that $P_1(x_i) \neq P_2(x_i)$.
Thus, a set of $t+1$ evaluations of a polynomial is all that is required to reconstruct a polynomial $P(x)$.
By *“reconstructing”* we mean deriving the coefficients $a_i$ of the polynomial so we will be able to express the polynomial in the form $P(x)=\sum_{i=0}^ta_ix^i$.
This process of reconstructing a polynomial from a set of its evaluations is also known as *interpolation*.

### Polynomial Interpolation

Before diving into how the sharing is done, let’s answer an even more fundamental question. Given these $t+1$ evaluations of a polynomial at points $x_0,…,x_{t}$, how can the interpolation polynomial be constructed? The reconstruction’s smallest building blocks will be a set of degree $t+1$ polynomials $\pi_i^t(x)$ that satisfy for $x \in \{ x_0,…,x_{t} \}$ the following $t+1$ constraints:

\[\pi_i^t(x) = \begin{cases} 1 &\quad x=x_i\\ 0 &\quad x\neq x_i\\ \end{cases}\]Notice that for $x$ values which are not one of $x_1,…,x_{t+1}$ the value of $\pi_i^t(x)$ is not necessarily 0 or 1 and that there is exactly one polynomial who satisfies these constraints for every choice of $i$ and $t$ (according to the unique-interpolation theorem). Thus, the polynomial $\pi_i^t(x)$ can be constructed with the following formula:

\[\pi_i^t(x) = \prod_{j=1\\j\neq i}^{t}\frac{x - x_j}{x_i-x_j}\]This formula satisfies all our constraints:

- If $x=x_i$ then all factors of the formula will be $1$ and thus $\pi_i^t(x_i)=1$.
- If $x=x_j$ for $j\neq i$ then at least one of the factors’ numerator will be zero and thus $\pi_i^t(x_j)=0$.

The actual coefficients of $\pi_i^t(x)$ can be derived from this formula by programmatically multiplying the factors of the product.

Two observations that will allow us to reconstruct any polynomial of degree $\leq t$ from its samples on points $x_1,…,x_{t+1}$ are as follows:

- Let $P(x)=\sum_{i=0}^{t}p_ix^i,Q(x)=\sum_{i=0}^{t}q_ix^i$ be two distinct polynomials of degree $\leq t$, then their sum is also a polynomial of degree $\leq t$.

This one is correct because their sum can be expressed as a polynomial where coefficients are simply added: \(P(x)+Q(x)=\sum_{i=0}^{t}(p_i+q_i)x^i\)

- Let $P(x)=\sum_{i=0}^tp_ix^i$ be a polynomial and let $a \neq 0$ be a constant. Then the product $a\cdot P(x)$ is also a polynomial of degree $\leq t$.

Similarly to the previous one, this observation is correct because the resulting polynomial is the same as the original polynomial with all coefficients just multiplied by $a$.

Great, now using these observations we can create a polynomial $P(x)$ such that $P(x_i)=y_i$ for all $0 \leq i \leq t$. First let’s show the construction of the polynomial and and then explain why it satisfis the required properties. So, the polynomial is the following:

\[P(x) = \sum_{i=0}^ty_i\pi_i^t(x)\]First, according to the previous two observations and since each $\pi_i^t(x)$ is a degree $\leq t$ polynomial, by multiplying each $\pi_i^t(x)$ by a constant $y_i$ and summing them, the result is also a polynomial of degree $\leq t$, so we have check the first requirement, great! Next, for each $x_i$ we get that:

\[\begin{split} P(x_i) & = \sum_{j=0}^ty_j\pi_j^t(x_i) \\ & = y_i\cdot\overset{=1}{\overbrace{\pi_i^t(x_i)}} + \sum_{j=0\\ j\neq i}^ty_j\overset{=0}{\overbrace{\pi_j^t(x_i)}} \\ & = y_i \end{split}\]By that achieving the requested interpolation.
This interpolation algorithm is known as *“Lagrange Interpolation”* and the $\pi_i^t$ are often referred to as *“Lagrange Polynomials”*.

### Sharing Algorithm

Now that we know how a polynomial can be (uniquely) interpolated from a set of its evaluations, let’s go back to the original polynomials-based secret-sharing scheme.
The sharing goes as follows.
The trusted dealer, who knows the secret $s$ will generate a polynomial $F(x)=\sum_{i=0}^tf_ix^i$ of degree $t$ such that $F(0) = f_0 = s$ and for $1\leq i \leq t$ the dealer will pick $f_i$ randomly from the field $\mathbb{Z}_p$.
The dealer will send, for each party $i$ between $1$ and $n$ its share $p_i = F(i)$.
In other words, each party $i$ has a **share of the secret** which is the polynomial $F$ evaluated at point $i$.

So why is this even working? Since the polynomial $F$ is of degree $t$, any set of $t+1$ parties will be able to derive $F$ according the to unique interpolation theorem. However, for any set of $t$ parties, they will not be able to learn anything about $F$ or $s$ since up to $p$ different polynomials can be created that all agree with the evaluations of $F$ given to these $t$ parties, and each will be evaluated to a diffenret value at point $0$.

This is all fun, but at this point we have this *trusted dealer* which we must trust and who is accessible to the secret.
In many MPC scenarios we want some secret $s$ to never exist at a single point but still be able to make some computations based on its value.
Therefore, we must find a way to get rid of the trusted dealer.

### Shamir’s Secret Sharing - Without a dealer

In this section we will try to get rid of the dealer and still achieve the same effect of Shamir’s secret sharing where a subset of $t+1$ out of $n$ parties, each holding $p_i$ - a share of a secret, can restore the secret, but without a dealer. One question that must be asked at this point is what is the meaning of $s$? In particular, since no one knows $s$ (since there is no dealer), what exactly are we trying to achieve? Well, we will change our goal by a little bit so that instead of sharing an existing secret $s$ held by the dealer, the parties will generate cooperatively a secret and share it between them without any party at any time holding the secret as a whole (or any information that may allow it to compute it efficiently).

This can be achieved in the following way.
Party $i$ (for all $1\leq i \leq n$) will generate a *local secret* denoted $s_i$ so that the final secret $s$ shared among all parties will be $s = \sum_{i=1}^{n}s_i$.
To achieve this, each party $i$ will share $s_i$ between all parties by following the steps of the dealer from the previous section.
To be explicit, it will randomly create a polynomial $F_i(x)$ of degree at most $t$ such that $F_i(0) = s_i$ and send to party $j$ a share of this secret denoted by $p_{i,j}=F_i(j)$. Now each party $j$ who hold the secret shares $\left(p_{1,j},…,p_{n,j}\right) = \left(F_1(j),…,F_n(j)\right)$ will sum all these shares to get $p_j = \sum_{i=1}^np_{i,j}$.
Since $F_i(x)$ are all polynomials of degree $t$, their sum is also a polynomial of degree at most $t$ denoted by $F(x) = \sum_{i=1}^nF_i(x)$.
Notice that:

- $p_j$, the secret share of party $j$ satisfies: \(p_j = \sum_{i=1}^np_{i,j} = \sum_{i=1}^nF_i(j)=F(j)\)
- The shared final secret $s$ satisfies: \(s = \sum_{i=1}^ns_i = \sum_{i=1}^nF_i(0) = F(0)\)

Therefore, the parties ended in a state where each party holds a secret-share $p_j$ which is the evaluation of a degree $\leq t$ polynomial $F(x)$ at point $j$ and the shared secret is $s=F(0)$. From previous section we know that this allows each subset of parties of size $\geq t+1$ to compute the secret and any subset of $\leq t$ parties will not be able to derive any information about the secret.

Without getting too much into details, the share $s$ isn’t exposed to any party along the way because if it did, it would imply the original secret-sharing algorithm from previous section to be insecure, but it is secure because of the unique-interpolation theorem.

## Motivation

Now that we know just enough about how secret shares are generated, we consider the scenario in which a set of $n$ parties have a secret shared among them so that each party $i$ holds a share of the secret, denoted $p_i=F(i)$ where $F(x)$ is a polynomial of degree at most $t$ and $F(0)=s$ where $s$ is the shared-secret which isn’t known fully to any party. The problem we want to solve is being able add party $n+1$ to the setup so that it will have its own share of the secret, $p_{n+1} = F(n+1)$ while maintaining the demand that each set of $t+1$ parties will be able to make some MPC-driven computations on the secret and any set of up to $t$ parties will not be able to do so.

The most naive approach is to gather all $n+1$ parties together, the original $n$ parties will forget about their existing shares $p_i$ and all parties will derive new shares $p’_i$ of a new secret $s’$. This is dissatisfactory since we don’t want the existing secret to change. On top of that, we would be happy if the solution will require as little communication as possible.

## The solution

Party $n+1$ should obtain $p_{n+1}=F(n+1)$ in a way that only it will learn $F(n+1)$ and no other party will learn anything about it. After obtaining this piece of information, the party will be able to collaborate with any set of $t$ additional parties to perform MPC-driven computations on the secret. The key observation which has driven us is:

If it only takes $t+1$ parties to compute the secret $s=F(0)$ it shouldn’t take more than $t+1$ parties to evaluate $F(n+1)$ and send it to party $n+1$.

According to this mindset, it should be possible to achieve a solution where not all parties are required to add new party in the happy flow where none of the parties is malicious.

### Naive Solution

One naive way in which a set of $t+1$ parties numbered $x_1,..,x_{t+1}$ could have done this is so that party $i$ will compute $Q_i=p_{x_i}\cdot\pi_{x_i}^t(n+1)$ and send it to the new party who will in turn sum these inputs to obtain $F(n+1)=\sum_{i=1}^{t+1}Q_i=\sum_{i=1}^{t+1}\left(p_{x_i}\cdot\pi_{x_i}^t(n+1)\right)$.

However, this imposes a major security risk, since party $n+1$ receiving $Q_i$ can divide it by $\pi_{x_i}^t(n+1)$ (notice that $\pi_{x_i}^t$ is a publicly known polynomial) and obtain $y_i$ for each $i$ and thus reconstruct the polynomial $F(x)$ with those $t+1$ shares and obtain the secret! Therefore, we should look for another solution that doesn’t violate the security requirements.

### Correct Solution

Each party $i$ out of the $t+1$ collaborating parties could locally compute their local additive share of $F(n+1)$ which is $Q_i=p_{x_i}\cdot\pi_{x_i}^t(n+1)$. As mentioned earlier the sum of the $Q_i$ s equals to the share of party $n+1$ which is $F(n+1)$. ($\triangle$)

Thus, we will think of their sum as a secret and we would like to share it. Recall that Shamir’s Secret Sharing algorithm without a dealer allowed some parties to distribute a secret between them so that the shared secret will be the sum of the local secrets of all parties. In our case the local secret of each party will be $Q_i$ and running this algorithm where each party uses $Q_i$ as the local secret will result in each party $i$ holding the evalution of some polynomial $G(x)$ at point $i$ such that $G(0)$ is the sum of all local secrets $Q_i$ which equals to $F(n+1)$ which is the share of party $n+1$ (see $\triangle$). Each party will send their respective evaluation of the polynomial $G(i)$ to party $n+1$ who will be able to reconstruct polynomial $G(x)$ and compute $F(n+1)$. Assuming Shamir’s secret sharing without a dealer is secure, no party should be able to infer $G(0)=F(n+1)$ and party $n+1$ shouldn’t be able to infer the secrets of the rest of the parties.