# IND-CCA game proof of Encrypt-then-Mac

In [BN07, Subsection 4.3], the authors show that if a symmetric scheme $$\mathcal{SE}$$ is IND-CPA and a MAC $$\mathcal{MA}$$ is EUF-CMA (though they use the SUF-CMA notation, but I think it refers to the same notion?), then the symmetric scheme $$\mathcal{SE'}$$, constructed via the Encrypt-the-MAC technique, is IND-CCA secure.

Unfortunately, they show it the following way:

1. $$\mathcal{SE}$$ being IND-CPA implies $$\mathcal{SE'}$$ being IND-CPA
2. $$\mathcal{MA}$$ being EUF-CMA implies $$\mathcal{SE'}$$ being INT-CTXT
3. $$\mathcal{SE'}$$ being INT-CPA and INT-CTXT implies it being IND-CCA

I struggle to see how a game-based proof of this would look-like. For instance, let us say we have an adversary $$\mathcal{A}$$ that breaks IND-CCA security of $$\mathcal{SE'}$$, and let us consider a reduction $$\mathcal{R}$$ that has access to this adversary and tries to break either IND-CPA security of $$\mathcal{SE}$$ or the EUF-CMA security of $$\mathcal{MA}$$. How would the reduction proceed, since it does not have access to a decryption oracle?

Assuming we work in the real-or-random setup, I understand the reduction can record the queries that $$\mathcal{A}$$ does in order to know how it should answer on these particular queries. However, how is it possible for $$\mathcal{R}$$ to answer decryption queries which are not stored in its database? If we consider that $$\mathcal{A}$$ won't try to query the decryption of some $$y$$ without previously having asked the encryption of $$x$$ which resulted in $$y=\mathrm{Enc}(x)$$, then what's the point of giving a decryption oracle to $$\mathcal{A}$$ at all? Should $$\mathcal{R}$$ answer with a random $$r=\mathrm{Enc}^{-1}(y)$$, hoping that $$\mathcal{A}$$ won't ever query $$x$$ such that $$r\neq y=f(x)$$? In that case doesn't this potentially break $$\mathcal{A}$$'s strategy to break IND-CCA?

• The SUF-CMA they use is strong unforgeability, i.e. an adversary can't even come up with a new tag for a message they already received a tag from the oracle for. What they call "WUF-CMA" tends to be more in-line with standard definitions of EUF-CMA (the definitions are in the paper as Figure 6) – SEJPM Mar 8 at 10:42
• Yes, I tried to read this answer but unfortunately, neither this answer (at the best of my understanding) nor BN07 gives a definition of EUF-CMA. The thing is, I'm working on this article which states that EUF-CMA+IND-CPA => IND-CCA, citing BN07 as the original, classical proof for this fact. A problem arises however: BN07 states that IND-CPA+WUF-CMA is not necessarily IND-CCA (contrarily to IND-CPA+SUF-CMA). Hence, we would have something like SUF-CMA => EUF-CMA => WUF-CMA? – Tristan Nemoz Mar 8 at 12:02
• Unless I'm mistaken and BN07 shows SUF-CMA + IND-CPA => IND-CCA3, since we're using an authentication mechanism (as stated in this answer)? But I'm almost sure CEV20 tries to define qIND-qCCA2... – Tristan Nemoz Mar 8 at 12:08
• A direct proof of IND-CPA + EUF-CMA => IND-CCA2 can be found in Boneh-Shoup's cryptobook (Theorem 9.2), EUF-CMA is defined by the attack game 6.1. – c633 Mar 9 at 12:22
• Looking at CEV20, it seems that their definition of EUF-CMA (taken from BZ13) tends to be more in-line with classical SUF-CMA (though it's tricky to define these security notions properly in the quantum setting, see recent results on defining security for MAC, e.g. AMRS20). – c633 Mar 9 at 12:31