# Prove the advantage of a ROR-CPA is less than or equal to the advantage of a IND-CPA

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.

• 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. – J. Doe Oct 3 '18 at 5:46