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.