# The security level of double encryption

Let PKE $$\Pi' = (Gen', Enc', Dec')$$ and it is secure in the sense of $$S'$$.

Let PKE $$\Pi'' = (Gen'', Enc'', Dec'')$$ and it is secure in the sense of $$S''$$.

$$S'$$ and $$S''$$ may be separation which means that $$S' \not\Rightarrow S''$$ and $$S'' \not\Rightarrow S'$$. For example, $$S' = \text{IND-CCA}, S'' = \text{NM-CPA}$$ or $$S' = \text{OW-CCA}, S'' = \text{IND-CPA}$$.

Let $$\Pi = (Gen, Enc, Dec)$$ be the double encryption such that

$$Gen(1^\lambda) = (pk, sk)$$

1. $$(pk', sk') \gets Gen'(1^\lambda)$$ and $$(pk'', sk'') \gets Gen''(1^\lambda)$$.

2. $$pk = pk' \Vert pk ''$$ and $$sk = sk' \Vert sk''$$.

$$Enc_{pk}(m) = c$$

1. $$(pk' , pk'') \gets pk$$

2. $$c \gets Enc'_{pk'}( Enc''_{pk''}(m))$$.

$$Dec_{sk}(c) = m$$

1. $$(sk' , sk'') \gets sk$$

2. $$c \gets Dec''_{sk''}( Dec'_{sk'}(m))$$.

Is $$\Pi$$ secure both in the sense of $$S'$$ and $$S''$$?

In my opinion, it is true.

We define the CPA game of $$\Pi$$ against an adversary $$A = (A_{1}, A_{2})$$ as follows:

1. $$(pk, sk) \gets Gen(1^\lambda)$$
2. $$(m_{0}, m_{1}, s) \gets A_{1}(pk)$$
3. $$b \leftarrow \{\, 0,1 \,\}$$ and $$c \gets Enc_{pk}(m_{b})$$.
4. $$d \gets A_{2}(c, s)$$.

We say $$A$$ wins if $$b = d$$, and $$\Pi$$ is IND-CPA secure if $$A$$ has at most negligible advantage.

For example, if $$S'' = \text{IND-CPA}$$, assume there exists an adversary $$A$$ with non-negligible advantage against $$\Pi$$. Then we construct an adversary $$A''$$ against $$\Pi''$$ as follows:

$$A''_{1}(pk'') = (m_{0}, m_{1}, s)$$:

1. $$(pk', sk') \gets Gen'(1^\lambda)$$.

2. $$pk = pk' \Vert pk''$$.

3. $$(m_{0}, m_{1}, s) \gets A(pk)$$.

$$A''_{2}(c, s) = d$$:

1. $$c' \leftarrow Enc'_{pk'}(c)$$

2. $$d \gets A(c', s)$$.

We see that $$A''$$ wins the CPA game against $$\Pi''$$ if and only if $$A$$ would have won the corresponding game against $$\Pi$$. Thus $$\Pi''$$ is IND-CPA secure implies that $$\Pi$$ is IND-CPA secure.

If $$S' = \text{IND-CPA}$$, assume there exists an adversary $$A$$ with non-negligible advantage against $$\Pi$$. Then we construct an adversary $$A'$$ against $$\Pi'$$ as follows:

$$A'_{1}(pk') = (m_{0}, m_{1}, s)$$:

1. $$(pk'', sk'') \gets Gen''(1^\lambda)$$.

2. $$pk = pk' \Vert pk''$$.

3. $$(m'_{0}, m'_{1}, s) \gets A(pk)$$.

4. $$m_{0} \gets Enc''_{pk''}(m'_{0})$$ and $$m_{1} \gets Enc''_{pk''}(m'_{1})$$

$$A'_{2}(c, s) = d$$:

1. $$d \gets A(c, s)$$.

We see that $$A'$$ wins the CPA game against $$\Pi'$$ if and only if $$A$$ would have won the corresponding game against $$\Pi$$. Thus $$\Pi'$$ is IND-CPA secure implies that $$\Pi$$ is IND-CPA secure.

Am I right? So I conclude that $$\Pi$$ is a little stronger than $$\Pi'$$ and $$\Pi''$$. If it is true, why is there no double public-key encryption scheme?