Proof that secret sharing based scheme is CPA secure as long as one of the scheme is CPA secure

Question

I want to construct a CPA-secure scheme using two given schemes $\prod_1$ and $\prod_2$ if only one of them is CPA secure.

Taking suggestions from this answer, I am able to construct a scheme as follows.

Given a message $m$, Generate a random string $r$, of same length as $m$.

Compute $r_2 = r \oplus m$

Encrypt $r$ using $\prod_1$ to get $c_1$ and $r_2$ using $\prod_2$ to get $c_2$.

Send both $c_1$ and $c_2$.

The scheme must be CPA secure because both of the ciphertexts need to be decrypted to get back the message.

However, I am not able to prove that the resultant scheme is CPA secure other than intuition.

How do I prove it rigorously?

Answer 1

Let us denote the above scheme as $\prod = (Gen, Enc, Dec)$ and formally define it by considering $\prod_1 = (Gen_1, Enc_1, Dec_1)$ and $\prod_2 = (Gen_2, Enc_2, Dec_2)$.

$Gen(1^{\lambda})$ runs $(pk_1, sk_1) \leftarrow Gen_1(1^{\lambda})$ and $(pk_2, sk_2) \leftarrow Gen_2(1^{\lambda})$ and outputs the public key $pk = (pk_1, pk_2)$ and secret key $sk = (sk_1, sk_2)$.

$Enc(pk, m)$ randomly generates $r$ and computes $c_1 \leftarrow Enc_1(pk_1, m \oplus r)$ and $c_2 \leftarrow Enc_2(pk_2, r)$. It outputs $(c_1, c_2)$ as the ciphertext.

$Dec(sk, (c_1, c_2))$ computes $r' \leftarrow Dec_1(sk_1, c_1)$ and $r \leftarrow Dec_2(sk_2, c_2)$. It outputs $r' \oplus r$.

We will show that if there is an adversary $\mathcal{A}$ that breaks the CPA-security of $\prod$, then we can build an adversary $\mathcal{B}$ that breaks the CPA-security of $\prod_1$. Let $\mathcal{C_1}$ be the challenger of the CPA-security game for $\prod_1$. The description of $\mathcal{B}$ is as follows.

1. $\mathcal{C}_1$ sends $pk_1$ to $\mathcal{B}$.
2. $\mathcal{B}$ generates $(pk_2, sk_2) \leftarrow Gen_2(1^{\lambda})$ and sends $pk = (pk_1, pk_2)$ to $\mathcal{A}$.
3. $\mathcal{A}$ sends $(m_0, m_1)$ to $\mathcal{B}$.
4. $\mathcal{B}$ randomly generates $r$ and sends $(m_0 \oplus r, m_1 \oplus r)$ to $\mathcal{C}_1$.
5. $\mathcal{C}_1$ returns the challenge ciphertext $c_1^*$ to $\mathcal{B}$.
6. $\mathcal{B}$ computes $c_2 \leftarrow Enc_2(pk_2, r)$ and sends $(c_1^*, c_2)$ to $\mathcal{A}$.
7. $\mathcal{A}$ returns $b' \in \{0,1\}$ to $\mathcal{B}$.
8. $\mathcal{B}$ outputs $b'$ as its answer.

Observe that if $c_1^*$ is an encryption of $m_0 \oplus r$ (i.e., $\mathcal{C}_1$ chose the first message to encrypt), then $(c_1^*, c_2)$ is an encryption of $m_0$ under the $\prod$ scheme. Similarly, if $c_1^*$ is an encryption of $m_1 \oplus r$, then $(c_1^*, c_2)$ is an encryption of $m_1$ under the $\prod$ scheme. Therefore, $\mathcal{B}$ has perfectly simulated the challenger of CPA-security for $\prod$ with the challenge bit being consistent with the choice used by $\mathcal{C}_1$. This implies that

$$\mathsf{Pr}[\mathcal{A} \text{ wins in CPA-security game for }\prod] = \mathsf{Pr}[\mathcal{B} \text{ wins in CPA-security game for }\prod\\_1]$$

Observe that we didn't use any facts about the security of $\prod_2$ in the above proof. Similarly, we can use the same proof for arguing with respect to $\prod_2$ by using the fact that the distribution $\{m \oplus r, r\}_r$ is the same as $\{r, m\oplus r\}_r$. In other words, $Enc(pk, m)$ remain the same if it computes $c_1 \leftarrow Enc_1(pk_1, r)$ and $c_2 \leftarrow Enc_2(pk_2, m \oplus r)$.