# security against CPA attack?

Let $\mathcal{E} = (E,D)$ be a CPA secure cipher.

Let's define $\mathcal{E'} = (E', D')$, where $E'(k,m) = E(k, E(k,m))$.

How can I prove that $\mathcal{E'}$ will be CPA secure if $\mathcal{E}$ is?

My guess: Let $a$ be the CPA advantage of an attacker over $\mathcal{E}$, that is, $\mathrm{CPAadv}[\mathcal{A, E}] = a$.

As $\mathcal{E}$ is CPA secure, then $a$ is negligible, thus $E(k,m)$ provides a negligible advantage to some arbitrary efficient attacker.

Let $E(k,m) = e$. If I repeat the prodecure $E(k,e)$, $E$ should give the attacker another negligible advantage $b$.

Then, the total advantage given by $E(k,E(k,m))$ would be $a+b$, and since they are both negligible, $a+b$ would be negligible and $\mathcal{E'}$ would be secure.

• You should attempt a proof by reduction. – Maeher May 2 '18 at 3:59

You can prove this by contradiction. Suppose $\mathcal{E'}$ is not CPA-Secure, meaning there exists an attacker $\mathcal{A}$ who can break this scheme with non negligible probability. Using this attacker, we try to break CPA-Security of $\mathcal{E}$ with non negligible probability as follows:
• The adversary $\mathcal{B}$ (for breaking $\mathcal{E}$) outputs two plaintexts $m_0$ and $m_1$.
• A bit $b$ is then chosen uniformly at random $b \leftarrow \{0,1\}$ and $\mathcal{B}$ receives the encryption of $m_b$ i.e., $c=E(k,m_b)$.
• Based on the definition of CPA indistinguishability experiment (see section 3.5 in Katz-Lindell book), the adversary has still access to the encryption oracle and can query this oracle at the point $c$ receiving $c'=Enc(k,c)$. (Here, we assume that the plaintext and ciphertext space is the same.)
• $\mathcal{B}$ emulates the CPA indistinguishability experiment for $\mathcal{A}$ by sending this challenge ciphertext $c'$ to $\mathcal{A}$.
• $\mathcal{A}$ outputs a bit $b'$.
• Eventually, $\mathcal{B}$ returns the same outbuts bit $b'$ as $\mathcal{A}$.
Now, it is obvious that assuming non-negligible success probability for $\mathcal{A}$, the success probability of $\mathcal{B}$ in breaking $\mathcal{E}$ is non-negligible too.