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?

  • $\begingroup$ 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) $\endgroup$
    – SEJPM
    Mar 8, 2021 at 10:42
  • $\begingroup$ 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? $\endgroup$ Mar 8, 2021 at 12:02
  • $\begingroup$ 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... $\endgroup$ Mar 8, 2021 at 12:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – c633
    Mar 9, 2021 at 12:22
  • 1
    $\begingroup$ 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). $\endgroup$
    – c633
    Mar 9, 2021 at 12:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.