does re-encrypting the same value with multiple keys reduce security I found myself wondering today, how much security is lost if you take a plaintext - assume that its content, including any metadata is unknown to an attacker, for example it may be random data - and encrypt it with multiple keys (not chained) and give all resulting ciphertexts to an attacker, how much higher is the probability of an attacker discovering the plaintext, vs only having a single ciphertext. 

An example:

Take plaintext $P_1$ and encrypt it with $K_1$, and send the resulting ciphertext $C_1$ to attacker $A_1$.

In addition: take the same plaintext $P_1$ and, and encrypt it with $K_1$, giving $C_1$. Then take $P_1$ and encrypt it with $K_2$ giving $C_2$, then $K_n$ giving $C_n$ and send all $n$ ciphertexts to attacker $A_2$.

How much more likely is attacker $A_2$ to discover the value of $P_1$, than $A_1$?
Does re-encrypting the same value with multiple keys reduce security?


The answer is "it depends"; there are some attack models and encryption methods where the security is reduced, there are other cases where there appears to be no security reduction.

Let us go through some models where we actually see a security reduction:

Plaintext guessing attack and deterministic encryption


In this attack model, the attacker has a guess to the plaintext $P_{guess}$ and wants to confirm whether $P_1 \stackrel{?}{=} P_{guess}$.  What he can do is guess random keys $K_{guess}$ and compute $E_{K_{guess}}(P_{guess})$ and he if that appears in one of the ciphertexts he's been given.  If he happens to guess a key $K_i$, then ciphertext $C_i$ will match, and he will get confirmation that his guess is likely to be correct - that's because we assume that the encryption is deterministic and so if the keys and the plaintext match, the ciphertext will as well.  Obviously, using more keys means that there are more targets the attacker can stumble into.

Deterministic stream ciphers, and plaintext with known linear relations.


Here, we assume we don't know the plaintext, however we do know certain linear relations between the bits of the plaintext; for example, we may know that the parity of each byte is even.  We also assume that the cipher works by generating a keystream (as a function of the key), and then exclusive-or the keystream with the plaintext to form the ciphertext.

So, what the attacker can do is examine each ciphertext; by assuming that the linear relationships hold in the original plaintext, he can evaluate the corresponding linear functions on the keystream; in the example, he can compute the parity of each byte of the keystream.

Then, he can pick random keys, and generate the corresponding keystream (here, we assume that this is determanistic).  Then, he can compute the linear function of that keystream (in the example, the parity of each byte), and see if it matches one of the keystreams that correspond to the known ciphertexts.

Like the first example, having more targets makes it more likely that the attacker will guess the correct key.

(Also, if you think that the example of "parity of each byte is even" is contrived, a more realistic example is "the msbit of each byte is 0").

Deterministic RSA encryption


If the encrypt the exact same message (without padding, or using determanistic padding) to $n$ different keys, and $n \ge e$ (where $e$ is the common public exponent), then it's easy to recover the message.  This is typically used as an example why you need to add randomness to your RSA encryption, even if you don't care about plaintext guessing attacks.



The above are three examples where encrypting with multiple keys can reduce security; in other cases (such as CBC-mode encryption), there is no obvious way to use multiple ciphertexts.

Now, the obvious thing about all three examples are that they are deterministic encryption; it would appear to be wise to add randomness if you are encrypting with multiple keys.