2
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so what do I need to add new share? Do I need k shares to reconstruct S and then I am able to add new share? $\endgroup$ – user1563721 Jul 7 '16 at 7:21
  • 2
    $\begingroup$ You do the same you did to generate any other share. No matter how many new shares you add, you still need $k$ shares to reconstruct $S$. $\endgroup$ – cygnusv Jul 7 '16 at 7:55
  • $\begingroup$ All implementations I know works with number of share and share as input in order to reconstruct S. If I generate 4 shares in 2 of 4 scheme with S and then do the same, I have 8 shares but I am not able to combine any 2 of them to get S back because of share index number is always from 1 to 4. The input to reconstruct S is in this case at least two shares in form (index number, share). When I take one from first generation and one from second generation I will get different result. There is something I am missing... I use timtiemens/secretshare Java library $\endgroup$ – user1563721 Jul 7 '16 at 8:33
  • 4
    $\begingroup$ That's a problem of the implementation, not of Shamir's Secret Sharing scheme. $\endgroup$ – cygnusv Jul 7 '16 at 8:45
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That is a good point. I assume that I am not able to get all shares to generate new unique share. What is the best practice in this manner? Generate number of shares that I know that I will need and never more? Or precompute and secure somehow shares that are not used and assign shares in future? $\endgroup$ – user1563721 Jul 10 '16 at 5:19
  • $\begingroup$ @user1563721: In many applications of Shamir's secret sharing, it is assumed that the $x$ components of the shares are public (since, after all, they can be). If they're not, the simplest solution is probably to work in a reasonably large field, like $GF(2^{256})$, and just assign the $x$ components at random. For $n$ participants over $GF(p^m)$, the probability of getting a collision between random $x$ coordinates is less than $(n^2-n)/(2p^m-2)$, so as long as you keep $n^2$ well below the field size $p^m$, you should be fine. $\endgroup$ – Ilmari Karonen Dec 21 '16 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.