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

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.

• Do you have an adversary model in mind? Aug 10, 2014 at 18:18
• Not really. But the adversary can only figure out who the people are and then try to find where they hid the key. Why? Aug 10, 2014 at 18:24
• How trustworthy are the parties who are given the shares? Aug 10, 2014 at 19:23
• The parties that I see often can be trusted to delete their own shares (and not compromising them). We can also, if necessary, assume that whenever a share is compromised, I know it. Aug 10, 2014 at 19:54
• Somewhat alike: Secret sharing scheme with possibility to change the secret Aug 15, 2014 at 2:29

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'$.

• I edited and added a lot of detail. I think that the trustworthy group of shareholders that accept to delete their shares makes it possible. Aug 10, 2014 at 20:42
• You second point about $x$ having to be private is really interesting (and really tricky). I never would've though about it (O_O) but I think the trustworthy group fixes that too. I'm not sure though. Anyway, I'm not going to make the $x$s public. But since I was thinking of only updating $y$ if a share was compromised, I'll probably have to rework my recovery protocol. I'll think about it and ask another question if I'm not sure :) Aug 10, 2014 at 20:49

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$.

• The problem is that decoding then takes 2 steps: Getting the old secret shifted by a constant and then unshifting by the constant. So that the person holding the constant is necessary, unless I'm mistaken. Feb 16, 2016 at 12:58
• @xavierm02 you can shift the constant without knowing it. When you add the keys, you add to polynomials. When you add the polynomials, you add the constants. Brilliant, ain't it? Feb 16, 2016 at 15:29
• Let's say we call $Q$ the original degree $k-1$ polynomial so that the secret is $Q(0)$ and the shares are $Q(i)$ for $1\le i \le n$. Then we generate your random polynomial $P$. The new shares are $Q(i)+P(i)$ and $P(0)$. If I have $k$ values of $Q+P$ and the value of $P(0)$, I can indeed get $Q(0)$ (assuming that $P$ is of degree $\le k-1$). But what if I have $k+1$ values of $Q+P$? All I can compute is $Q(0)+P(0)$. To get the secret, you need to have the new share: $Q(0)$. Feb 16, 2016 at 17:21
• @xavierm02 $P(0)$ is stored in the xoring scheme. You need the new agents to get it. Feb 16, 2016 at 17:27
• Precisely. $(k,n)$ means that any subset of size $k$ can have the secret. Let's say $n\ge k + 1$. Then your method doesn't give a $(k+1, n+1)$ because if you take a subset of size $k+1$ consisting of only people who already have shares, you can't find the secret. You give more importance to new shares, somehow. Feb 16, 2016 at 17:36