Secret sharing scheme with possibility to change the secret

Question

Here's a scenario I want to handle with a secret sharing scheme:

1. Alice wants to share the secret $S$ with Bob, Charlie and Dave. Alice generates private shares based on $S$ for Bob, Charlie and Dave, and communicates them to their intended recipients via a secure channel.
2. Alice generates a parameter $P$ based on $S$ and publishes it.
3. Each of Bob, Charlie and Dave can reconstruct the secret using $P$ and their personal share. Eve can't reconstruct it, even if she knows $P$.
4. Alice needs to change the secret. Alice recomputes only a new $P$. All private shares of the participants stay the same.
5. Each of Bob, Charlie and Dave can reconstruct the new secret using the new public parameter $P$.
6. Alice wants to add a new participant Fred and remove participant Bob from the group. Alice recomputes a new $P$ and a new private share for Fred.
7. Each of Charlie, Dave and Fred can reconstruct the secret using their shares and the new $P$. Bob can't reconstruct the secret using the new $P$.

Is there some secret sharing scheme that can handle such a scenario? I found myself some secret sharing schemes like Shamir's secret sharing or secret sharing using the Chinese remainder theorem, but those do no satisfy all my requirements.

Answer 1

Basically, use a bunch of independent one-time pads.

I will use array slicing, where array[x:y] returns the length y-x subarray
consisting of the entries from x inclusive to y exclusive.

