# $(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? –  mikeazo Aug 10 '14 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? –  xavierm02 Aug 10 '14 at 18:24
How trustworthy are the parties who are given the shares? –  mikeazo Aug 10 '14 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. –  xavierm02 Aug 10 '14 at 19:54
Somewhat alike: Secret sharing scheme with possibility to change the secret –  e-sushi Aug 15 '14 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. –  xavierm02 Aug 10 '14 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 :) –  xavierm02 Aug 10 '14 at 20:49