For the sake of readability we adjust the notation somewhat.
Let $\Pi=(Gen,Enc,Dec)$ be a $\mathsf{CPA}$-secure public-key encryption scheme with message space $\mathcal{M}$. We wish to prove that $\Pi^2=(Gen^2,Enc^2,Dec^2)$, with message space $\mathcal{M}\times\mathcal{M}$ is also $\mathsf{CPA}$-secure, where
$\underline{(pk,sk)\gets Gen^2(1^n)}$:
- $(pk_\alpha,sk_\alpha)\gets Gen(1^n)$
- $(pk_\beta,sk_\beta)\gets Gen(1^n)$
- $(pk,sk):= \big((pk_\alpha,pk_\beta),(sk_\alpha,sk_\beta)\big)$
$\underline{c\gets Enc^2(pk,m)}$:
- $(pk_\alpha,pk_\beta) := pk$
- $(m_\alpha,m_\beta) := m$
- $c_\alpha \gets Enc(pk_\alpha,m_\alpha)$
- $c_\beta \gets Enc(pk_b,m_\beta)$
- $c:=(c_\alpha,c_\beta)$
$\underline{m := Dec^2(sk,c)}$:
- $(sk_\alpha,sk_\beta) := sk$
- $(c_\alpha,c_\beta) := c$
- $m_\alpha := Dec(sk_\alpha, c_\alpha)$
- $m_\beta := Dec(sk_\beta, c_\beta)$
- $m := (m_\alpha,m_\beta)$.
We can prove the following claim by proving the contrapositive, i.e
$\underline{Claim:}$
\begin{align*}
&\Pi\text{ is $\mathsf{CPA}$-secure}\implies\Pi^2\text{ is $\mathsf{CPA}$-secure} \\
\iff &\Pi^2\text{ is $\lnot\mathsf{CPA}$-secure}\implies\Pi\text{ is $\lnot\mathsf{CPA}$-secure}.
\end{align*}
$\underline{Proof:}$
To prove the contrapositive, we assume there exists an adversary $\mathcal{A}^2$ against $\Pi^2$, such that $$\Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A}^2,\Pi^2}(n)=1]>\frac{1}{2}+\mathsf{negl}(n).$$
In other words, $\mathcal{A}^2$ can win against $\Pi^2$ in the $\mathsf{CPA}$ game with non-negligible advantage.
We will now use $\mathcal{A}^2$ to construct an adversary $\mathcal{A}$ against $\Pi$ in the $\mathsf{CPA}$ game.
The $\mathsf{CPA}$ game proceeds as follows:
- $Gen(1^n)$ is run to obtain keys $(pk_\alpha, sk_\alpha)$.
- Adversary $\mathcal{A}$ is given $pk_\alpha$ as well as oracle access to $Enc(pk_\alpha,\cdot)$. Next, $\mathcal{A}$ runs $Gen(1^n)$ to obtain $(pk_\beta, sk_\beta)$.
- Adversary $\mathcal{A}^2$ is given $pk:=(pk_\alpha,pk_\beta)$ as well as oracle access to $Enc^2(pk,\cdot)$.
- $\mathcal{A}^2$ outputs a pair of distinct messages $m_0:=(m_{0_\alpha},m_{0_\beta}), m_1:=(m_{1_\alpha},m_{1_\beta}) \in\mathcal{M}\times\mathcal{M}$ with $m_{0_\beta} = m_{1_\beta}$ and $|m_0|=|m_1|$. In other words, the messages $m_0$, $m_1$ are different, but the second half is the same.
- After receiving $m_0$ and $m_1$ from $\mathcal{A}^2$, the adversary $\mathcal{A}$ forwards only the first parts $m_{0_\alpha}$,$m_{1_\alpha}$ to the $\mathsf{CPA}$ game.
- The game chooses a random bit $b \in \{0, 1\}$, and the challenge ciphertext $c_\alpha \gets Enc(pk_\alpha, m_{b_\alpha})$ is computed and given to $\mathcal{A}$. $\mathcal{A}$ continues to have access to $Enc(pk_\alpha,\cdot)$.
- Now $\mathcal{A}$ computes the second half of the challenge ciphertext as $c_\beta \gets Enc(pk_\beta, m_{0_\beta}=m_{1_\beta})$. Note that $\mathcal{A}$ doesn't need to know the challenge bit $b$. Then, $\mathcal{A}$ sends the challenge ciphertext \begin{align*} c&:=(c_\alpha,c_\beta)\\&:=\big(Enc(pk_\alpha, m_{b_\alpha}),Enc(pk_\beta, m_{0_\beta}=m_{1_\beta})\big)\end{align*} to $\mathcal{A}^2$. $\mathcal{A}^2$ continues to have access to $Enc^2(pk,\cdot)$.
- $\mathcal{A}^2$ returns a guess bit $b''$ to $\mathcal{A}$.
- $\mathcal{A}$ sets its own guess bit $b':=b''$, and returns $b'$ to the $\mathsf{CPA}$ game.
- The output of the game is defined to be $1$ if $b'= b$, and $0$ otherwise.
From the reduction it follows that, \begin{align*} \Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A},\Pi}(n)=1]&=\Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A}^2,\Pi^2}(n)=1] \\&>\frac{1}{2}+\mathsf{negl}(n). \end{align*}
Here, the last inequality follows from our assumptions that $\mathcal{A}^2$ can win against $\Pi^2$ in the $\mathsf{CPA}$ game with non-negligible advantage.
Finally, this proves the initial claim that $\Pi\text{ is $\mathsf{CPA}$-secure}\implies\Pi^2\text{ is $\mathsf{CPA}$-secure}$. $\;\blacksquare$
