Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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).
