Changing encryption key without revealing the original key

Question

Say that Alice encrypts a $\text{plaintext}$ with $\text{key}_{m}$ and gives the $\text{ciphertext}_m$ to Bob. Alice wants to send several gigabytes of $\text{plaintext}$ to Eve but she is on a mobile 3G connection. So instead, Alice and Eve exchange a new secret $\text{key}_{eve}$. She then creates a $\text{key}_{mutate} = \operatorname{Keymutate}(\text{key}_m, \text{key}_{eve})$ and sends it Bob where he applies a mutation function to produce $\text{ciphertext}_{eve} = \operatorname{Mutate}(\text{ciphertext}_m, \text{key}_{mutate})$. Bob sends the $\text{ciphertext}_{eve}$ to Eve and she produces the $\text{plaintext} = \operatorname{Decrypt}(\text{ciphertext}_{eve}, \text{key}_{eve})$.

This seems like a homomorphic encryption cryptosystem, does something like this possible or even implemented?

Answer 1

As CodesInChaos already answered in the comments, this seems to be a perfect fit for proxy re-encryption (PRE). The basic idea of PRE is that a ciphertext encrypted under the public key of user $A$ can be transformed (i.e., re-encrypted) into a ciphertext decryptable by the private key of user $B$; the re-encryption process does not reveal any information about the underlying message.

Note then that proxy re-encryption is a type of public-key encryption. Therefore, users in your scenario should have pairs of public and private keys. Proxy re-encryption schemes come in all flavors (unidirectional vs. bidirectional, single-use vs. multi-use, interactive vs. non-interactive, etc.). Depending on your scenario, you would choose one or another.

However, from your question, one could think that users were using symmetric encryption. In case you were asking for the symmetric counterpart of PRE, then this can be constructed using other mechanisms, such as Key-Homomorphic Pseudo-Random Functions.