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


  • $\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.

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


Your Answer

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