# Is using a CPA secure public key encryption twice on two halves of the message with different keys secure?

If $$\Pi=(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$$ is a CPA secure public key encryption protocol, is the following public key encryption CPA secure?

$$\Pi'$$:

• $$\mathrm{Gen'}$$: Run $$\mathrm{Gen}$$ twice to get keys $$\langle pk_1,sk_1\rangle$$ and $$\langle pk_2,sk_2\rangle$$.
• $$\mathrm{Enc'}$$: Take $$pk=\langle pk_1,pk_2\rangle$$. On message $$m=\langle m_1,m_2\rangle$$, compute $$c_1=\mathrm{Enc}_{pk_1}(m_1),\ c_2=\mathrm{Enc}_{pk_2}(m_2)$$. Output $$c=\langle c_1,c_2\rangle$$.
• $$\mathrm{Dec'}$$: Take $$sk=\langle sk_1,sk_2\rangle$$ and the ciphertext $$c=\langle c_1,c_2\rangle$$. Compute $$m_1=\mathrm{Dec}_{sk_1}(c_1),\ m_2=\mathrm{Dec}_{sk_2}(c_2)$$. Output $$m'=\langle m_1',m_2'\rangle$$.

Intuitively I think that this is secure because using a secure protocol twice with different keys at different times is of course secure. However I cannot find a reduction.

The main problem I face is that if I reduce an adversary $$A$$ of $$\Pi$$ to an adversary $$A'$$ of $$\Pi'$$, then $$A$$ can only send out the first halves of the two messages given by $$A'$$ to the challenger. $$A$$ has to encrypt the second half by itself (or, use oracle) to give back to $$A'$$. However, $$A$$ does not know the second half of which message it should encrypt and give to $$A'$$, because $$A$$ does not know the random bit $$b$$ chosen by the challenger, thus not know the first half of which message is encrypted by the challenger, but the two halves given to $$A'$$ must match.

• This is a classical application for a hybrid argument. Nov 9 at 7:54
• @Maeher I do not really understand. Could you please explain in more detail? Nov 9 at 13:56