Reverse Shamir's Secret Sharing Algorithm?

Shamir's Secret Sharing algorithm works by breaking a single secret to multiple parts. While it is trivial to implement the reverse in a $n$-out-of-$n$ scheme, how would one implement an $m$-out-of-$n$ scheme were $k$ predefined shares $(k < m)$ are included in the share pool?

It is obvious that the resulting secret will be random but deterministic-ally derived.

Let's first recall the normal construction for Shamir's Secret Sharing:

We work in a finite field $\mathbb{K}$. This will usually be $\mathbb{F}_{256}$ (the binary field with 256 elements), so that the sharing can be conveniently done on a per-byte basis. We want an $m$-out-of-$n$ scheme, so the finite field must have at least $n+1$ elements. For each value to share, a random polynomial $P \in \mathbb{K}[X]$ of degree at most $m-1$: we write $P = \sum_{i=1}^{m-1} p_i X^i$ where the $p_i$ are chosen randomly and uniformly in $\mathbb{K}$, except for $p_0$, which we set to the secret value to share.

Thus, $P(0) = p_0$ is the secret value. The "shares" are $P(v_1)$, $P(v_2)$... $P(v_n)$, where the $v_j$ values are $n$ distinct non-zero elements of $\mathbb{K}$, that are chosen arbitrarily through a fixed, public convention (exactly which convention is used does not matter).

To retrieve the secret out of $m$ shares, we really rebuild the polynomial $P$, using Lagrange's polynomials. Let $N_i \in \mathbb{K}[X]$ be the following polynomial: $$N_i = \left(\prod_{1\leq j\leq n, j\neq i} (X - v_j) \right)$$ It is easily seen that $N_i(v_j) = 0$ for any $j \neq i$, but $N_i(v_i) \neq 0$. We thus define the Lagrange polynomial $L_i = N_i / N_i(v_i)$; it has value $1$ on $v_i$, and $0$ on all other $v_j$.

Then, $P$ is reconstructed as a linear combination of the Lagrange polynomials. If we have shares $P(v_1)$, $P(v_2)$,... $P(v_m)$, then we can write: $$P = \sum_{i=1}^{m} P(v_i) L_i$$ Therefore, the secret is: $$p_0 = P(0) = \sum_{i=1}^{m} P(v_i) L_i(0)$$

In a practical implementation, the coefficients $L_i(0)$ will be precomputed, and the reconstruction needs not bother with actually rebuilding the polynomial $P$; it just recomputes the secret $p_0$ as a linear combination of the shares $p_i$.

Now, let's examine the problem at hand: you have $k$ predefined "shares" and want to use them in a secret sharing. To do that, you simply apply the reconstruction above, and use fresh random values when needed. In other words, you first declare that the polynomial $P$ really exists, and that the $k$ predefined shares are $P(v_1)$, $P(v_2)$,... $P(v_k)$. You then generate randomly and uniformly $m-k-1$ extra shares, which you call $P(v_{k+1})$, $P(v_{k+2})$,... $P(v_{m-1})$. Finally, you define that your secret value is $P(0)$. At that point, you have the evaluation of $P$ on exactly $m$ values ($0$, and the non-zero elements $v_1$ to $v_{m-1}$). You then define new Lagrange polynomials for a set of values that include $0$: \begin{eqnarray*} N'_0 &=& \prod_{1\leq j\leq m-1} (X - v_j) \\ N'_i &=& X \prod_{1\leq j\leq m-1, j\neq i} (X - v_j) \\ L'_0 &=& N'_0 / N'_0(0) \\ L'_i &=& N'_i / N'_i(0) \\ \end{eqnarray*} At that point, you can find $P$: $$P = P(0) L'_0 + \sum_{i=1}^{m-1} P(v_i) L'_i$$

What happened here is that you rebuilt a polynomial $P$ that matches your predefined shares and the target secret value; you also generated new random shares in order to have enough value to make a unique candidate for $P$. Now that you have the polynomial $P$, you can compute as many extra shares $P(v_i)$ (for $i\geq m$) as you need.

Some extra notes:

• If $k < m$, you can still choose the secret value, as shown above. It does not need to be "something random". If you do not want to choose the shared secret, you can simply create $m-k$ extra shares (instead of $m-k-1$) and use the normal Lagrange interpolation to get $P$, at which point you can obtain $P(0)$ as the shared secret. The computations always work, for all input values (that's how the scheme is secure, indeed). This would also be the situation if you started from exactly $m$ predefined shares: if you want a threshold of $m$ and already have $m$ shares, then there is no room for choice of the secret.

• In all of the above, I used $P(0)$ for the secret, but that's purely conventional. $0$ is not special here. The gist of Lagrange interpolation is that, for any set of values $P(v_i)$ on $m$ different field elements $v_i$, there is a unique matching polynomial $P$ of degree less than $m$ (i.e. a polynomial that can be represented as $m$ coefficients).

• Thank you a lot for the very in-depth and informative reply, it shed a lot of light into how Shamir's Algorithm works internally. You mention that it is indeed possible to actually compute the shares needed to reconstruct a pre-defined secret with a few pre-defined shares. My question would be whether the above scheme is trivial to actually compute on a common computer. – Alex Papageorgiou Aug 6 '18 at 8:49
• All of the above is easy to implement on a common computer, or even smaller systems such as smartcards. – Thomas Pornin Aug 6 '18 at 18:20