Secret sharing scheme with ability to add or update share number

Question

I would like to have a secret sharing scheme with the following properties:

1. Generate secret $S$ a split it to $N$ shares $(s_1, s_2, ..., s_N)$
2. Require $k$ of $N$ shares in order to reconstruct secret $S$
3. Update $N$ to $N+1$ and generate new share $s_{N+1}$ (everything remains the same, $N$ shares not changed)

The scenario is that I use Shamir secret scheme to split secret $S$ into for example 4 parts and require 2 of them to be present in order to reconstruct $S$. In that case if I would like to reconstruct S then I have to also input scheme type, i.e. 2 of 4.

What if I need to update number of parts but need to preserve existing shares and be able to reconstruct the same secret $S$? Is there a way how to do it?

Answer 1

With Shamir's Secret Sharing you can add as many shares as you want, as long as the threshold and the secret is unchanged.

You can see that neither the generation of the polynomial that produces the shares nor the reconstruction of the secret by polynomial interpolation require the parameter $N$ (number of shares), but only the threshold $k$.

Of course the number of shares $N$ should obey $N\leq p-1,$ since they need to be obtained as polynomial values at distinct points of the field $F_p$ and one point, usually zero, is reserved for the secret. You can increase $p$ if needed, but shares need to then be recomputed modulo the new prime you choose.

Answer 2

This is really an extended comment on @cygnusv's excellent answer.

Each share in Shamir's secret-sharing scheme really has two parts: the share $s_i=P(x_i)$ of the secret (where $P(x) = P_0 + P_1x +\cdots + P_{k-1}x^{k-1}$ is the polynomial of degree $k-1$ whose coefficient $P_0$ is the secret while the other $k-1$ coefficients are chosen at random) and the value of $x_i$, the argument at which $P(x)$ has been evaluated. That is, the $s_i$ values (or the $x_i$ values) by themselves do not allow a cabal of $k$ or more shareholders to reconstruct $P(x)$ or $P_0$: they need (at least) $k$ of the $N$ pairs $(s_i,x_i)\colon 1\leq i \leq N$ to find $P(x)$.

Now, having reconstituted $P(x)$, the cabal of $k$ shareholders can create an additional share $(s_{N+1},x_{N+1}) = (P(x_{N+1}), x_{N+1})$ but unless the cabal knows $x_1, x_2, \ldots, x_N$, there is no guarantee that $x_{N+1}$ is different from all of the previously used $x_1, x_2, \ldots, x_N$. That is, the newly created share $(s_{N+1},x_{N+1})$ might be the same as the share $(s_i,x_i)$ issued to a nonmember of the cabal. The new shareholder will enjoy the property that he can join up with any of the $\binom{N-1}{k-1}$ sets of $k-1$ original shareholders that do not have the $i$-th shareholder as a member and recreate the secret. But, he cannot recreate the secret in conjunction with any subcabal of $k-1$ shareholders that includes the $i$-th shareholder as a member. What exactly happens when two shareholders submit the same share of the secret depends on the implementation of the secret sharing scheme; all that can be said is that the secret will not be recreated.