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?


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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.