I am trying to implement Shamir's secret sharing in C++. I have got the generation of shares working.
However, I am very confused with the reconstruction of shares. I get the part on how three users can reconstruct the secret. But what if there are more than 3 users needed to reconstruct the secret? How do I implement the formula then?
Any help would be appreciated.
Suppose $s_0, s_1, s_2, \ldots, s_{k-1}$ are elements from the finite field you are working in, where $s_0$ is the secret to be shared, and the $s_i, i > 0$ are randomly chosen nonzero elements of the field. Then, the polynomial used to construct the shares is $$S(x) = s_0 + s_1x + s_2x^2+ \cdots + s_{k-1}x^{k-1}$$ and the shares themselves are $y_i = S(x_i), 1 \leq i \leq n$ where the $x_i$ are $n$ distinct nonzero elements of the field. Note that $n$ must be at least as large as $k$, and that the polynomial $S(z)$ can be recovered from any $k$ of these $n$ shares. This is commonly done using Lagrange interpolation as has been already pointed out in the other answers. Assuming without loss of generality that $y_1, y_2, \ldots, y_k$ are the shares available for reconstruction, $S(x)$ is a weighted sum (or linear combination) of $k$ different polynomials $g_i(x)$. We have $$\begin{align} S(x) &= \sum_{i=1}^k y_i \cdot g_i(x)\\ &=\sum_{i=1}^k y_i \prod_{j=1, j\neq i}^k\frac{x-x_j}{x_i-x_j}\\ &= y_1 \frac{(x-x_2)(x-x_3)\cdots(x-x_k)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_k)} + y_2 \frac{(x-x_1)(x-x_3)\cdots(x-x_k)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_k)}\\ &\qquad +y_3 \frac{(x-x_1)(x-x_2)(x-x_4)\cdots(x-x_k)}{(x_3-x_1)(x_3-x_2)(x_3-x_4)\cdots(x_3-x_k)} +\cdots\\ &\qquad +y_k \frac{(x-x_1)(x-x_2)\cdots(x-x_{k-1})}{(x_k-x_1)(x_k-x_2)\cdots(x_k-x_{k-1})} \end{align}$$ Notice that each $y_i$ is being multiplied by the polynomial $$g_i(x) = \frac{1}{c_i}(x-x_1)(x-x_2)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_k)$$ which has as factors all terms of the form $(x-x_j)$ except $(x-x_i)$, and the constant $c_i$ is given by $$c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_k). \tag{1}$$ In other words, $g_i(x_i)=1$ and $g_i(x_j)=0$ for all $j \neq i$.
So there is a lot of calculation required, and care must be exercised when writing the computer program that carries out these calculations. But note that we really don't need to compute the entire polynomial $S(z)$ since all we want to find is the secret $s_0 = S(0)$. This saves us a fair amount of work because we have $$\begin{align} S(0) &= \sum_{i=1}^k y_i \cdot g_i(0)\\ &=\sum_{i=1}^k y_i \prod_{j=1, j\neq i}^k\frac{-x_j}{x_i-x_j}\\ &= y_1 \frac{(-x_2)(-x_3)\cdots(-x_k)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_k)} + y_2 \frac{(-x_1)(-x_3)\cdots(-x_k)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_k)}\\ &\qquad +y_3 \frac{(-x_1)(-x_2)(-x_4)\cdots(-x_k)}{(x_3-x_1)(x_3-x_2)(x_3-x_4)\cdots(x_3-x_k)} +\cdots\\ &\qquad +y_k \frac{(-x_1)(-x_2)\cdots(-x_{k-1})}{(x_k-x_1)(x_k-x_2)\cdots(x_k-x_{k-1})}\\ &= \sum_{i=1}^k y_i \cdot (-1)^{k-1}\frac{x_1x_2x_3\cdots x_k}{x_i\cdot c_i}\\ s_0 &= (-1)^{k-1} (x_1x_2x_3\cdots x_k) \sum_{i=1}^k \frac{y_i}{x_i\cdot c_i} \end{align}$$ So now the task seems a little easier. We need to compute $x_1x_2x_3\cdots x_k$ only once using $k-1$ multiplications, each $c_i$ has to be calculated separately and needs $k-1$ subtractions and $k-2$ multiplications. We multiply $c_i$ by $x_i$ and then do the division $y_i/(x_i\cdot c_i)$. The hard part in all this is thus writing the code for computing each $c_i$. And of course we must remember that all this is using finite-field arithmetic so that we must use operations or subroutine calls as described in the answer by Ilmari Karonen.
The formula you are looking for is Lagrange Basis Polynomials. Essentially, each share consists of two values, an x coordinate and an y coordinate. The x coordinate might, depending on your specific needs, be implicitly determined by context, such as a preexisting identifier for the entity holding the share. The only requirement is that it is non-zero and unique. The y coordinate is calculated as the value of the polynomial (with random coefficients and a degree equal to the threshold parameter) in the x coordinate.
Hence, in pseudo code, in order to generate $n$ shares such that at least $m+1$ shares are required to regenerate the secret, and presuming you work in a $\mathbb Z_p$ field, do the following:
$Input: $ Parameters $n, m$. A large prime $p$. Secret $s$, represented as an element in $\mathbb Z_p$. Coordinates $x_0,...,x_{n-1}$.
$Setup:$
You regenerate the secret $s$ from $k$ shares, such that $k \gt m$, by implementing the Lagrange Interpolation Polynomial $L(x)$ using the $x_j,y_j$ pairs you got access to, and calculating $s' = L(0)$.
As per your question, if $m = 2$ and $k = 3$ (presuming that $k = n$ for simplicity), the formula for $L(x)$ becomes:
$L(x) = y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$
The easy way to reconstruct the secret is using Neville's algorithm.
Basically, let the array y contain n shares (assumed to be represented as the type gf_t here), let the array x contain the points at which the polynomial was evaluated to generate those shares, and let sub(), mul() and inv() be functions/macros that perform the appropriate finite field subtraction, multiplication and inversion respectively. Then the following function computes the value of the interpolated polynomial at zero:
gf_t shamir_reconstruct (int n, gf_t *x[], gf_t *y[]) {
int d,i;
for (d = 1; d < n; d++) {
for (i = 0; i < n - d; i++) {
int j = i + d;
gf_t num = sub( mul( x[j], y[i] ), mul( x[i], y[i+1] ) );
gf_t den = sub( x[j], x[i] );
y[i] = mul( num, inv(den) );
}
}
return y[0];
}
This code is written in C, but it should work with appropriate modifications in C++ too. Note that this function overwrites the y array; if this is not desired, make a copy of it first. Finally, note that I wrote this code off the top of my head — I haven't actually tested it.
