1
$\begingroup$

If I have $n$ secure assymetric encryption schemes, is their concatenation $Enc_{k_1,...,k_n}(m)=Enc_{k_1}(m)||...||Enc_{k_n}(m)$ secure?

My intuition is that the concatenation is secure, but I can't solve it by reduction, which gives me the feeling that maybe an attacker can somehow take advantage of the combination of the encryptions.

The main security definition I'm interested in is the following - an encryption scheme is secure if for all PPT $A$ and function that maps public keys to messages $f$, the probability of $A$ to guess a random bit $b$ chosen uniformly when it sees $p_k,f(p_k)=(m_0,m_1),Enc_{pk}(m_b)$ is at most $\frac{1}{2}+negl(n)$, where the probability is over the coin tosses of $A$ and the public key $p_k$ generation.

$\endgroup$
14
  • $\begingroup$ This is an easy question if you consider how strong a chain... $\endgroup$
    – kelalaka
    Commented Mar 17 at 21:14
  • $\begingroup$ @MaartenBodewes-modelection - thanks for your comment. This is non an homework question, that's a question I thought about and couldn't solve. I didn't think my thoughts about it are so helpful, so I just posted the question. I also think that the existence of this question with answer in this site would help others. Anyway, I edited the question to include some of my thoughts. $\endgroup$ Commented Mar 18 at 6:30
  • $\begingroup$ @kelalaka - What do you mean by chain? And what is its strength? $\endgroup$ Commented Mar 18 at 6:31
  • 1
    $\begingroup$ That depends entirely on the definition of security. $\endgroup$
    – Maeher
    Commented Mar 18 at 6:42
  • $\begingroup$ @Maeher - Can you elaborate? I also added security definition. $\endgroup$ Commented Mar 18 at 6:48

1 Answer 1

1
$\begingroup$

Yes, generally the encryption with separate unrelated public keys of a plaintext message is considered secure. This is true even if you use the same scheme, but it is fine to choose other secure schemes.

If you combine these encryptions by concatenation then that's fine of course, assuming that you're able to deconstruct the result back into the separate encrypted values. This can usually be performed as the ciphertext size of each separate algorithm can be calculated as a function over the key size.

Consider the following proof by contradiction: if an adversary would receive $\text{Enc}_{k_1}(m)$. Then the adversary would be able to try and guess $m$ and construct $\text{Enc}_{k_1,...,k_n}(m)=\text{Enc}_{k_1}(m)||...||\text{Enc}_{k_n}(m)$ using the public keys of locally generated key pairs. If that would leak any information then the initial cipher would not be IND-CPA secure. This in turn would mean that no public key encryption schemes would be secure.

Note that indistinguishability is performed over the output domain of the cipher used. For asymmetric ciphers this is commonly a group, where the group size is not a two-exponent. This in turn means that at least the most significant bit of operations on a finite field has a skew to zero. As most ciphertext are in bytes, the topmost bits may actually always be zero. Similar issues may exist with the least significant bits (etc.). So the test you are proposing does generally not work for asymmetric ciphers.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer! Can you clarify your proof? You try to prove that if all n schemes are secure, also their concatenation is secure, right? If I understood correctly you go from the contra positive - you assume that the concatenation is not secure and show it implies that one of the encryptions is not secure, right? If this is the case, how do you know the adversary will be able to find m? From what I see it is not part of the assumption. $\endgroup$ Commented Mar 20 at 16:19
  • $\begingroup$ For CPA security the attacker controls the message. For all intents and purposes, the message could be a simple 0 or 1 so they would guess right by having two guesses. Even if the message is just one bit the attacker should not gain any information about the message, i.e. they should not know if they've guessed right. $\endgroup$
    – Maarten Bodewes
    Commented Mar 20 at 17:55
  • $\begingroup$ The main point is simply that if the attacker could break the encryption by encrypting a message using a different cipher or key pair (under their control) that all asymmetric encryption is broken by definition. Encrypting a message using a key pair that they don't own is a weaker premise as now they don't control the private key. And since concatenation doesn't weaken the ciphers either the only possible outcome is that it must be secure. This is a bit of a tricky proof as it completely disregards the algorithms themselves and it only works if the ciphers are known secure. $\endgroup$
    – Maarten Bodewes
    Commented Mar 20 at 17:57
  • $\begingroup$ It's not so much as a proof in itself. It is more a statement that if such a thing was possible then the algorithms would never be considered secure. $\endgroup$
    – Maarten Bodewes
    Commented Mar 20 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.