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?

  • $\begingroup$ 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)$. $\endgroup$
    – ckamath
    Commented Sep 5, 2017 at 9:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.