3
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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