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.