Secret sharing scheme with possibility to change the secret Here's a scenario I want to handle with a secret sharing scheme:


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. 
Alice generates a parameter $P$ based on $S$ and publishes it. 
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$. 
Alice needs to change the secret. Alice recomputes only a new $P$. All private shares of the participants stay the same. 
Each of Bob, Charlie and Dave can reconstruct the new secret using the new public parameter $P$. 
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. 
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.
An obvious solution that handles steps 1&ndash;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.