k = computational_security_parameter
L = length_of_the_secret
n = number_of_changes_at_which_you_lose_information-theoretic_security
userinfo = [["Bob",Bob's_share],["Charlie",Charlie's_share],["Dave",Dave's_share]]

define makeparameterfor(m,userinfo,secret):
 P = [m]
 if m < n:
  for [name,share] in userinfo:
   append [name,(share[m*L:(m+1)*L] xor secret)] to P
 else:
  for [name,share] in userinfo:
   append [name,enc(share[n*L:(n*L)+k],secret)] to P
 return P

countervalue = 0

define generateparameter(userinfo,secret):
 return makeparameterfor(0,userinfo,newsecret)

define reconstruct(username,usershare,parameter):
 namefound = False
 for entry in parameter:
  if entry[0] == username and length(entry) != 1:
   [name,ctext] = entry
   namefound = True
  break
 if namefound == False:
  throwexception("invalid reconstruction attempt")
 else:
  cv = parameter[0]
  if cv < n:
   return ctext xor share[cv*L:(cv+1)*L]
  else:
   return dec(share[n*L:(n*L)+k],ctext)

define changesecret(userinfo,newsecret):
 countervalue = max(n,countervalue+1)
 return makeparameterfor(countervalue,userinfo,secret)

define addnewuser(oldparam,secret,name,share):
 append [name,share] to userinfo
 cv = oldparam[0]
 newP = oldparam
 if cv < n:
  append [name,(share[cv*L:(cv+1)*L] xor secret)] to newP
 else:
  append [name,enc(share[n*L:(n*L)+k],secret)] to newP
 return newP

define removeuser(username,oldparam):
 for [name,share] in userinfo:
  if name == username:
   remove [name,share] from userinfo
 newP = [oldparam[0]]
 for [name,ctext] in oldparam:
  if name != username:
   append [name,ctext] to newP
 return newP

Answer 2

An obvious solution that handles steps 1–5 (changing the secret) would be for Alice to generate a random encryption key $K$ (of, say, 128 bits), encrypt $S$ with $K$ to generate $P$, and then share $K$ with the other participants using a conventional secret sharing scheme such as Shamir's.

Indeed, if all the shareholders (other than Alice) are always needed to reconstruct the secret, you don't even need to use Shamir's scheme: trivial XOR secret sharing (where Alice gives all but one of the shareholders a random bitstring, and gives the last one the XOR of all the other shares plus the secret) will do the job just as well.

Indeed, with XOR secret sharing, steps 6 and 7 (adding and removing participants) can also be achieved: Alice simply sends random bitstrings to the new participants, computes a new key $K$ by XORing together the shares of all the active participants, and encrypts the secret $S$ with the new $K$ to obtain the new $P$.

In fact, if the key $K$ is (at least) as long as the secret $S$, you don't even really need a separate encryption step: as long as $K$ is random, you can simply XOR $K$ with $S$ to obtain $P$, making this an instance of one-time pad encryption.

This also works with Shamir's scheme, as long the reconstruction threshold equals the number of shareholders; Alice can just send random shares to all the shareholders, reconstruct a (random) key $K$ by applying Shamir's reconstruction algorithm to the shares of the active participants, and use that key to encrypt the secret.

However, note that all these protocols suffer from some fundamentally unavoidable flaws:

• if the shareholders can remember old $P$ values, they will be able to reconstruct old secrets even after Alice has changed them, and

• if removed shareholders can remember their old shares (and the old $P$), they can still reconstruct the secret (assuming the other old shareholders cooperate) as it was before they were removed. However, if the secret $S$ is changed whenever participants are removed, the remove participants won't be able to contribute anything useful to reconstructing the new secret.

---

Edit: Based on the comment below, it seems I misunderstood the question: you want each of Bob, Charlie and Dave alone to be able to reconstruct the secret using $P$.

A simple way to achieve this would be for Alice to distribute different random keys $K_i$ to each of the other participants $i$, encrypt her own key $K$ with each of $K_i$, and combine the ciphertexts into $P$.

Of course, the down side to this method is that the length of $P$ would be proportional to the number of participants, which could be a problem if that number is large. However, I'm not sure if it's possible to do any better, and I suspect it may not be.

Answer 3

I actually have a patent on a technique that can be used here -- or rather, I put in an application and then left that employer, and I don't know whether the patent issued; it seems based on this Google patents link that it's still an application, 12 years on.

Here's the idea. Shamir m-of-n secret sharing is a series of pairs $(x_i, y_i)$ such that

1. All pairs (x, y) satisfy Equation E: $a_m x^m + a_{m-1} x^{m-1} + ... + a_0 = y$
2. There are in total n pairs with n > m (obviously)

Now, say the x values are drawn from a series. Maybe $x_i = i$, or $3i$, or $i^2$. This series is a system parameter; all participants know it, and it doesn't matter if it's also known to non-participants.

Say also that m > n/2. This is a reasonable assumption as it means a majority of participants is required to recover the secret.

Say also that the secret is unstructured, such as a 128-bit random number. This is reasonable, you can do a lot of things with a 128-bit random number.

Say I get a group of $m$ people together to change the secret. These people are the participants, and I'll use "sharers" to mean everyone who knows a share. The first thing we do is work out the existing secret. The novel steps are:

1. As part of calculating the secret, we have calculated the coefficients of Equation E. That means that we know the shares of those sharers in the group who haven't participated in this transaction.
2. We calculate those shares. There are n-m < m of these.
3. We select (2m-n) of the participants in the current transaction and pick their new shares randomly. We now know (2m - n) + (n-m) = m shares of a new secret -- the shares of the non-participating sharers, which we've just calculated, and the shares of the (2m-n) participants, which we've just assigned randomly.
4. This is enough to calculated the new secret, so we calculate that secret and its equation E
5. We use the new equation E to calculate the shares of the other (n-m) participants.
6. All the participants store their newly calculated shares; the other sharers don't need to be notified.

This means that we've been able to update the shared secret without having to contact the other sharers and without them having to update their shares. Which is quite cute.

I don't know if this exactly meets your requirements. As other answerers have noted, if Alice is just worried about a series of pairwise relationships, she can do everything with XOR or similar. But this approach has a nice flexibility to it and I think works in the same trust model as standard secret sharing.

I'm not sure of the patent situation -- Baltimore were eventually bought by Verizon Business but I think this application lapsed. If you think this technique might be helpful to you, I'll reach out to find the owners and see if there's anything we can do to put it in the public domain.