We are given the following securitygame $G^{\text{LOSTNAME}}$:

  1. Generate $k \leftarrow \{0,1\}^{\kappa}$ uniformly at random
  2. Choose $h \leftarrow \{0,1\}$ uniformly random
  3. Create decryption oracle $\mathcal{O}_{\text{Dec}}$ that on input c returns $Dec_{k}(c)$
  4. Create a one-time test oracle $\mathcal{O}_{\text{Test}}$ that on $m_1$ $m_2$ returns $Enc_{k}(m_h)$
  5. Call $\mathcal{A}$ with the security parameter and the oracles await $h'$
  6. If $c*$ (output of the testoracle) was input to the decryption oracle ACCEPT/REJECT randomly
  7. If $h'=h$ ACCEPT else REJECT

Now I should prove that IND-CCA -> LOSTNAME and LOSTNAME -> IND-CCA. The first direction is easy but the second one is not clear to me. In the IND-CCA setting we also have an encryption oracle, so an attacker on a scheme $\Pi$ would not be an attacker against LOSTNAME in my opinion. I also have no idea how I would prove that the encryption oracle can just be omitted. So how would I prove that the encryption oracle is actually irellevant? Any hint is highly appreciacted.

  • 1
    $\begingroup$ Have you tried to prove the contrapositive? $\endgroup$
    – Lery
    Feb 9, 2021 at 17:41
  • $\begingroup$ This is what I am trying, but I run into the problem I tried to describe. To prove LOSTNAME -> IND-CCA I would need to assume it is LOSTNAME secure but not IND-CCA secure and then construct a reduction from the LOSTNAME attacker to the IND-CCA attacker. But the IND-CCA attacker requires an encryption oracle which I dont have nor do I know how I would emulate that encryption oracle. I just cant think of any way I can construct this, but I mean it is required that the IND-CCA attacker gets this encryption oracle otherwise he is not in the IND-CCA setting. $\endgroup$
    – Chessn00b
    Feb 9, 2021 at 18:16
  • $\begingroup$ You could prove that $\neg \text{IND-CCA} \implies \neg \text{LOSTNAME}$ instead. Assume an adversary with advantage $\epsilon$ against CCA and transform it into an adversary against LOSTNAME. $\endgroup$
    – Lery
    Feb 9, 2021 at 18:28
  • $\begingroup$ So I meant exactly what you wrote with above, but I guess I was imprecise. My problem is that the CCA Attacker has one more oracle he can use (an encryption oracle he can query as much as he likes). And my problem is that in LOSTNAME I dont have that. I also belive that I cannot assume that the CCA attacker just does not use the encryption oracle. So how do I transform a CCA-attacker that uses that extra oracle into one that does not? Since I cant assume that the CCA-attacker just does not use it (at least not without loss of generality) I dont see how this would ever be possible. $\endgroup$
    – Chessn00b
    Feb 9, 2021 at 20:12


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.