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

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?

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)$$.