SUF-CMA MAC + CPA-secure SKE ⇒ CCA-secure SKE

Fully-black-box reduction · standard model · BN00 · security loss: factor $q_D$ in the MAC term: a CCA adversary making $q_E$ encryption and $q_D$ decryption queries has advantage at most the CPA advantage of an adversary making $q_E$ encryption queries plus $2q_D$ times the SUF-CMA advantage of a forger making $q_E$ tag queries

Statement

Let $\mathsf{SKE}$ be a CPA-secure SKE scheme and $\mathsf{MAC}$ a strongly unforgeable (SUF-CMA) MAC. Encrypt-then-MAC under an $\mathsf{SKE}$ key $k_e$ and an independent $\mathsf{MAC}$ key $k_m$ — encrypt $m$ to $c\leftarrow \mathsf{Enc}(k_e,m)$, output $(c,\mathsf{Tag}(k_m,c))$, and decrypt $(c,t)$ to $\mathsf{Dec}(k_e,c)$ if $\mathsf{Vrfy}(k_m,c,t)=1$ and to $\perp$ otherwise — is a CCA-secure SKE scheme, and with a MAC that is only UF-CMA it can fail CCA security — BN00.

Sketch

An admissible CCA adversary never asks to decrypt an output of the encryption oracle, so by strong unforgeability all its decryption queries are rejected except with negligible probability; answering all of them with $\perp$ leaves a CPA adversary against $\mathsf{SKE}$.

\begin{algorithm}
\algname{Algorithm}
\caption{$\Enc'((k_e, k_m), m)$}
\begin{algorithmic}
\State $c \gets \Enc(k_e, m)$
\State $t \gets \Tag(k_m, c)$
\Return $(c, t)$
\end{algorithmic}
\end{algorithm}

Notes

• With strong unforgeability defined through a verification oracle, the forger forwards every decryption query, and the bound is the CPA advantage plus twice the SUF-CMA advantage at $q_D$ verification queries — BN00; passing from that notion to the single-forgery one costs the factor $q_D$ — BGM04.
• Concurrently and independently, KY00 prove that unforgeability of ciphertexts together with CPA security implies CCA security.