1
$\begingroup$

Note that this is a homework problem assigned in Comp 655, UNC-CH. Please do not give an explicit answer as the instructor prohibited consulting outside resources.


The problem is as follow:

Prove for any $\mathcal{SE}= (K, E, D)$

$\mathbf{Adv}^{\text{RoR-CPA}}_{\mathcal{SE}}(t, q, \mu) \leq \mathbf{Adv}^{\text{Ind-CPA}}_{\mathcal{SE}} (t', q, \mu) \leq 2 * \mathbf{Adv}^{\text{RoR-CPA}}_{\mathcal{SE}}(t'', q, \mu)$

$t$ is approximately equal to $t'$ and $t''$

Intuitively, it's obvious that an indistinguishable chosen plaintext attack is at least as good as a real or random, and both are no better than the advantage of a real or random multiplied by two, but the problem is to create a formal proof. The first step is to break the two parts and prove them separately

$\mathbf{Adv}^{\text{RoR-CPA}}_{\mathcal{SE}}(t, q, \mu) \leq \mathbf{Adv}^{\text{Ind-CPA}}_{\mathcal{SE}} (t', q, \mu) $

and

$\mathbf{Adv}^{\text{Ind-CPA}}_{\mathcal{SE}} (t', q, \mu) \leq 2 * \mathbf{Adv}^{\text{RoR-CPA}}_{\mathcal{SE}}(t'', q, \mu)$

I know this lemma $\mathbf{Adv}^{\text{ind-cpa}}_{\mathcal{SE}[\mathsf{Func}(\ell;L)]}(A)=0$ will be necessary on the IND-CPA end, but I'm unsure of what lemma can be used on the RoR-CPA end.

All guidance or even links to similar proofs are extremely appreciated.

$\endgroup$
  • 1
    $\begingroup$ Note that this is a homework problem assigned in Comp 655, UNC-CH. Please do not give an explicit answer as the instructor prohibited consulting outside resources. $\endgroup$ – J. Doe Oct 3 '18 at 5:46

Your Answer

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