2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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
    Sep 5, 2017 at 9:31

0

Reset to default

Your Answer

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