Secure double encryption using CPA and CCA

Question

Do you mind if you give me any hints, links or ideas about how to improve the security of double regular encryption and decryption, by using CPA game and CCA game, it sounds interesting question, and I'm still discussing it with my classmate. Given the following info,

The key generation algorithm $(PK, SK) \leftarrow Gen(1^λ)$:

• Compute $(pk, sk) \leftarrow gen(1^λ)$
• Compute $(pk', sk') \leftarrow gen'(1^λ)$
• Set $PK := (pk, pk')$ and $SK := (sk, sk')$

The encryption algorithm $C \leftarrow Enc(m)$:

• Compute $c \leftarrow enc(m)$
• Compute $C \leftarrow enc'(c)$

The decryption algorithm $\tilde{m} \leftarrow Dec(C)$:

• Compute $\tilde{c} \leftarrow dec'(C)$
• Compute $\tilde{m} \leftarrow dec(\tilde{c})$

If both $\pi$ is CPA-secure, then will the new scheme $\Pi$ be CPA-secure? If so, please prove it. If not, please disprove it. Same as for CCA. Kind Regards

Answer 1

For CPA security it is actually enough that the first scheme, i.e., $\pi = (gen, enc, dec)$ is CPA secure.

Lets define the CPA game of a general scheme $\pi = (Gen, Enc, Dec)$ against an adversary $A$ as follows:

1. We sample $(pk, sk) \leftarrow Gen(1^\lambda)$, and send $pk$ to $A$.
2. $A$ outputs messages $m_0$ and $m_1$.
3. We sample $b \leftarrow \{0,1\}$ (a random bit), and $c \leftarrow Enc(pk,m_b)$ (here I add the public key as a parameter to $Enc$, to make the key explicit)
4. $A$ outputs a bit $b'$.

We say $A$ wins if $b = b'$, and the scheme is IND-CPA secure if $A$ has at most negligible advantage.

Now, let $\Pi = (Gen, Enc, Dec)$, $\pi = (gen, enc, dec)$ and $\pi' = (gen', enc', dec')$ be the schemes you suggest in your question. Assume there exists an adversary $A$ with non-negligible advantage against $\Pi$ (i.e., proving $\Pi$ is not IND-CPA secure). Then we can construct an adversary $B$ against $\pi$ as follows:

1. On input $pk$ from the CPA game $B$ samples $(pk', sk') \leftarrow gen'(1^\lambda)$, and sends $PK = (pk, pk')$ to $A$.
2. When $A$ outputs $m_0$, $m_1$ $B$ forwards these messages to the CPA game.
3. On input $c$ from the CPA game $B$ samples $C \leftarrow Enc'(pk', c)$ and sends $C$ to $A$.
4. When $A$ outputs $b'$ $B$ outputs the same bit.

Now you see that $B$ wins the CPA game against $\pi$ if and only if $A$ would have won the corresponding game against $\Pi$. This means that since $A$ has non-negligible advantage against $\Pi$ and $B$ has provided $A$ with messages exactly as in the CPA game against $\Pi$, it follows that $B$ must also have non-negligible advantage against $\pi$. This, however, contradicts $\pi$ being IND-CPA secure, so no such $A$ can exist. I.e., $\Pi$ is also CPA secure.

Note the security of $\pi'$ really does not matter here.

A similar proof might be possible for CCA security, but I have not attempted one.