0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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$
    – Kagura Hitoha
    Nov 9 at 13:56

0

Reset to default

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.