Can I encrypt data with multiple keys and decrypt with one? [closed]

Question

Can I encrypt data with multiple keys and decrypt with one? To be clear, I am not saying encrypt a file, decrypt it, then encrypt it again with a different key. I want to encrypt it, then encrypt it again, then again, maybe even again. I want to know whether I can use only one key to decrypt. The key can change though, it doesn't have to be the same key (in fact it shouldn't be).

I need a smart way to update the key to the new key, depending on how many times the data was encrypted. Also, the only way to get the new key is to have the old key... Is this possible? Is there an encryption algorithm that can be stacked multiple times and be decrypted by one key (and can I create that key)? Either this can already be done, or I am crazy--remember, I'm new to this...

---

Previously handled comments on StackOverflow:

"What's the point of encrypting multiple times? Properly encrypted data is indistinguishable from random noise."

I'm not trying to make it more secure by doing this...

"Do you want to perform E(k_n, msg) once with one of many possible keys then E(k_d,ciphertext) to get the ciphertext? Or do you want to perform E(k_1, E(k2, ... E(k_n,msg) ... ) ) as the encryption?

The latter, except I don't want to do encrypt with all keys all at once. I want E(k_1, msg) ... some time ... E(k_2, encrypted_msg) ... and so on, but I want to know if I can decrypt with one key after however many encryptions (and how to get that key).

"Consider: 'I really want a smart way to update the key to the new key'."

Yes. And, of course, the encrypted file will change during the process.

Answer 1

Maybe this schema will suit your needs, even though it is not exactly what you asked:

Encrypt your plaintext $M$ with a symmetric key $K$, producing $\{M\}_K$. Then encrypt $K$ with $K_1$. Store $\{K\}_{K_1}||\{M\}_K$ (with $||$ being the concatenation operator).

Then, when you want to update your encryption key with $K_2$: Decrypt $\{K\}_{K_1}$ and encrypt it with $K_2$ (you will need to know $K_1$ and $K_2$ for this step). Update the header of the stored file by overwriting it with the new value, obtaining $\{K\}_{K_2}||\{M\}_K$.

Repeat as many times as you wish, obtaining $\{K\}_{K_n}||\{M\}_K$. At each encryption step $n$, you will need the previous key $K_{n-1}$ and the key $K_n$. You never have to decrypt $\{M\}_K$.

Answer 2

Here is a candidate system, based on an ordinary message cipher $\mathcal E_\kappa(p)$ and $\mathcal D_\kappa(c)$ so that $\mathcal D_\kappa(\mathcal E_\kappa(p)) = p$ and $\mathcal E_\kappa(p)$ is indistinguishable from uniform random noise to anyone who doesn't know $\kappa$.

Let $k_i$ be the $i^\mathit{th}$ encryption key, let ${E^i}_{k_i}(x)$ be the $i^\mathit{th}$ encryption function, let $k$ be the decryption key, and let $D_k(x)$ be the decryption function. We want to define $E^i$ and $D$ so that $$D_k({E^{n-1}}_{k_{n-1}}(\cdots({E^1}_{k_1}({E^0}_{k_0}(x)))\cdots) = x,$$ but otherwise we want all the intermediate ciphertexts, ${E^i}_{k_i}(\cdots({E^0}_{k_0}(x))\cdots)$, to be indistinguishable from uniform random noise to an adversary who does not know $k$ or the $k_i$.

To this end, define

\begin{align*} {E^0}_{k_0}(x) &= \mathcal E_{k_0}(x), \\ {E^i}_{k_i}(x) &= x, &&\text{for $i > 0$.} \end{align*}

Decryption is easy: the decryption key is simply $k_0$, and $D_k(x) = \mathcal D_k(x)$.

---

If this doesn't satisfy your needs, you will need to be more specific about what your needs are so that they meaningfully exclude this system. ‘Meaningfully exclude’ implies that you have to give some reason related to your application why this won't work, rather than just say you don't like it and the $E^i$ functions have to actually do something.

In particular, it will be helpful for you to identify who changes the key and why. Are you the sender and recipient, and are you changing your password because it got compromised and surgically removing all traces of the previous key derived from it and ciphertexts encrypted with it from all storage systems everywhere? Are there multiple parties involved, like members of an organization who have split administrative functions to avoid unilateral power to doctor records? What are you or they all trying to accomplish? What is the adversary you hypothesize able to do to manipulate the resources they are trying to accomplish it with? What do you want to make sure the adversary can't do?

Answer 3

I'm not sure I understand the question correctly. Assuming you want multiple encryption and decryption keys: Could you not just make multiple ciphertexts that are each encrypted with a different key?

If the problem is that the ciphertext is large, and you don't want multiple large ciphertexts, then you could generate a new "envelope" key, encrypt the message with the envelope key, and then make multiple ciphertexts of the envelope key encrypted with different keys. The envelope-key ciphertexts can be bundled with the main ciphertext. Then with any of those keys, the user could decrypt the envelope key, and then decrypt the main message.

I believe this is what GPG actually does internally if you encrypt a file with multiple symmetric or asymmetric keys.

This also allows you to update the main-message decryption key: you can take the main ciphertext with the previous envelope-key ciphertexts stripped off, generate new keys, encrypt the envelope key with the new keys, and then bundle the main ciphertext with the new envelope-key ciphertexts.

Answer 4

You could do this with one-time pads. Simply XOR the new pad into both the ciphertext and the decryption key each time.