# Is there a way to use Shamir Secret Sharing with updatable data?

I want to divide a system that maintains these properties, based on Shamir's Secret Sharing:

1. A secret key is split up to N pieces, where T of them are enough to reconstruct the key.
2. The original key is then destroyed and doesn't exist anywhere except the N separate pieces.
3. The information unlocked by the T signatures is updatable - I want to retain some other information that will allow me to update the secret that is accessible by the secret holders.

The use case is a will that contains secret information. I have N people I trust, and I want any group of T of them to be able to read the secret information (hopefully, only after I'm dead). I want to be able to update this secret information from time to time, without the bother of recreating and redistributing another set of keys.

Is there something that answers these requirements?

-
How about simply using asymmetric encryption where you retain the public key, and secret share the private key? –  CodesInChaos Mar 8 '13 at 14:17
@CodesInChaos - Hmm, close but no cigar. I need to be able to update the data, which means Read it, Change it, and Save it. I can't read it without retaining the private key. –  ripper234 Mar 9 '13 at 11:45
Then why don't you retain the private key, without giving it to the other parties? If you want to be able to read the data without consulting the other parties, then you need to do something that's equivalent to retaining the key. –  CodesInChaos Mar 9 '13 at 11:51
@CodesInChaos - see my answer - crypto.stackexchange.com/a/6644/340 –  ripper234 Mar 9 '13 at 11:52
I don't want to retain the key in unencrypted form, but I can (hopefully) retain it in my memory. –  ripper234 Mar 9 '13 at 11:52

I think there's a better way to do this, and I'm not sure the existing answers check all your boxes. I suggest using secret splitting together with asymmetric keys so that:

• Nobody but you can write data.
• Shareholders can come together to read data.
• Each shareholder can individually verify, but not read data.
• You can read and write data at any time.

Here's how I'd do it:

1. Create asymmetric (e.g. RSA) key pair "A".
2. Split the private half of A into $s$ shares, where $s=nx+t$.
3. Keep $t$ shares for yourself.
4. Create asymmetric key pair "B".
5. Give $x$ shares in A and the public half of B to each trusted person.
6. Secure the public half of A and the private half of B and keep them to yourself.
7. Create your data, encrypt it using the public half of A, then sign it using the private half of B. Distribute the signed, encrypted data.

Each shareholder can use the public half of B to verify the encrypted data; they may do this alone and at any time. Shareholders may combine their shares to recover the private half of A, which can then decrypt the data.

You, may at any time, use your shares to recover the private half of A and read the data. Also at any time, and as often as you wish, you may create new and/or additional data, encrypt and sign it, and distribute to your trusted people.

-
Nice improvements, thanks! –  ripper234 Apr 17 '13 at 6:17

I think this answers most of the requirements, even if not to the letter - but rather the practical use case:

1. I choose and remember a secret key
2. The key is split according to Shamir Secret Sharing
3. I then destroy the original key from my computer (but not from my memory)
4. I publish a file locked by this key
5. Whenever I need to, I encrypt an publish a new file
6. If I happen to forget the key, I collect the split parts or just recreate a new secret key from zero.

This system relies on me remembering the key for the sake of updates, but can recover if I forget it.

-

If you don't update the shares, then any $T$ share holders will be able to reconstruct only the original secret $S_{\scriptstyle{\text{old}}}$, and not the updated version $S_{\scriptstyle{\text{new}}}$. Instead of providing all the $N$ share holders with new shares to use in the reconstruction process you could consider informing all $N$ to simply XOR $S_{\scriptstyle{\text{old}}}\oplus S_{\scriptstyle{\text{new}}}$ into the secret (still $S_{\scriptstyle{\text{old}}}$) after it has been reconstructed. Of course, this is not all that different from simply sending everyone a new share, and both scenarios are fraught with the possibilities of screw-ups due to human nature and behavior that you will be unable to rectify from beyond the grave. In the first scenario, some share holders might not discard the old shares at all, and when $T$ share holders get together to reconstruct the secret, some of them may inadvertently (or possibly advertently!) submit the old shares while others submit the new shares with the result that neither version of the secret is recoverable. In the second scenario, some share holders might not remember the additional instruction to XOR $S_{\scriptstyle{\text{old}}}\oplus S_{\scriptstyle{\text{new}}}$ into the secret after reconstruction so that some share holders will correctly have $S_{\scriptstyle{\text{old}}}\oplus (S_{\scriptstyle{\text{old}}}\oplus S_{\scriptstyle{\text{new}}}) = S_{\scriptstyle{\text{new}}}$ in front of them while the amnesiacs will have the just-reconstructed $S_{\scriptstyle{\text{old}}}$ to work from.

-