$(k, n)$ threshold secret sharing to $(k+k', n + n')$ without reissuing all shares

Question

Given a $(k,n)$ threshold secret sharing used to back up a secret (meaning that the dealer has access to the secret at all times), is it possible to update it to a $(k+k', n+n')$ threshold secret sharing without reissuing all shares (in fact, the fewer have to be reissued, the better).

Obviously, if $k' = 0$, He just has to issue $n'$ new shares.

Also, the number of shares that aren't updated has to be $<k$ because $k$ non-updated shares allow to get the secret. So you have to update at least $n-k+1$ old shares.

---

My use case is that I want to back up an encryption key by giving shares to several people. But since I want to give them shares on paper and in person, I can't give them all at once. If I fix $k$, my backup is unreliable until I give at least $k$ shares. So I'd prefer to be able to start with a small $k$ and then, once I give new shares, update the shares of a few people that I see more often to increase $k$.

Added to further specify the problem:

• The secret is a (randomly generated) keyfile used for cryptsetup. This means that it isn't the actual encryption key: it's a key with which the encryption key is encrypted. So I have the secret available at all times (and so can easily issue new shares) and can also reset the secret at any time if needed (for example if shares are compromised). But that's inconvenient because I want to distribute new shares and:

• I want to distribute shares in person (because most people's computers are so easy to get into that I consider anything on it as public).

• Because I give shares in person, I can't give all shares at once. I would therefore prefer to be able to start with small $k$ and $n$ and then increase them. I would give the first shares to people I see often (and that are trustworthy). Then, when given the opportunity, I would generate an update (meaning, new shares for new shareholders and a few old shareholders). The old shareholders would be chosen among the people I see the more often and I trust the more. I would then distribute then new shares to new shareholders and once this is done, I would give their new shares to the old shareholders and ask them to destruct their old shares. So an update would actually be in two steps: first, distribute shares to new shareholders (which are, at that time, completely useless) and then, change the shares of a few old shareholders ("activating" the shares of the new shareholders and increasing $n$).

• Sareholders are of three types: trustworthy, trustworthy-ish and trustworthy-ish-ish. All shareholders can be trusted to give back the shares when asked. trustworthy-ish-ish shareholders can not be trusted for anything else and will only be here to make getting the secret harder. I will consider a $(k,n)$ threshold with $t$ trustworthy-ish-ish shareholders as a $(k-t, n-t)$ one. In other words, their shares can be considered public but they make adversaries work a bit harder to actually get the secret. trustworthy-ish shareholders can be truster to tell me when their shares are compromised and not vonluratily compromise them. trustworthy shareholders can be trusted to do anything a trustworthy-ish can be trusted to do and can also be trusted to destroy their shares when asked to. There will be at least $n - k + 1$ trustworthy shareholders at all time (because that's the number of existing shares I know I need to update to issue new shares without reissuing all shares). Note: You can assume that I see trustworthy shareholders often.

• I don't want to use multi-level secret sharing because subshares have less importance than original shares so doing that, I would either just issue a new share and split it (in which case I have increased $n$ without being able to increase $k$ which is something that I most likely don't want to do) or take the share of a trustworthy shareholder, split it and give him back a subshare (in which case, I've disminished the importance on one of the shareholders I trust the most). Another problem is that I would need to keep a map of which share goes with which share. If that map is with my keyfile, then when I lose the keyfile, I also lose the knowledge of how to combine shares to recover it. If the map is somewhere else, it leaks information to adversaries: the identities of the shareholders which are part of the secret protecting shares (the other part being where the shareholders hid the shares). I could also give this map to a special shareholder but I would have to interact with him every time I distribute a share and if he got compromised, we would get back to the previous problem.

Answer 1

Well, first off, unless the updated shares hid a different secret, the problem is impossible (unless $k' = 0$, or you haven't distributed $k$ of the old shares). That's because, since at least $k$ people have the old shares, they can get together and ignore the new shares; instead, they use their old shares to construct the secret.

If you need the new secret be the same as the old, well, we can stop right here.

And, even if you did assume the new shares hid a different secret, if we don't update all the shares, we would need to assume that the $x$ value that we assign in each share must be secret (that is, part of their share, and not a publicly known value; generally in Shamir secret sharing, that can be known publicly). That's because $k$ holders of the old secret can reconstruct the entire old polynomial (and not just the old shared secret); if they knew anyone else's $x$ value, they could reconstruct their old share (and if that share wasn't updated, that'd give them a share in the new system they weren't supposed to have).

Now, given the above, the obvious solution would appear to mostly work in your scenario; the dealer picks a random degree $k-1$ polynomial, assigns $n$ different $x$-coordinates to the $n$ initial shares, and distributes those shares to the $n$ different share holders (and record those shares). Then, when it comes time to redeal, you pick $k'+k-1$ share holders and a random new secret, and compute the degree $k+k'-1$ polynomial that goes though those $k'+k-1$ points and has the new constant term, select new $x$-coordinates for the new (updated) shares, compute the share values, and distribute those to the $n+n'-(k+k'-1)$ members that can't reuse their old shares. Now, I don't believe that this scheme will give the same level of security as a pure secret sharing method (as I believe that some groups smaller than $k+k'$ will be able to deduce values of the shared secret which is impossible), however if what we're sharing is an encryption key, the ability to deduce that a handful of values are impossible is not a realistic concern.

However, a more simplistic approach would be to simply run multiple secret sharing schemes simultanously, at different levels of $k$. Each share would include the share for each scheme (at least, the schemes which are still active when the share is issued). When it comes time to increase $k$, all we need to do is tell everyone that the 'current' secret isn't the old one being shared with that level of $k$, instead they need to use the secret hidden by the level $k + k'$.

Answer 2

Here is a method, although it involves both shamir's scheme and XORING, and can only update $(k,n)$ to $(k+t,n+t)$ (but can do so repeatly).

There are exactly two sets of agents: original and new. The original agents share a secret $X$ with shamir secret sharing, and the new agents each have a field element, such that $X$ added (which usually means XORED) to all the new agents field elements are $S$.

To start, the original agents share $S$, and there are no new agents.

To add a new new agent, generate a random polynomial $p(x)$. $C$ is the constant term of this polynomial (and is therefore also random). Instruct each original agent to add $p(a_x)$ to his share, where $a_x$ is the agent's public x coordinate. Then give $-C$ (which is just $C$ is a field of characteristic 2) to the new agent.

After adding a new agent, the shamir secret sharing scheme will be storing $X+C$, and the new agent will have $-C$. Adding $X+C$ to the new new agent gives $X$, and adding $X$ to all the old new agents gives $S$.