1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\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$
    – Tristan Nemoz
    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$
    – Tristan Nemoz
    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

0

Reset to default

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.