Equivalence of SIM-CCA and IND-CCA

From CRYPTUTOR

This page is under construction. Do not rely on its accuracy until it is finished. Please edit this page or use the talk page to leave comments.

SIM-CCA is a stronger definition in secrecy than IND-CCA.

[edit]

SIM-CCA $\Rightarrow$ IND-CCA

Suppose not IND-CCA, therefore, $\exists A\,$ , for the IND-CCA experiment with non-negligible advantage.

Construct Env* and Adv* such that $\forall$ Sim,

$\Pr_{REAL}[z=1] - \Pr_{IDEAL}[z=1] = \epsilon\,$ where $\epsilon\,$ is negligible.

IND-CCA adversary:

Env picks $b \gets \{0,1\}$ .

If Adv asks for encryption, Env sends to Alice, and Alice gives to Adv.

If Adv asks for decryption, Env(or oracle for IND) sends to Bob, and Bob gives to Adv.

If Bob sends to Env the decryption of the ciphertext received from Alice, Env ignores it by not sending the decryption to Adv. Otherwise (ciphertext is not from Alice), Env sends $\mathcal{DO}_{k}(c)$ to Adv.

Adv guesses and sends $b'\,$ to Env.

Env outputs $z$ , where z=1 if Adv guesses correctly (b=b'), z=0 otherwise.

In REAL, Adv in IND-CCA experiment, $\Pr_{REAL}[z=1] = \mbox{ advtg of } A \mbox{ in IND-CCA } = \Pr_{IND-CCA}[b'=b]$

In IDEAL, $\Pr_{IDEAL}[z=1] = 1/2$

Putting the two together,

$\Pr_{REAL}[z=1] - \Pr_{IDEAL}[z=1] = \epsilon\,$

Suppose SIM-CCA is not IND-CCA, then $\exists A\,$ in IND-CCA experiment with non-negligible advtg. Then consider Env* and adversary A* as above, then $\Pr_{REAL}[z=1] - \Pr_{IDEAL}[z=1] = \mbox{ advtg of } A$ which is non-negligible. This contradicts our definition of SIM-CCA.