# How can I show the new crypto scheme is still IND-CCA1 in proof of “IND-CCA1 does not imply NM-CPA”?

I am trying to show IND-CCA1 does not imply NM-CPA. From what I have read the "classical" proof goes by taking an IND-CCA1 scheme $$E$$ and modifying it so that the encryption of the inverted plaintext is appended to its ciphertext: $$E': m \mapsto (E(m), E(\bar{m}))$$

It is clear $$E'$$ is not NM-CPA since just swapping the two ciphertext parts leads to a non-trivial relation between the two plaintexts (i.e., inverting it).

But how do we show $$E'$$ remains IND-CCA1?

### My work so far:

Assume $$E'$$ is not IND-CCA1 and can be broken by a PPT $$\mathcal{B}$$. Let us then construct a PPT $$\mathcal{A}$$ which breaks $$E$$.

$$\mathcal{B}$$'s decryption oracle for $$E'$$ can be simulated by $$\mathcal{A}$$ by using its own decryption oracle for $$E$$: it receives $$(c_1, c_2)$$ as query and decrypts $$c_1$$ while ignoring the redundant part $$c_2$$.

$$\mathcal{B}$$ chooses two plaintexts $$m_1$$ and $$m_2$$, which $$\mathcal{A}$$ forwards to its challenger. $$\mathcal{A}$$ receives $$E(m_i)$$ as challenge. This is where I am stuck.

It suggests itself to append, e.g., $$E(\bar{m_1})$$ to the challenge and forward it to $$\mathcal{B}$$, but it does not seem to work. If $$i = 1$$ everything is good, but as far as I can tell $$\mathcal{B}$$'s behavior is undefined if it receives $$(E(m_2), E(\bar{m_1}))$$ at this point.

What am I missing?

• This follows by a hybrid argument. You want to show that $E'(m_1)=(E(m_1),E(\bar{m}_1))$ is indistinguishable (denoted by $\approx$) from $E'(m_2)=(E(m_2),E(\bar{m}_2))$ (given that ciphertexts $\mathcal{B}$ queries the oracle). Define the intermediate distribution as $H(m_1,m_2)=E((m_2,\bar{m}_1))$. By the indistinguishability of $E$, $E'(m_1)\approx H(m_1,m_2)$ and $H(m_1,m_2)\approx E'(m_2)$; by transitivity of $\approx$ $E'(m_1)\approx E'(m_2)$. Commented Sep 5, 2017 at 9:31